We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set.
- Authors
Durocher, Stephane; Keil, J. Mark; Mehrabi, Saeed; Mondal, Debajyoti
- Abstract
Chvátal and Klincsek (1980) gave an O (n 3) -time algorithm for the problem of finding a maximum-cardinality convex subset of an arbitrary given set P of n points in the plane. This paper examines a generalization of the problem, the Bottleneck Convex Subsets problem: given a set P of n points in the plane and a positive integer k , select k pairwise disjoint convex subsets of P such that the cardinality of the smallest subset is maximized. Equivalently, a solution maximizes the cardinality of k mutually disjoint convex subsets of P of equal cardinality. We give an algorithm that solves the problem exactly, with running time polynomial in n when k is fixed. We then show the problem to be NP-hard when k is an arbitrary input parameter, even for points in general position. Finally, we give a fixed-parameter tractable algorithm parameterized in terms of the number of points strictly interior to the convex hull.
- Subjects
CONVEX sets; POINT set theory; POLYNOMIAL time algorithms; NP-hard problems; ARBITRARY constants; PROBLEM solving
- Publication
International Journal of Computational Geometry & Applications, 2023, Vol 33, Issue 1/2, p25
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195922410035