Document Open Access Logo

Computing Low-Cost Convex Partitions for Planar Point Sets Based on a Memetic Approach (CG Challenge)

Authors Laurent Moalic , Dominique Schmitt, Julien Lepagnot, Julien Kritter

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2020.84.pdf
  • Filesize: 1.18 MB
  • 9 pages

Document Identifiers

Related Versions

  • A description of the 2020 CG:SHOP Challenge with related work and overall outcomes can be found at [Erik D. Demaine et al., 2020] https://arxiv.org/abs/2004.04207.

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

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.

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

Author Details

Laurent Moalic
  • Université de Haute-Alsace, IRIMAS UR 7499, F-68100 Mulhouse, France
  • Université de Strasbourg, France
Dominique Schmitt
  • Université de Haute-Alsace, IRIMAS UR 7499, F-68100 Mulhouse, France
  • Université de Strasbourg, France
Julien Lepagnot
  • Université de Haute-Alsace, IRIMAS UR 7499, F-68100 Mulhouse, France
  • Université de Strasbourg, France
Julien Kritter
  • Université de Haute-Alsace, IRIMAS UR 7499, F-68100 Mulhouse, France
  • Université de Strasbourg, France

References

  1. CGAL, Computational Geometry Algorithms Library. URL: http://www.cgal.org.
  2. 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.
  3. Nicolas Grelier. Minimum convex partition of point sets is NP-hard, 2019. URL: http://arxiv.org/abs/1911.07697.
  4. 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.
  5. 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. Google Scholar
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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact