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

Created from the Publication Database of the Vienna University of Technology.