License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.3
URN: urn:nbn:de:0030-drops-82199
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8219/
Go to the corresponding LIPIcs Volume Portal

Ahn, Hee-Kap ; Bae, Sang Won ; Choi, Jongmin ; Korman, Matias ; Mulzer, Wolfgang ; Oh, Eunjin ; Park, Ji-won ; van Renssen, André ; Vigneron, Antoine

Faster Algorithms for Growing Prioritized Disks and Rectangles

pdf-format:
LIPIcs-ISAAC-2017-3.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{ahn_et_al:LIPIcs:2017:8219,
  author =	{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{\'e} van Renssen and Antoine Vigneron},
  title =	{{Faster Algorithms for Growing Prioritized Disks and Rectangles}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{3:1--3:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8219},
  URN =		{urn:nbn:de:0030-drops-82199},
  doi =		{10.4230/LIPIcs.ISAAC.2017.3},
  annote =	{Keywords: map labeling, growing disks, elimination order}
}

Keywords: map labeling, growing disks, elimination order
Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 07.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI