Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Two-Sided Boundary Labeling with Adjacent Sides
verfasst von : Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter, Marcus Schaefer, André Schulz, Alexander Wolff
Erschienen in: Algorithms and Data Structures
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the
Boundary Labeling
problem, we are given a set of
n
points, referred to as
sites
, inside an axis-parallel rectangle
R
, and a set of
n
pairwise disjoint rectangular labels that are attached to
R
from the outside. The task is to connect the sites to the labels by non-intersecting rectilinear paths, so-called
leaders
, with at most one bend.
In this paper, we study the problem
Two-Sided Boundary Labeling with Adjacent Sides
, where labels lie on two adjacent sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases that labels lie on one side or on two opposite sides of
R
(where a crossing-free solution always exists). For the more difficult case where labels lie on adjacent sides, we show how to compute crossing-free leader layouts that maximize the number of labeled points or minimize the total leader length.