[Back]

S. Bhore, G. Li, M. Nöllenburg:
"An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling";
Talk: European Symposium on Algorithms, Pisa, Italien; 2020-09-07 - 2020-09-09; in: "28th Annual European Symposium on Algorithms (ESA 2020)", LIPICS, 173 (2020), ISBN: 978-3-95977-162-7; 1 - 24.

Map labeling is a classical problem in cartography and geographic information systems (GIS) that
asks to place labels for area, line, and point features, with the goal to select and place the maximum
number of independent, i.e., overlap-free, labels. A practically interesting case is point labeling with
axis-parallel rectangular labels of common size. In a fully dynamic setting, at each time step, either
a new label appears or an existing label disappears. Then, the challenge is to maintain a maximum
cardinality subset of pairwise independent labels with sub-linear update time. Motivated by this, we
study the maximal independent set (MIS) and maximum independent set (Max-IS) problems on
fully dynamic (insertion/deletion model) sets of axis-parallel rectangles of two types - (i) uniform
height and width and (ii) uniform height and arbitrary width; both settings can be modeled as
rectangle intersection graphs.
We present the first deterministic algorithm for maintaining a MIS (and thus a 4-approximate
Max-IS) of a dynamic set of uniform rectangles with amortized sub-logarithmic update time. This
breaks the natural barrier of
( ) update time (where is the maximum degree in the graph) for
vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating Max-IS and
provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first
give an algorithm that maintains a 4-approximate Max-IS with O(1) update time. In a subsequent
algorithm, we establish the trade-off between approximation quality 2(1 + 1
k ) and update time
O(k2 log n), for k 2 N. We conclude with an algorithm that maintains a 2-approximate Max-IS
for dynamic sets of unit-height and arbitrary-width rectangles with O(! log n) update time, where
! is the maximum size of an independent set of rectangles stabbed by any horizontal line. We
have implemented our algorithms and report the results of an experimental comparison exploring
the trade-off between solution quality and update time for synthetic and real-world map labeling
instances.

http://dx.doi.org/10.4230/LIPIcs.ESA.2020.19

https://publik.tuwien.ac.at/files/publik_292476.pdf