TY - JOUR

T1 - Topological stability of kinetic k-centers

AU - van der Hoog, Ivor

AU - Kreveld, Marc J. van

AU - Meulemans, Wouter

AU - Verbeek, Kevin

AU - Wulms, Jules

N1 - Funding Information:
W. Meulemans and J. Wulms are (partially) supported by the Netherlands eScience Center (NLeSC) under grant number 027.015.G02 . K. Verbeek is supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 639.021.541 . Research on the topic of this paper was initiated at the 3rd Workshop on Applied Geometric Algorithms (AGA 2017) in Vierhouten, The Netherlands, supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 639.023.208 .

PY - 2021/4/18

Y1 - 2021/4/18

N2 - We study the k-center problem in a kinetic setting: given a set of continuously moving points P in the plane, determine a set of k (moving) disks that cover P at every time step, such that the disks are as small as possible at any point in time. Whereas the optimal solution over time may exhibit discontinuous changes, many practical applications require the solution to be stable: the disks must move smoothly over time. Existing results on this problem require the disks to move with a bounded speed, but this model allows positive results only for k<3. Hence, the results are limited and offer little theoretical insight. Instead, we study the topological stability of k-centers. Topological stability was recently introduced and simply requires the solution to change continuously, but may do so arbitrarily fast. We prove upper and lower bounds on the ratio between the radii of an optimal but unstable solution and the radii of a topologically stable solution—the topological stability ratio—considering various metrics and various optimization criteria. For k=2 we provide tight bounds, and for small k>2 we can obtain nontrivial lower and upper bounds. Finally, we provide an algorithm to compute the topological stability ratio in polynomial time for constant k.

AB - We study the k-center problem in a kinetic setting: given a set of continuously moving points P in the plane, determine a set of k (moving) disks that cover P at every time step, such that the disks are as small as possible at any point in time. Whereas the optimal solution over time may exhibit discontinuous changes, many practical applications require the solution to be stable: the disks must move smoothly over time. Existing results on this problem require the disks to move with a bounded speed, but this model allows positive results only for k<3. Hence, the results are limited and offer little theoretical insight. Instead, we study the topological stability of k-centers. Topological stability was recently introduced and simply requires the solution to change continuously, but may do so arbitrarily fast. We prove upper and lower bounds on the ratio between the radii of an optimal but unstable solution and the radii of a topologically stable solution—the topological stability ratio—considering various metrics and various optimization criteria. For k=2 we provide tight bounds, and for small k>2 we can obtain nontrivial lower and upper bounds. Finally, we provide an algorithm to compute the topological stability ratio in polynomial time for constant k.

KW - Mobile facility location

KW - Stability analysis

KW - Time-varying data

UR - http://www.scopus.com/inward/record.url?scp=85103401297&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2021.03.026

DO - 10.1016/j.tcs.2021.03.026

M3 - Article

SN - 0304-3975

VL - 866

SP - 145

EP - 159

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -