Grelier, Nicolas
Hardness and Approximation of Minimum Convex Partition
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 NPhard, 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 kdirected 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 NonCrossing Segments problem. We show that this problem is NPhard, and present an FPT algorithm. This allows us to obtain a constantapproximation 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:145:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16053},
URN = {urn:nbn:de:0030drops160530},
doi = {10.4230/LIPIcs.SoCG.2022.45},
annote = {Keywords: degenerate point sets, point cover, noncrossing segments, approximation algorithm, complexity}
}
01.06.2022
Keywords: 

degenerate point sets, point cover, noncrossing segments, approximation algorithm, complexity 
Seminar: 

38th International Symposium on Computational Geometry (SoCG 2022)

Issue date: 

2022 
Date of publication: 

01.06.2022 