Mobile Facility
Location
This applet is a visual demonstration of my work with David Kirkpatrick on bounded-velocity approximations of the mobile Euclidean k-centre and k-median problems. Results related to this work were presented at CCCG in 2003, 2004, and 2005, at FWCG in 2005, at ISAAC in 2007, and in journal form in IJCGA in 2006 and 2008, in CGTA in 2009, and in DAM in 2009. For details, see my publications. Improvements on the visual presentation of data used in this applet were suggested by Will Evans, Tamara Munzner, and Alan Wagner. | |
This applet displays a set of mobile clients (blue)
and various mobile centre functions and mobile medians functions.
Clients may be added by clicking inside the red rectangle or by using the
slider. Clients may be moved by clicking and dragging (easier when
motion is paused).
Centre Functions
Also displayed is the convex hull in yellow. | |
Median Functions
2-Centre
Functions
References [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^{2}. 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^{3}. 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. |
Page last updated March 26, 2009.