Minimum enclosing circle of a set of fixed points and a mobile point (Q396467)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimum enclosing circle of a set of fixed points and a mobile point |
scientific article |
Statements
Minimum enclosing circle of a set of fixed points and a mobile point (English)
0 references
13 August 2014
0 references
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.
0 references
Euclidean 1-centre problem
0 references
minimum enclosing circle
0 references
centre function
0 references
farthest-point Voronoi diagram
0 references
mobile facility location
0 references
algorithm
0 references