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

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