Centre Functions

• The Euclidean centre is the centre of the smallest enclosing circle. It minimizes the maximum distance to any of the clients. Even when the velocity of the clients is bounded, the velocity of the Euclidean centre is unbounded [BBKS2000]. All other centre functions' approximation factors are measure relative to the radius of the minimum enclosing circle.
• The centre of mass is simply the average position of clients. Its maximum relative velocity is 1 (relative to the velocity of the clients) but its approximation factor is 2.
• The rectilinear centre is the centre of the bounding box. That is, its position is given by finding the respective centres of the x-coordinates and y-coordinates of the set of client positions. The rectilinear centre provides an approximation of (1 + √ 2) / 2 ≈ 1.2071 and a maximum relative velocity of √ 2 ≈ 1.4142 [BBKS2000].
• The Steiner centre improves on these with an approximation factor of ≈ 1.1153 and a maximum relative velocity of 4 / π ≈ 1.2732. In our earlier work we referred to the Steiner centre as Gaussian centre or projection centre.

Also displayed is the convex hull in yellow.

Median Functions
To view median functions, select the Median tab, and any of the medians function checkboxes.

• The Euclidean median, also known by a variety of other names including Weber point, Fermat point, and Toricelli point, minimizes the sum of distances to clients. In general, for greater than four clients, its position cannot be computed exactly. Here the position is approximated using Weiszfeld's algorithm [Weis1937]. Like the Euclidean centre, velocity of the Euclidean median is unbounded even when the velocity of the clients is bounded. The approximation factor of other median functions is measured relative to the sum of distances from clients to the Euclidean median.
• The centre of mass again provides a 2-approximation and has a maximum relative velocity of 1.
• The rectilinear median is found by taking the respective medians of the x-coordinates and y-coordinates of the set of client positions. When the number of clients is even, the rectilinear median may not be unique; in this case we select the midpoint of the range of medians to ensure continuity of motion. The rectilinear centre provides an approximation of √ 2 and a maximum relative velocity of √ 2 [BBKS2000].
• The projection median has an approximation factor of at most 4 / π and a maximum relative velocity of 4 / π.
• The Gaussian median is defined similarly to the Steiner centre. Its approximation factor and velocity have not yet been determined.

2-Centre Functions
To view 2-centre functions, select the 2-Centre tab, and any of the 2-centre function checkboxes.

• The Euclidean 2-centre is a set of two points that correspond to the centre of two discs whose union contains the clients such that the radius of the larger circle is minimized. The mobile Euclidean 2-centre is discontinuous. The approximation factor of other 2-centres functions is measured relative to the maximum distance from any client to the nearest Euclidean 2-centre.
• The rectilinear reflection 2-centre is found by selecting a client (denoted by a blue circle) and its reflection across the rectilinear centre. The rectilinear reflection 2-centre provides an approximation of 2√ 2 and a maximum relative velocity of 2√ 2.
• The rectilinear Steiner 2-centre is found by selecting a client (denoted by a blue circle) and its reflection across the Steiner centre. The Steiner reflection 2-centre provides an approximation of 8 π / 4 and a maximum relative velocity of 8 π / 4.

References
[BBKS2000] Sergei Bespamyatnikh, Binay Bhattacharya, David Kirkpatrick, and Michael Segal. Mobile Facility Location. In proceedings of the Fourth International ACM Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. 4:46-53. 2000. (ps.gz)

[BBKS2006] Sergei Bespamyatnikh, Binay Bhattacharya, David Kirkpatrick, and Michael Segal. Competitive Algorithms for Mobile Centers. Mobile Networks and Applications. 11(2):177-186. 2006.

[Dur2006] Stephane Durocher. Geometric Facility Location under Continuous Motion. Ph.D. thesis. University of British Columbia. 2006. (pubs) (pdf)

[DK2009] Stephane Durocher and David Kirkpatrick. The Projection Median of a Set of Points. Computational Geometry: Theory and Applications. 42:364-375. 2009. (pdf)

[DK2008] Stephane Durocher and David Kirkpatrick. Bounded-Velocity Approximation of Mobile Euclidean 2-Centres. International Journal of Computational Geometry and Applications. 18(3):161-183. 2008. (pdf)

[DK2006] Stephane Durocher and David Kirkpatrick. The Steiner Centre: Stability, Eccentricity, and Applications to Mobile Facility Location. International Journal of Computational Geometry and Applications. 16(4):354-371. 2006. (pubs) (pdf)

[DK2005b] Stephane Durocher and David Kirkpatrick. Bounded-velocity Approximations of the Mobile Euclidean 2-centre. In proceedings of the Fifteenth Annual Fall Workshop on Computational Geometry and Visualization. 15:48-50. 2005. (pubs) (pdf)

[DK2005a] Stephane Durocher and David Kirkpatrick. The Projection Median of a Set Points in R². In proceedings of CCCG. 17:46-50. 2005. (pubs) (pdf)

[DK2004] Stephane Durocher and David Kirkpatrick. The Gaussian Centre and the Projection Centre of a Set Points in R³. In proceedings of CCCG. 16:140-144. 2004. (pubs) (pdf)

[DK2003] Stephane Durocher and David Kirkpatrick. The Gaussian Centre of a Set of Mobile Points. In proceedings of CCCG. 15:123-127. 2003. (pubs) (pdf)

[DP2009] Stephane Durocher and Christophe Paul. Kinetic Maintenance of Mobile k-Centres on Trees. In Discrete Applied Mathematics. 157(7):1432-1446. 2009. (pdf)

[DP2007] Stephane Durocher and Christophe Paul. Kinetic Maintenance of Mobile k-Centres on Trees. In proceedings of ISAAC. Springer Lecture Notes in Computer Science. 4835:341-352. 2007. (pdf)

[Weis1937] Endre Weiszfeld. Sur le Point pour Lequel les Sommes des Distances de n Points Donné est Minimum. Tôhoku Mathematical Journal. 34:355-386. 1937.