Three Rules Suffice for Good Label Placement |
| |
Authors: | F Wagner A Wolff V Kapoor T Strijk |
| |
Affiliation: | Institut für Informatik, Fachbereich Mathematik und Informatik, Freie Universit?t Berlin, Takustra? e 9, D-14195 Berlin, Germany. \{wagner$|$kapoor\}@inf.fu-berlin.de., DE Institut für Mathematik und Informatik, Ernst-Moritz-Arndt-Universit?t Greifswald, Jahnstra? e 15a, D-17487 Greifswald, Germany. awolff@mail.uni-greifswald.de., DE Department of Computer Science, Utrecht University, 3508 TB Utrecht,The Netherlands. tycho@cs.uu.nl., NL
|
| |
Abstract: | The general label-placement problem consists in labeling a set of features (points, lines, regions) given a set of candidates
(rectangles, circles, ellipses, irregularly shaped labels) for each feature. The problem arises when annotating classical
cartographical maps, diagrams, or graph drawings. The size of a labeling is the number of features that receive pairwise nonintersecting
candidates. Finding an optimal solution, i.e., a labeling of maximum size, is NP-hard.
We present an approach to attack the problem in its full generality. The key idea is to separate the geometric part from
the combinatorial part of the problem. The latter is captured by the conflict graph of the candidates. We present a set of
rules that simplify the conflict graph without reducing the size of an optimal solution. Combining the application of these
rules with a simple heuristic yields near-optimal solutions.
We study competing algorithms and do a thorough empirical comparison on point-labeling data. The new algorithm we suggest
is fast, simple, and effective.
Received December 21, 1998; revised October 13, 1999. |
| |
Keywords: | , Computational geometry, Cartography, Label-placement algorithms, Experimental comparison, |
本文献已被 SpringerLink 等数据库收录! |
|