Veröffentlichung

Titel:

Two-Sided Boundary Labeling with Adjacent Sides

AutorInnen:

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

Kategorie:

Workshopbeiträge

erschienen in:

Proceedings of the 29th European Workshop on Computational Geometry (EuroCG'13), pp. 233-236, Abstract

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.

BibTeX-Eintrag:

@InProceedings{knrssw-tsbla-eurocg13, 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 29th European Workshop on Computational Geometry (EuroCG'13)}, Year = {2013}, Editor = {S{\'a}ndor Fekete}, Note = {Abstract}, Pages = {233--236}, Publisher = {Braunschweig}, 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.} }