Minimum enclosing circle of a set of fixed points and a mobile point

Given a set S of n static points and a mobile point p   in R2R2, we study the variations of the smallest circle that encloses S∪{p}S∪{p} when p moves along a straight line ℓ  . In this work, a complete characterization of the locus of the center of the minimum enclosing circle (MEC) of S∪{p}S∪{p}, for p∈ℓp∈ℓ, is presented. The locus is a continuous and piecewise differentiable linear function, and each of its differentiable pieces lies either on the edges of the farthest-point Voronoi diagram of S, or on a line segment parallel to the line ℓ  . Moreover, the locus has O(n)O(n) differentiable pieces, which can be computed in linear time, given the farthest-point Voronoi diagram of S.