LIPIcs.SoCG.2020.84.pdf
- Filesize: 1.18 MB
- 9 pages
Document
Computing Low-Cost Convex Partitions for Planar Point Sets Based on a Memetic Approach (CG Challenge)
Authors
Laurent Moalic 
,
Julien Kritter
-
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
- Université de Haute-Alsace, IRIMAS UR 7499, F-68100 Mulhouse, France
- Université de Strasbourg, France
Cite As Get BibTex
Laurent Moalic, Dominique Schmitt, Julien Lepagnot, and Julien Kritter. Computing Low-Cost Convex Partitions for Planar Point Sets Based on a Memetic Approach (CG Challenge). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 84:1-84:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.84
Abstract
We present a memetic approach designed to tackle the 2020 Computational Geometry Challenge on the Minimum Convex Partition problem. It is based on a simple local search algorithm hybridized with a genetic approach. The population is brought down to its smallest possible size - only 2 individuals - for a very simple implementation. This algorithm was applied to all the instances, without any specific parameterization or adaptation.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- metaheuristics
- memetic algorithms
- convex partition optimization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- CGAL, Computational Geometry Algorithms Library. URL: http://www.cgal.org.
- 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.
- Nicolas Grelier. Minimum convex partition of point sets is NP-hard, 2019. URL: http://arxiv.org/abs/1911.07697.
- Laurent Moalic and Alexandre Gondran. Variations on memetic algorithms for graph coloring problems. Journal of Heuristics, 24(1):1-24, 2018. URL: https://doi.org/10.1007/s10732-017-9354-9.
-
Pablo Moscato and Carlos Cotta. A Gentle Introduction to Memetic Algorithms. In F. Glover and G. A. Kochenberger, editors, Handbook of Metaheuristics, pages 105-144. Springer, 2003.
