Minimum enclosing circle of a set of fixed points and a mobile point (Q396467)

A complete characterization of the locus of the Euclidean 1-center problem -- the centre of the minimum enclosing circle of a set of \(n\) fixed points in the plane and one mobile point moving along a straight line is provided. The straight line along which another point moves does not pass through any point of the set of points. A continuous and piecewise differentiable linear function called centre function is defined. The centre function determines for any point lying on the straight line the centre of the minimum enclosing circle with combinatorial complexity \(O(n)\). Each of the differentiable pieces of the centre function lies either on the boundary of the farthest-point Voronoi diagram of the set of points or on a line parallel to the direction of motion. Given the farthest-point Voronoi diagram of the set of points, a simple \(O(n)\) time algorithm for computing the centre function is presented. The obtained results can be used in mobile computing, telecommunication, navigation, geographic information systems, etc.