Kinetic Euclidean 2-centers in the black-box model

Research output: Contribution to conferenceAbstractAcademic

31 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages173-176
Publication statusPublished - 2013
Event29th European Workshop on Computational Geometry (EuroCG 2013) - Braunschweig, Germany
Duration: 17 Mar 201320 Mar 2013
Conference number: 29

Workshop

Workshop29th European Workshop on Computational Geometry (EuroCG 2013)
Abbreviated titleEuroCG 2013
CountryGermany
CityBraunschweig
Period17/03/1320/03/13

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

  • Cite this

    Berg, de, M. T., Roeloffzen, M. J. M., & Speckmann, B. (2013). Kinetic Euclidean 2-centers in the black-box model. 173-176. Abstract from 29th European Workshop on Computational Geometry (EuroCG 2013), Braunschweig, Germany.