Minimum convex partition of a constrained point set (Q5929323): Difference between revisions

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\).