We study the 2-center problem for moving points in the plane. Given a set P of n points, the Euclidean 2-center problem asks for two congruent disks of minimum size that together cover P. Our methods work in the black-box KDS model, where we receive the locations of the points at regular time steps and we know an upper bound d_max on the maximum displacement of any point within one time step. We show how to maintain a (1 + e)-approximation of the Euclidean 2-center in amortized sub-linear time per time step, under certain assumptions on the distribution of the point set P. In many cases --namely when the distance between the centers of the disks is relatively large or relatively small-- the solution we maintain is actually optimal.
|Status||Gepubliceerd - 2013|
|Evenement||29th European Workshop on Computational Geometry (EuroCG 2013) - Braunschweig, Duitsland|
Duur: 17 mrt 2013 → 20 mrt 2013
|Workshop||29th European Workshop on Computational Geometry (EuroCG 2013)|
|Verkorte titel||EuroCG 2013|
|Periode||17/03/13 → 20/03/13|