The Gaussian Centre of a Set of Mobile Points
Stéphane Durocher, David G. Kirkpatrick · Canadian Conference on Computational Geometry · 2003
Given a set of client positions as input, facility location attempts to find positions for a set of facilities to optimize some objective function. In mobile facility location, clients undergo continuous motion with bounded velocity and the problem becomes maintaining the position of a mobile facility. This new area within the classical field of facility location is attractive for the many new challenges it presents, problems which did not exist in static facility location. The velocity of the mobile Euclidean centre in two or more dimensions (centre of the smallest enclosing sphere) is unbounded [BBKS00]. It is natural to impose some upper bound on the velocity of a facility. Thus, one must approximate the position of the centre. The goal is to balance a good approximation factor while maintaining low velocity. To solve these two opposing goals, we present the Gaussian centre as an approximation to the mobile Euclidean centre.