Motivated by map labeling, we study the problem in which ]  we are given a collection of n disks D_1,%DIFDELCMD < \dots%%% , D_n in the plane that grow at possibly different speeds. Whenever two disks meet , the one with the lower 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. This 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\big(\big(\big)\big) the ratio of the fastest speed to the slowest speed of disks or the spread of 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.
Motivated by map labeling, Funke, Krumpe, and Storandt IWOCA 2016] introduced the following problem: we are given a sequence of n disks %DIFDELCMD < \dots%%% in the plane . Initially, all disks have radius 0, and they grow at constant, but possibly different, speeds. Whenever two disks touch , the one with the higher index disappears. The goal is to determine the elimination order, i.e., the order in which the disks disappear . We provide the first general subquadratic algorithm for this problem. Our solution extends to other shapes ( e.g., rectangles), and it works in any fixed dimension. We also describe an alternative algorithm that is based on quadtrees. Its running time is O\big(n\big(\log n + \min \{ \log \Delta, \log \Phi \}\big)\big), where \Delta is the ratio of the fastest and the slowest growth rate and \Phi is the ratio of the largest and the smallest distance between two disk centers. This improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017] , and Funke and Storandt [ EuroCG 2017]. Finally, we give an \Omega(n\log n) lower bound , showing that our quadtree algorithms are almost tight.
R
we study the problem in which
Funke, Krumpe, and Storandt
A
IWOCA 2016
A
introduced the following problem:
R
collection
sequence
D
D_1,
D
, D_n
R
that grow at possibly different
. Initially, all disks have radius 0, and they grow at constant, but possibly different,
R
meet
touch
R
lower
higher
D
This problem was introduced by Funke, Krumpe, and Storandt
R
IWOCA 2016
The goal is to determine the elimination order, i.e., the order in which the disks disappear
R
computing the times and the order of disappearance. This algorithm also works for
this problem. Our solution extends to
R
such as rectangles)and
e.g., rectangles), and it works
R
Using quadtrees, we provide
We also describe
R
runs in near linear time , although this second algorithm has a logarithmic dependence on either
is based on quadtrees. Its running time is O
A
n
A
\log n + \min \{ \log \Delta, \log \Phi \}
A
, where \Delta is
R
speed to the slowest speed of disks or the spread of disk centers (the
and the slowest growth rate and \Phi is the
R
maximum to the minimum distance between them). Our result
largest and the smallest distance between two disk centers. This
A
,
R
EWCG
EuroCG
D
on the problem