LIPIcs.SoCG.2022.45.pdf
- Filesize: 0.62 MB
- 15 pages
Document
Hardness and Approximation of Minimum Convex Partition
Author
-
Part of:
Volume:
38th International Symposium on Computational Geometry (SoCG 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-01
File
Document Identifiers
Acknowledgements
The author thanks Michael Hoffmann for his helpful advice.
Cite As Get BibTex
Nicolas Grelier. Hardness and Approximation of Minimum Convex Partition. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.45
Abstract
We consider the Minimum Convex Partition problem: Given a set P of n points in the plane, draw a plane graph G on P, with positive minimum degree, such that G partitions the convex hull of P into a minimum number of convex faces. We show that Minimum Convex Partition is NP-hard, and we give several approximation algorithms, from an 𝒪(log OPT)-approximation running in 𝒪(n⁸)-time, where OPT denotes the minimum number of convex faces needed, to an 𝒪(√nlog n)-approximation algorithm running in 𝒪(n²)-time. We say that a point set is k-directed if the (straight) lines containing at least three points have up to k directions. We present an 𝒪(k)-approximation algorithm running in n^{𝒪(k)}-time. Those hardness and approximation results also holds for the Minimum Convex Tiling problem, defined similarly but allowing the use of Steiner points. The approximation results are obtained by relating the problem to the Covering Points with Non-Crossing Segments problem. We show that this problem is NP-hard, and present an FPT algorithm. This allows us to obtain a constant-approximation FPT algorithm for the Minimum Convex Partition Problem where the parameter is the number of faces.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- degenerate point sets
- point cover
- non-crossing segments
- approximation algorithm
- complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Sayan Bandyapadhyay, Santanu Bhowmick, and Kasturi Varadarajan. Approximation schemes for partitioning: Convex decomposition and surface approximation. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1457-1470. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973730.96.
- Allan S. Barboza, Cid C. de Souza, and Pedro J. de Rezende. Minimum convex partition of point sets. In Proceedings of International Conference on Algorithms and Complexity, pages 25-37. Springer, 2019. URL: https://doi.org//10.1007/978-3-030-17402-6_3.
- Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Erik D Demaine, Rudolf Fleischer, Alejandro López-Ortiz, Pat Morin, and J Ian Munro. Online routing in convex subdivisions. International Journal of Computational Geometry & Applications, 12(04):283-295, 2002. URL: https://doi.org/10.1142/S021819590200089X.
- 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). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.20.
- Erik Demaine, Sándor Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S. B. Mitchell. CG:SHOP 2020. https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2020. Accessed: 12/02/2020.
- Adrian Dumitrescu, Sariel Har-Peled, and Csaba D. Tóth. Minimum convex partitions and maximum empty polytopes. In Proceedings of Scandinavian Workshop on Algorithm Theory, pages 213-224. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-31155-0_19.
- Thomas Fevens, Henk Meijer, and David Rappaport. Minimum convex partition of a constrained point set. Discrete Applied Mathematics, 109(1-2):95-107, 2001. URL: https://doi.org/10.1016/S0166-218X(00)00237-7.
- Jesús García-López and Carlos M. Nicolás. Planar point sets with large minimum convex decompositions. Graphs and Combinatorics, 29(5):1347-1353, 2013. URL: https://doi.org/10.1007/s00373-012-1181-z.
- Magdalene Grantson and Christos Levcopoulos. A fixed parameter algorithm for the minimum number convex partition problem. In Japanese Conference on Discrete and Computational Geometry, pages 83-94. Springer, 2004. URL: https://doi.org/10.1007/11589440_9.
- Nicolas Grelier. Hardness and approximation of minimum convex partition. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.07697.
- Leonidas J. Guibas, Mark H. Overmars, and Jean-Marc Robert. The exact fitting problem in higher dimensions. Computational geometry, 6(4):215-230, 1996. URL: https://doi.org/10.1016/0925-7721(95)00020-8.
- Christian Knauer and Andreas Spillner. Approximation algorithms for the minimum convex partition problem. In Proceedings of Scandinavian Workshop on Algorithm Theory, pages 232-241. Springer, 2006. URL: https://doi.org/10.1007/11785293_23.
- Stefan Langerman and Pat Morin. Covering things with things. Discrete & Computational Geometry, 33(4):717-729, 2005. URL: https://doi.org/10.1007/s00454-004-1108-4.
- Andrzej Lingas. The power of non-rectilinear holes. In Proceedings of International Colloquium on Automata, Languages, and Programming, pages 369-383. Springer, 1982. URL: https://doi.org/10.1007/BFb0012784.
- Dániel Marx. Parameterized complexity of independence and domination on geometric graphs. In International Workshop on Parameterized and Exact Computation, pages 154-165. Springer, 2006. URL: https://doi.org/10.1007/11847250_14.
- Joseph S. B. Mitchell. Approximation algorithms for geometric separation problems. Technical report, Dept. of Applied Math. and Statistics, State U. of New York at Stony Brook, 1993. Available at URL: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.7089&rep=rep1&type=pdf.
- Víctor Neumann-Lara, Eduardo Rivera-Campo, and Jorge Urrutia. A note on convex decompositions of a set of points in the plane. Graphs and Combinatorics, 20(2):223-231, 2004. URL: https://doi.org/10.1007/s00373-004-0555-2.
- Franco P. Preparata and Michael I. Shamos. Computational Geometry. Springer-Verlag, New York, 1985. URL: https://doi.org/10.1007/978-1-4612-1098-6.
- Toshinori Sakai and Jorge Urrutia. Convex decompositions of point sets in the plane. arXiv preprint, 2019. URL: http://arxiv.org/abs/1909.06105.
- Allan Sapucaia, Pedro J. de Rezende, and Cid C. de Souza. Solving the minimum convex partition of point sets with integer programming. Computational Geometry, page 101794, 2021. URL: https://doi.org/10.1016/j.comgeo.2021.101794.
- Andreas Spillner. A fixed parameter algorithm for optimal convex partitions. Journal of Discrete Algorithms, 6(4):561-569, 2008. URL: https://doi.org/10.1016/j.jda.2008.07.002.
- Csaba D. Tóth. Binary space partitions for line segments with a limited number of directions. SIAM Journal on Computing, 32(2):307-325, 2003. URL: https://doi.org/10.1137/S0097539702403785.