Some variations on constrained minimum enclosing circle problem

摘要

Given a set P of n points and a straight line L, we study three important variations of minimum enclosing circle problem as follows: (i) Computing k identical circles of minimum radius with centers on L, whose union covers all the points in P. (ii) Computing the minimum radius circle centered on L that can enclose at least k points of P. (iii) If each point in P is associated with one of the k given colors, then compute a minimum radius circle with center on L such that at least one point of each color lies inside it. We propose three algorithms for Problem (i). The first one runs in O(nk log n) time and O(n) space. The second one is efficient where k << n; it runs in O(nlog n+nk+ k2 log3 n) time and O(nlog n) space. The third one is based on parametric search and it runs in O(nlog n+k log4 n) time. For Problem (ii), the time and space complexities of the proposed algorithm are O(nk) and O(n) respectively. For Problem (iii), our proposed algorithm runs in O(nlog n) time and O(n) space.