Three Rules Suffice for Good Label Placement | BibSonomy

Three Rules Suffice for Good Label Placement
, , , и .
Algorithmica 30 (2): 334--349 (2001)

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. \par 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.
  • @awolff
  • @dblp
  • @fink
К этой публикации ещё не было создано рецензий.

распределение оценок
средняя оценка пользователей0,0 из 5.0 на основе 0 рецензий
    Пожалуйста, войдите в систему, чтобы принять участие в дискуссии (добавить собственные рецензию, или комментарий)