LIPIcs.SoCG.2021.20.pdf
- Filesize: 0.68 MB
- 13 pages
Document
An Integer Programming Formulation Using Convex Polygons for the Convex Partition Problem
Authors
-
Part of:
Volume:
37th International Symposium on Computational Geometry (SoCG 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-02
Cite AsGet BibTex
Hadrien Cambazard and Nicolas Catusse. An Integer Programming Formulation Using Convex Polygons for the Convex Partition Problem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.20
https://doi.org/10.4230/LIPIcs.SoCG.2021.20
Abstract
A convex partition of a point set P in the plane is a planar partition of the convex hull of P into empty convex polygons or internal faces whose extreme points belong to P. In a convex partition, the union of the internal faces give the convex hull of P and the interiors of the polygons are pairwise disjoint. Moreover, no polygon is allowed to contain a point of P in its interior. The problem is to find a convex partition with the minimum number of internal faces. The problem has been shown to be NP-hard and was recently used in the CG:SHOP Challenge 2020. We propose a new integer linear programming (IP) formulation that considerably improves over the existing one. It relies on the representation of faces as opposed to segments and points. A number of geometric properties are used to strengthen it. Data sets of 100 points are easily solved to optimality and the lower bounds provided by the model can be computed up to 300 points.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- convex partition
- integer programming
- geometric optimization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Allan S. Barboza, Cid C. de Souza, and Pedro J. de Rezende. Minimum convex partition of point sets - benchmark instances and solutions, 2018. URL: https://www.ic.unicamp.br/~cid/Problem-instances/Convex-Partition.
-
Allan S. Barboza, Cid C. de Souza, and Pedro J. de Rezende. Minimum convex partition of point sets. In Pinar Heggernes, editor, Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings, volume 11485 of Lecture Notes in Computer Science, pages 25-37. Springer, 2019.
- Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S. B. Mitchell. Cg challenge 2020 - minimum convex partition, 2020. URL: https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2020.
- Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S. B. Mitchell. Computing convex partitions for point sets in the plane: The cg:shop challenge 2020, 2020. URL: http://arxiv.org/abs/2004.04207.
-
David P. Dobkin, Herbert Edelsbrunner, and Mark H. Overmars. Searching for empty convex polygons. Algorithmica, 5(4):561-571, 1990.
-
T. Fevens, H. Meijer, and D. Rappaport. Minimum convex partition of a constrained point set. Discret. Appl. Math., 109:95-107, 2001.
-
J. García-López and C.M. Nicolás. Planar point sets with large minimum convex decompositions. Graphs and Combinatorics, 29:1347-1353, 2013.
- Nicolas Grelier. Hardness and approximation of minimum convex partition, 2020. URL: http://arxiv.org/abs/1911.07697.
-
Kiyoshi Hosono. On convex decompositions of a planar point set. Discrete Mathematics, 309(6):1714-1717, 2009.
-
C. Knauer and A. Spillner. Approximation algorithms for the minimum convex partition problem. In Scandinavian Workshop on Algorithm Theory (SWAT), 2006.
- Mario Lomeli-Haro. Minimal convex decompositions, 2012. URL: http://arxiv.org/abs/1207.3468.
- Toshinori Sakai and Jorge Urrutia. Convex decompositions of point sets in the plane, 2019. URL: http://arxiv.org/abs/1909.06105.
-
Jorge Urrutia. Open problem session. In Canadian Conference on Computational Geometry (CCCG), 1998.
-
Da Wei Zheng, Jack Spalding-Jamieson, and Brandon Zhang. Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge). In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 83:1-83:7, Dagstuhl, Germany, 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.