Veröffentlichung

Titel:

Two-Sided Boundary Labeling with Adjacent Sides

AutorInnen:

Philipp Kindermann
Benjamin Niedermann
Ignaz Rutter
Marcus Schaefer
André Schulz
Alexander Wolff

Kategorie:

Konferenzbandbeiträge

erschienen in:

Proceedings of the 13th International Symposium on Algorithms and Data Structures (WADS'13), pp. 463-474

Abstract:

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.

Download:

Proceeding Website

BibTeX-Eintrag:

@InProceedings{knrssw-tsbla-wads13, Title = {Two-Sided Boundary Labeling with Adjacent Sides}, Author = {Philipp Kindermann and Benjamin Niedermann and Ignaz Rutter and Marcus Schaefer and Andr{\'{e}} Schulz and Alexander Wolff}, Booktitle = {Proceedings of the 13th International Symposium on Algorithms and Data Structures (WADS'13)}, Year = {2013}, Editor = {Frank Dehne and Roberto Solis{-}Oba and J{\"{o}}rg{-}R{\"{u}}diger Sack}, Pages = {463--474}, Publisher = {Springer}, Series = {Lecture Notes in Computer Science}, Volume = {8037}, Abstract = {In the \emph{Boundary Labeling} problem, we are given a set of $n$ points, referred to as \emph{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 \emph{leaders}, with at most one bend. In this paper, we study the problem \emph{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.}, Doi = {10.1007/978-3-642-40104-6_40} }