Minimum enclosing circle of a set of fixed points and a mobile point (Q396467): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Ivana Linkeová / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65D18 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6329750 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Euclidean 1-centre problem | |||
Property / zbMATH Keywords: Euclidean 1-centre problem / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
minimum enclosing circle | |||
Property / zbMATH Keywords: minimum enclosing circle / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
centre function | |||
Property / zbMATH Keywords: centre function / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
farthest-point Voronoi diagram | |||
Property / zbMATH Keywords: farthest-point Voronoi diagram / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
mobile facility location | |||
Property / zbMATH Keywords: mobile facility location / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
algorithm | |||
Property / zbMATH Keywords: algorithm / rank | |||
Normal rank |
Revision as of 16:24, 29 June 2023
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