Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge)

Authors Da Wei Zheng , Jack Spalding-Jamieson, Brandon Zhang



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.83.pdf
  • Filesize: 1.88 MB
  • 7 pages

Document Identifiers

Author Details

Da Wei Zheng
  • Department of Computer Science, University of British Columbia, Vancouver, Canada
Jack Spalding-Jamieson
  • Department of Computer Science, University of British Columbia, Vancouver, Canada
Brandon Zhang
  • Department of Computer Science, University of British Columbia, Vancouver, Canada

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

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)
    0
    PDF Downloads

References

  1. 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.
  2. 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. Google Scholar
  3. 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. Google Scholar
  4. 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.
  5. Nicolas Grelier. Minimum convex partition of point sets is np-hard, 2019. URL: http://arxiv.org/abs/1911.07697.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail