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. The first problem is on computing k circles of minimum (common) radius with centers on L which can cover the members in P. We propose three algorithms for this problem. The first one runs in O(nklogn) time and O(n) space. The second one runs in O(nk + k²log³n) time and O(nlogn) space assuming that the points are sorted along L, and is efficient where k < < n. The third one is based on parametric search and it runs in O(nlogn + klog⁴n) time. The next one is on computing the minimum radius circle centered on L that can enclose at least k points. The time and space complexities of the proposed algorithm are O(nk) and O(n) respectively. Finally, we study the situation where the points are associated with k colors, and the objective is to find a minimum radius circle with center on L such that at least one point of each color lies inside it. We propose an O(nlogn) time algorithm for this problem. [ABSTRACT FROM AUTHOR]