License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.45
URN: urn:nbn:de:0030-drops-160530
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16053/
Go to the corresponding LIPIcs Volume Portal

Grelier, Nicolas

Hardness and Approximation of Minimum Convex Partition

pdf-format:
LIPIcs-SoCG-2022-45.pdf (0.6 MB)

Abstract

We consider the Minimum Convex Partition problem: Given a set P of n points in the plane, draw a plane graph G on P, with positive minimum degree, such that G partitions the convex hull of P into a minimum number of convex faces. We show that Minimum Convex Partition is NP-hard, and we give several approximation algorithms, from an ?(log OPT)-approximation running in ?(n⁸)-time, where OPT denotes the minimum number of convex faces needed, to an ?(√nlog n)-approximation algorithm running in ?(n²)-time. We say that a point set is k-directed if the (straight) lines containing at least three points have up to k directions. We present an ?(k)-approximation algorithm running in n^{?(k)}-time. Those hardness and approximation results also holds for the Minimum Convex Tiling problem, defined similarly but allowing the use of Steiner points. The approximation results are obtained by relating the problem to the Covering Points with Non-Crossing Segments problem. We show that this problem is NP-hard, and present an FPT algorithm. This allows us to obtain a constant-approximation FPT algorithm for the Minimum Convex Partition Problem where the parameter is the number of faces.

BibTeX - Entry

@InProceedings{grelier:LIPIcs.SoCG.2022.45,
  author =	{Grelier, Nicolas},
  title =	{{Hardness and Approximation of Minimum Convex Partition}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16053},
  URN =		{urn:nbn:de:0030-drops-160530},
  doi =		{10.4230/LIPIcs.SoCG.2022.45},
  annote =	{Keywords: degenerate point sets, point cover, non-crossing segments, approximation algorithm, complexity}
}

Keywords: degenerate point sets, point cover, non-crossing segments, approximation algorithm, complexity
Collection: 38th International Symposium on Computational Geometry (SoCG 2022)
Issue Date: 2022
Date of publication: 01.06.2022

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