LIPIcs.SoCG.2020.85.pdf
- Filesize: 1 MB
- 11 pages
Document
Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions (CG Challenge)
Authors
Günther Eder 
,
Martin Held ,
Stefan de Lorenzo ,
Peter Palfrader
-
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
Cite AsGet BibTex
Günther Eder, Martin Held, Stefan de Lorenzo, and Peter Palfrader. Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions (CG Challenge). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 85:1-85:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.85
https://doi.org/10.4230/LIPIcs.SoCG.2020.85
Abstract
Our work on minimum convex decompositions is based on two key components: (1) different strategies for computing initial decompositions, partly adapted to the characteristics of the input data, and (2) local optimizations for reducing the number of convex faces of a decomposition. We discuss our main heuristics and show how they helped to reduce the face count.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Computational Geometry
- geometric optimization
- algorithm engineering
- convex decomposition
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Bernard Chazelle. On the Convex Layers of a Planar Set. IEEE Transactions on Information Theory, 31(4):509-517, July 1985. URL: https://doi.org/10.1109/TIT.1985.1057060.
- 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.
-
Christian Knauer and Andreas Spillner. Approximation Algorithms for the Minimum Convex Partition Problem. In Algorithm Theory - SWAT 2006, pages 232-241, 2006.
-
Jonathan Richard Shewchuk. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In Applied Computational Geometry: Towards Geometric Engineering, volume 1148 of Lecture Notes in Computer Science, pages 203-222. Springer-Verlag, May 1996. ISBN 3-540-61785-X.