KIT | KIT-Bibliothek | Impressum
Open Access Logo
§
Volltext
URN: urn:nbn:de:swb:90-635632
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 for this pro ... mehr


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Jahr 2016
Sprache Englisch
Identifikator ISSN: 1920-180X
KITopen ID: 1000063563
HGF-Programm 37.06.01; LK 01
Erschienen in Journal of computational geometry
Band 7
Heft 1
Seiten 308-331
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page