Minimum convex partition of a constrained point set (Q5929323): Difference between revisions
From MaRDI portal
Latest revision as of 23:34, 1 August 2024
scientific article; zbMATH DE number 1584608
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimum convex partition of a constrained point set |
scientific article; zbMATH DE number 1584608 |
Statements
Minimum convex partition of a constrained point set (English)
0 references
14 June 2001
0 references
Based on a technique used by \textit{E. Anagnostou} and \textit{D. Corneil} [Comput. Geom. 3, No. 5, 247-259 (1993; Zbl 0799.68183)] for the Minimum Weight Triangulation problem, the authors propose a dynamic programming algorithm for finding a convex partition, with respect to a point set \(S\) in the Euclidean space, having a minimum number of convex polygons. Assuming that \(S\) lies on the boundaries of a fixed number of nested convex hulls, the algorithm is proved to be polynomial in the cardinality of \(S\).
0 references
minimum convex partition
0 references
polynomial time algorithm
0 references
dynamic programming
0 references