Minimum convex partition of a constrained point set (Q5929323): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Polynomial-time instances of the minimum weight triangulation problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimum convex partition of a constrained point set / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Decomposing a Polygon into Simpler Components / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computing the minimum weight triangulation of a set of linearly ordered points / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computational Geometry in C / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3992847 / rank | |||
Normal rank |
Latest revision as of 16:02, 3 June 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