BibSonomy publications for /http://www.bibsonomy.org/BibSonomy RSS feed for /2014-10-20T23:15:35+02:00Three Rules Suffice for Good Label Placementhttp://www.bibsonomy.org/bibtex/25000db379aefd9078b8dc96e7cd05d2b/awolffawolff2014-10-20T23:07:08+02:00cartography csuniwue experimental_comparison label-placement_algorithms map_labeling <span class="authorEditorList"><a href="/author/Wagner">Frank Wagner</a>, <a href="/author/Wolff">Alexander Wolff</a>, <a href="/author/Kapoor">Vikas Kapoor</a>, and <a href="/author/Strijk">Tycho Strijk</a>. </span><em>Algorithmica</em> <em>30(2):334--349</em> (<em>2001</em>)Mon Oct 20 23:07:08 CEST 2014Algorithmica2334--349Three Rules Suffice for Good Label Placement302001cartography csuniwue experimental_comparison label-placement_algorithms map_labeling 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.A Practical Map Labeling Algorithmhttp://www.bibsonomy.org/bibtex/273e0b488296f823885052aff9182c053/awolffawolff2014-10-20T23:07:08+02:00NP-hardness approximation_algorithm computational_cartography csuniwue heuristic map_labeling packing_problem <span class="authorEditorList"><a href="/author/Wagner">Frank Wagner</a>, and <a href="/author/Wolff">Alexander Wolff</a>. </span><em>Computational Geometry: Theory and Applications</em> <em>7(5--6):387--404</em> (<em>1997</em>)Mon Oct 20 23:07:08 CEST 2014Computational Geometry: Theory and Applications5--6387--404A Practical Map Labeling Algorithm71997NP-hardness approximation_algorithm computational_cartography csuniwue heuristic map_labeling packing_problem The Map Labeling problem is a classical problem of
cartography. There is a theoretically optimal
approximation algorithm $A$. Unfortunately $A$ is
useless in practice as it typically produces results
that are intolerably far off the optimal size. On
the other hand there are heuristics with good
practical results. In this paper we present an
algorithm $B$ that (a) guarantees the optimal
approximation quality and runtime behaviour of $A$,
and (b) yields results significantly closer to the
optimum than the best heuristic known so far. The
sample data used in the experimental evaluation
consists of three different classes of random
problems and a selection of problems arising in the
production of groundwater quality maps by the
authorities of the City of Munich.Map Labeling Heuristics: Provably Good and
Practically Usefulhttp://www.bibsonomy.org/bibtex/206ce16139137e8304dcc18d8ae5a0070/awolffawolff2014-10-20T23:07:08+02:00csuniwue <span class="authorEditorList"><a href="/author/Wagner">Frank Wagner</a>, and <a href="/author/Wolff">Alexander Wolff</a>. </span><em>Technical report, </em><em>B 95-04. </em><em>Institut für Informatik, Freie Universität
Berlin, </em>(<em>April 1995</em>)Mon Oct 20 23:07:08 CEST 2014aprB 95-04Map Labeling Heuristics: Provably Good and
Practically UsefulTechnical report1995csuniwue Map Labeling Heuristics: Provably Good and
Practically Usefulhttp://www.bibsonomy.org/bibtex/237dec387df5d4cb2dc8a30eab106ccf7/awolffawolff2014-10-20T23:07:08+02:00approximation_algorithm csuniwue experimental_comparison map_labeling <span class="authorEditorList"><a href="/author/Wagner">Frank Wagner</a>, and <a href="/author/Wolff">Alexander Wolff</a>. </span><em>Proc. 11th Annu. ACM Sympos. Comput. Geom.
SoCG'95, </em><em>page 109--118. </em>(<em>1995</em>)Mon Oct 20 23:07:08 CEST 2014Proc. 11th Annu. ACM Sympos. Comput. Geom.
(SoCG'95)109--118Map Labeling Heuristics: Provably Good and
Practically Useful1995approximation_algorithm csuniwue experimental_comparison map_labeling Guest Editors' Foreword Special Issue of Selected
Papers from the 21st Int. Symp. Graph Drawinghttp://www.bibsonomy.org/bibtex/2753aec2ecbfdb18762d40498718fd129/awolffawolff2014-10-20T23:07:08+02:00csuniwue <span class="authorEditorList"><a href="/author/Wismath">Stephen Wismath</a>, and <a href="/author/Wolff">Alexander Wolff</a>. </span><em>Journal of Graph Algorithms \& Applications</em> <em>18(2):174--175</em> (<em>2014</em>)Mon Oct 20 23:07:08 CEST 2014Journal of Graph Algorithms \& Applications2174--175Guest Editors' Foreword (Special Issue of Selected
Papers from the 21st Int. Symp. Graph Drawing)182014csuniwue