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
Thumbnail PDF

File

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

Document Identifiers

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

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

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