Hardness and Approximation of Minimum Convex Partition
OPEN ACCESS
Loading...
Author / Producer
Date
2022
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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 O(log OPT)-approximation running in O(n8)-time, where OPT denotes the minimum number of convex faces needed, to an O(vnlog n)-approximation algorithm running in O(n2)-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 O(k)-approximation algorithm running in nO(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.
Permanent link
Publication status
published
External links
Book title
Volume
224
Pages / Article No.
45
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
38th International Symposium on Computational Geometry (SoCG 2022)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
degenerate point sets; point cover; non-crossing segments; approximation algorithm; complexity
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
Notes
Funding
Related publications and datasets
Is previous version of: