Minimum convex partition of a constrained point set
From MaRDI portal
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\).
Recommendations
- Minimum convex partition of point sets
- A fixed parameter algorithm for optimal convex partitions
- Approximation Algorithms for the Minimum Convex Partition Problem
- Solving the minimum convex partition of point sets with integer programming
- Polynomial-time instances of the minimum weight triangulation problem
Cites work
- Computational Geometry in C
- Computing the minimum weight triangulation of a set of linearly ordered points
- Decomposing a Polygon into Simpler Components
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- Minimum convex partition of a constrained point set
- ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
- Polynomial-time instances of the minimum weight triangulation problem
Cited in
(16)- A fixed parameter algorithm for optimal convex partitions
- Minimum convex partitions of multidimensional polyhedrons
- On almost empty monochromatic triangles and convex quadrilaterals in colored point sets
- Minimum convex partition of point sets
- Decompositions, partitions, and coverings with convex polygons and pseudo-triangles
- Minimum Convex Partitions and Maximum Empty Polytopes
- Computing optimal islands
- A Convex Approach to Minimal Partitions
- Convex quadrangulations of bichromatic point sets
- Minimum weight convex Steiner partitions
- Approximation Algorithms for the Minimum Convex Partition Problem
- Minimum convex partition of a constrained point set
- Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge)
- An integer programming formulation using convex polygons for the convex partition problem
- Solving the minimum convex partition of point sets with integer programming
- Decomposing a simple polygon into pseudo-triangles and convex polygons
This page was built for publication: Minimum convex partition of a constrained point set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5929323)
