Topological stability of kinetic k-centers

DOI10.1016/J.TCS.2021.03.026MaRDI QIDQ2662690zbMATH OpenOpenAlexFDO

Authors Ivor van der Hoog, Wouter Meulemans, Kevin Verbeek, Jules Wulms, Marc Van Kreveld

Publication date 14 April 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.00794

zbMATH Keywords

stability analysismobile facility locationtime-varying data

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Continuous location (90B85)

Abstract: 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$.

Recommendations

• Topological stability of kinetic \(k\)-centers
• Approximation algorithm for the kinetic robust \(k\)-center problem
• Kinetic 2-centers in the black-box model
• Kinetic maintenance of mobile \(k\)-centres on trees
• Kinetic Maintenance of Mobile k-Centres on Trees

Cites work

• scientific article; zbMATH DE number 1254001 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• A framework for algorithm stability and its application to kinetic Euclidean MSTs
• Approximation algorithm for the kinetic robust \(k\)-center problem
• BOUNDED-VELOCITY APPROXIMATION OF MOBILE EUCLIDEAN 2-CENTRES
• Data Structures for Mobile Data
• Deformable spanners and applications
• Discrete mobile centers
• Finding the upper envelope of n line segments in O(n log n) time
• Kinetic 2-centers in the black-box model
• Kinetic facility location
• More planar two-center algorithms
• On piercing sets of axis-parallel rectangles and rings
• On the Complexity of Some Common Geometric Location Problems
• On the rectangularp-center problem
• THE STEINER CENTRE OF A SET OF POINTS: STABILITY, ECCENTRICITY, AND APPLICATIONS TO MOBILE FACILITY LOCATION
• The p-Centre Problem-Heuristic and Optimal Algorithms
• The slab dividing approach to solve the Euclidean \(P\)-center problem

Cited in

(5)

• Approximation algorithm for the kinetic robust \(k\)-center problem
• A framework for algorithm stability and its application to kinetic Euclidean MSTs
• Kinetic maintenance of mobile \(k\)-centres on trees
• Stability analysis of kinetic orientation-based shape descriptors
• Topological stability of kinetic \(k\)-centers

This page was built for publication: Topological stability of kinetic \(k\)-centers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2662690)