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 Multi-Sided Boundary Labeling
problem, with labels lying on at least two 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
in which labels lie on one side or on two opposite
sides of $R$ (here a crossing-free solution always
exists). The case where labels may lie on adjacent
sides is more difficult. We present efficient
algorithms for testing the existence of a
crossing-free leader layout that labels all sites
and also for maximizing the number of labeled sites
in a crossing-free leader layout. For two-sided
boundary labeling with adjacent sides, we further
show how to minimize the total leader length in a
crossing-free layout.
%0 Journal Article
%1 knrssw-tsblas-Algorithmica16
%A Kindermann, Philipp
%A Niedermann, Benjamin
%A Rutter, Ignaz
%A Schaefer, Marcus
%A Schulz, André
%A Wolff, Alexander
%D 2016
%J Algorithmica
%K boundary_labeling dynamic_programming multi-sided_case myown
%N 1
%P 225--258
%R 10.1007/s00453-015-0028-4
%T Multi-Sided Boundary Labeling
%V 76
%X 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 Multi-Sided Boundary Labeling
problem, with labels lying on at least two 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
in which labels lie on one side or on two opposite
sides of $R$ (here a crossing-free solution always
exists). The case where labels may lie on adjacent
sides is more difficult. We present efficient
algorithms for testing the existence of a
crossing-free leader layout that labels all sites
and also for maximizing the number of labeled sites
in a crossing-free leader layout. For two-sided
boundary labeling with adjacent sides, we further
show how to minimize the total leader length in a
crossing-free layout.
@article{knrssw-tsblas-Algorithmica16,
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
leaders, with at most one bend. In this paper, we
study the \emph{Multi-Sided Boundary Labeling}
problem, with labels lying on at least two 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
in which labels lie on one side or on two opposite
sides of $R$ (here a crossing-free solution always
exists). The case where labels may lie on adjacent
sides is more difficult. We present efficient
algorithms for testing the existence of a
crossing-free leader layout that labels all sites
and also for maximizing the number of labeled sites
in a crossing-free leader layout. For two-sided
boundary labeling with adjacent sides, we further
show how to minimize the total leader length in a
crossing-free layout.},
added-at = {2024-04-29T21:12:31.000+0200},
arxiv = {http://arxiv.org/abs/1305.0750},
author = {Kindermann, Philipp and Niedermann, Benjamin and Rutter, Ignaz and Schaefer, Marcus and Schulz, André and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/23f53f14e4e6c4748795c43c75bc06a33/awolff},
doi = {10.1007/s00453-015-0028-4},
interhash = {0616edf5e7d6055787d71966e80bdfe3},
intrahash = {3f53f14e4e6c4748795c43c75bc06a33},
journal = {Algorithmica},
keywords = {boundary_labeling dynamic_programming multi-sided_case myown},
number = 1,
pages = {225--258},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/knrssw-tsblas-Algorithmica16.pdf},
timestamp = {2024-04-29T21:12:31.000+0200},
title = {Multi-Sided Boundary Labeling},
volume = 76,
year = 2016
}