Paper Info
Title
The Steiner Centre Of A Set Of Points: Stability, Eccentricity, And Applications To Mobile Facility Location
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,(27) we prove the stability of the Steiner centre is pi/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/pi.
Year
DOI
Venue
2006
10.1142/S0218195906002075
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
Keywords
DocType
Volume
centre, Steiner point, Euclidean centre, smallest enclosing circle, stability, eccentricity, approximation, facility location, mobile facility location
Journal
16
Issue
ISSN
Citations 
4
0218-1959
1
PageRank 
References 
Authors
0.36
0
2
Name
Order
Citations
PageRank
Stephane Durocher134242.89
David G. Kirkpatrick22394541.05