# Kinetic 2-centers in the black-box model

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

10 Citations (Scopus)

## Abstract

We study two versions of 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; the rectilinear 2-center problem correspondingly asks for two congruent axis-aligned squares 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 the rectilinear 2-center in amortized sub-linear time per time step, under certain assumptions on the distribution of the point set P. For the Euclidean 2-center we give a similar result: we can maintain in amortized sub-linear time (again under certain assumptions on the distribution) a (1+e)-approximation of the optimal 2-center. 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. We also present results for the case where the maximum speed of the centers is bounded. We describe a simple scheme to maintain a 2-approximation of the rectilinear 2-center, and we provide a scheme which gives a better approximation factor depending on several parameters of the point set and the maximum allowed displacement of the centers. The latter result can be used to obtain a 2.29-approximation for the Euclidean 2-center; this is an improvement over the previously best known bound of 8/p approx 2.55. These algorithms run in amortized sub-linear time per time step, as before under certain assumptions on the distribution.
Original language English Proc. 29th ACM Symposium on Computational Geometry (SoCG) New York NY Association for Computing Machinery, Inc 145-154 978-1-4503-2031-3 https://doi.org/10.1145/2462356.2462393 Published - 2013 29th Annual Symposium on Computational Geometry (SoCG 20013) - Rio de Janeiro, BrazilDuration: 17 Jun 2013 → 20 Jun 2013Conference number: 29

### Conference

Conference 29th Annual Symposium on Computational Geometry (SoCG 20013) SOCG 2013 Brazil Rio de Janeiro 17/06/13 → 20/06/13

## Fingerprint

Dive into the research topics of 'Kinetic 2-centers in the black-box model'. Together they form a unique fingerprint.