2026-07-22T10:53:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8219 2024-03-06T10:41:45Z ddc:004 open_access

Faster Algorithms for Growing Prioritized Disks and Rectangles Ahn, Hee-Kap Bae, Sang Won Choi, Jongmin Korman, Matias Mulzer, Wolfgang Oh, Eunjin Park, Ji-won van Renssen, André Vigneron, Antoine map labeling growing disks elimination order Motivated by map labeling, we study the problem in which we are given a collection of n disks in the plane that grow at possibly different speeds. Whenever two disks meet, the one with the higher index disappears. This problem was introduced by Funke, Krumpe, and Storandt[IWOCA 2016]. We provide the first general subquadratic algorithm for computing the times and the order of disappearance. Our algorithm also works for other shapes (such as rectangles) and in any fixed dimension. Using quadtrees, we provide an alternative algorithm that runs in near linear time, although this second algorithm has a logarithmic dependence on either the ratio of the fastest speed to the slowest speed of disks or the spread of the disk centers (the ratio of the maximum to the minimum distance between them). Our result improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EWCG 2017]. Finally, we give an \Omega(n\log n) lower bound on the problem, showing that our quadtree algorithms are almost tight. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hee-Kap Ahn and Sang Won Bae and Jongmin Choi and Matias Korman and Wolfgang Mulzer and Eunjin Oh and Ji-won Park and André van Renssen and Antoine Vigneron 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.3 urn:nbn:de:0030-drops-82199 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.3 eng https://creativecommons.org/licenses/by/3.0/legalcode