THE STEINER CENTRE OF A SET OF POINTS: STABILITY, ECCENTRICITY, AND APPLICATIONS TO MOBILE FACILITY LOCATION
Authors:
- 1 August 2006
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 16 (04) , 345-371
Abstract
The Euclidean centre (centre of the smallest enclosing sphere) of a set of points P in two or more dimensions is unstable; small perturbations at only a few points of P can result in an arbitrarily large relative change in the position of the Euclidean centre. Any centre function more stable than the Euclidean centre is eccentric; that is, its associated radius exceeds the radius of the smallest enclosing circle for some point sets P. Motivated by applications in mobile facility location (in which clients move continuously with some maximum velocity) we seek alternative notions of centrality that are stable while maintaining low eccentricity. In general there is a trade-off; centre functions with lower eccentricity are less stable. In an attempt to balance the conflicting goals of closeness of approximation and stability, we apply the Steiner centre, traditionally defined for convex polytopes, as a centre function of a set of points in the plane. Although previously defined, the notion of a Steiner centre had not been analyzed in terms of its approximation of the Euclidean centre. Exploiting the equivalence of the two definitions of the Steiner centre established by Shephard,27we prove the stability of the Steiner centre is π/4 and show that the associated radius is at most 1.1153 times the Euclidean radius of any point set P. It follows that a mobile facility located at the Steiner centre of the positions of a set of mobile clients remains close to the Euclidean centre of the clients yet never moves with relative velocity that exceeds 4/π.Keywords
This publication has 12 references indexed in Scilit:
- Smooth kinetic maintenance of clustersComputational Geometry, 2005
- Discrete Mobile CentersDiscrete & Computational Geometry, 2003
- Maintaining the Extent of a Moving Point SetDiscrete & Computational Geometry, 2001
- Data Structures for Mobile DataJournal of Algorithms, 1999
- Approximation of Planar Convex Sets from Hyperplane ProbesDiscrete & Computational Geometry, 1997
- Episodes in Nineteenth and Twentieth Century Euclidean Geometry1995
- The Multiperiod Location-Allocation Problem with Relocation of FacilitiesManagement Science, 1975
- Dynamic Facility LocationManagement Science, 1973
- A valuation property of Steiner pointsMathematika, 1966
- Approximation problems for convex polyhedraMathematika, 1964