LIPIcs.SoCG.2020.83.pdf
- Filesize: 1.88 MB
- 7 pages
Document
Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge)
Authors
Da Wei Zheng 
,
-
Part of:
Volume:
36th International Symposium on Computational Geometry (SoCG 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-08
File
Document Identifiers
Author Details
Acknowledgements
We want to thank Sam Bayless for help with MonoSAT and constraint programming.
Cite AsGet BibTex
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 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 83:1-83:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.83
https://doi.org/10.4230/LIPIcs.SoCG.2020.83
Abstract
The Minimum Convex Partition problem (MCP) is a problem in which a point-set is used as the vertices for a planar subdivision, whose number of edges is to be minimized. In this planar subdivision, the outer face is the convex hull of the point-set, and the interior faces are convex. In this paper, we discuss and implement the approach to this problem using randomized local search, and different initialization techniques based on maximizing collinearity. We also solve small instances optimally using a SAT formulation. We explored this as part of the 2020 Computational Geometry Challenge, where we placed first as Team UBC.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- convex partition
- randomized local search
- planar point sets
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- A.M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters, 9(5):216-219, 1979. URL: https://doi.org/10.1016/0020-0190(79)90072-3.
-
Fahiem Bacchus, Matti Järvisalo, and Ruben Martins, editors. MaxSAT Evaluation 2019: Solver and Benchmark Descriptions. Department of Computer Science Report Series B. Department of Computer Science, University of Helsinki, Finland, 2019.
-
Sam Bayless, Noah Bayless, Holger H. Hoos, and Alan J. Hu. SAT Modulo Monotonic Theories. Proceedings of the 29th AAAI Conference on Artificial Intelligence, 2015.
- Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Joseph S. B. Mitchell, and Dominik Krupke. Computing convex partitions for point sets in the plane: The cg:shop challenge 2020, 2020. URL: http://arxiv.org/abs/2004.04207.
- Nicolas Grelier. Minimum convex partition of point sets is np-hard, 2019. URL: http://arxiv.org/abs/1911.07697.