Optimal algorithms for circle partitioning

Abstract

Given a set of n points F on a circle and an integer k, we would like to find a size k subset of F such that these points are “evenly distributed” on the circle. We define two different criteria to capture the intuitive notion of evenness. Let U be a set of points on a circle and let u ₁, u ₂, u ₃,..., u _k be the order of the points in U visited clockwise starting from u ₁. Denote by d; the distance between u _{i-1(mod k)} and u _i. Let min(U) = min(d _i) denote the minimum distance between every pair of adjacent points and similarly max(U) = max(d _i) denote the maximum distance between every pair of adjacent points. We feel that a set U is evenly distributed if min(U) is the largest among all the size k subset or max(U) is the smallest among all the size k subset. We call the former problem maxmin point location problem and the latter minmax point location problem.

For both problems we find O(_n) time algorithms to find the optimal solutions, if the points on the circle are sorted. The basic idea of the algorithm is to open the circle at some point and treat the circle as a line. By applying the Frederickson's algorithm for tree partitioning, we first find an optimal solution for the corresponding line case (which is a special case of tree), then carefully relocate points in the optimal solution for the line case to get the optimal solution for the original problem. Both problems have applications for resource allocation on Synchronous Ethernet, a protocol designed for real-time applications over Ethernet.