Covering points with convex sets of minimum size (Q1705773)

In this paper algorithms are presented for finding two bounded convex sets, that cover a set \(P\) of \(n\) points in the plane, such that the total area or perimeter of the convex sets is minimized in \(O(n^{4} \log n)\) and \(O(n^{2} \log n)\) time, respectively. The former algorithm is the first result for minimum total area, and the latter one is an improvement on the fastest previous algorithm for minimum total perimeter, which runs in \(O(n^{3})\) time. Both presented algorithms are also extended to find \(k \geq 2\) convex sets minimizing area in \(O(n^{2k(k-1)} \log n)\) time. The proposed algorithms can be applied to detect road intersections from the GPS trajectories of moving vehicles for automated map generation or partial clustering.