KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
§
Verlagsausgabe
DOI: 10.5445/IR/1000083097
Veröffentlicht am 28.05.2018
Originalveröffentlichung
DOI: 10.20382/jocg.v7i1a15

Consistent labeling of rotating maps

Gemsa, Andreas; Nöllenburg, Martin; Rutter, Ignaz

Abstract:
Dynamic maps that allow continuous map rotations, for example, on mobile
devices, encounter new geometric labeling issues unseen in static maps before. We study the
following dynamic map labeling problem: The input is an abstract map consisting of a set P
of points in the plane with attached horizontally aligned rectangular labels. While the map
with the point set P is rotated, all labels remain horizontally aligned. We are interested in
a consistent labeling of P under rotation, i.e., an assignment of a single (possibly empty)
active interval of angles for each label that determines its visibility under rotations such
that visible labels neither intersect each other (soft conflicts) nor occlude points in P at any
rotation angle (hard conflicts). Our goal is to find a consistent labeling that maximizes the
number of visible labels integrated over all rotation angles.
We first introduce a general model for labeling rotating maps and derive basic geometric
properties of consistent solutions. We show NP-hardness of the above optimization
problem even for unit-square labels. We then present a constant-factor approximation fo ... mehr


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Jahr 2016
Sprache Englisch
Identifikator ISSN: 1920-180X
URN: urn:nbn:de:swb:90-830972
KITopen ID: 1000083097
Erschienen in Journal of computational geometry
Band 7
Heft 1
Seiten 308-331
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page