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 languageEnglish
Title of host publicationProc. 29th ACM Symposium on Computational Geometry (SoCG)
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
Pages145-154
ISBN (Print)978-1-4503-2031-3
DOIs
Publication statusPublished - 2013
Event29th Annual Symposium on Computational Geometry (SoCG 20013) - Rio de Janeiro, Brazil
Duration: 17 Jun 201320 Jun 2013
Conference number: 29

Conference

Conference29th Annual Symposium on Computational Geometry (SoCG 20013)
Abbreviated titleSOCG 2013
Country/TerritoryBrazil
CityRio de Janeiro
Period17/06/1320/06/13

Fingerprint

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

Cite this