Largest convex hulls for convex-hull disjoint clusters with bounded size
Xuehou Tan, Rong Chen · Theoretical Computer Science · 2025
A cluster is a set of points, with a predefined similarity measure. In this paper, we study the problem of computing the largest possible convex hulls, measured by length and by area, of the points that are selected from a set of convex-hull disjoint clusters, one per cluster. We show that the largest convex hulls for convex-hull disjoint clusters with bounded size , measured by length or area, can be computed in O ( n 4 ) time, where n is the number of given clusters. Our solution of either problem for arbitrarily given points relies on the convex hull of all points. Moreover, for a set of the clusters, whose all points are in convex position, its solution can be reduced to several instances of the problem of computing the single-source shortest-paths in a weighted graph. Not only our results significantly improve upon the known time bound O ( n 9 ) , but also the obtained solutions are unified and simple. Moreover, our algorithms can be used to improve the known results on several other variants of the considered problem.