License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.83
URN: urn:nbn:de:0030-drops-122412
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12241/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-SoCG-2020-83.pdf (2 MB)

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.

BibTeX - Entry

@InProceedings{zheng_et_al:LIPIcs:2020:12241,
  author =	{Da Wei Zheng and Jack Spalding-Jamieson and Brandon Zhang},
  title =	{{Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge)}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{83:1--83:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12241},
  URN =		{urn:nbn:de:0030-drops-122412},
  doi =		{10.4230/LIPIcs.SoCG.2020.83},
  annote =	{Keywords: convex partition, randomized local search, planar point sets}
}

Keywords: convex partition, randomized local search, planar point sets
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI