Angle-restricted Steiner arborescences for flow map layout
| Autor: | Buchin, K., Speckmann, B., Verbeek, K.A.B., Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. |
|---|---|
| Přispěvatelé: | Algorithms, Applied Geometric Algorithms |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Arborescence General Computer Science Flux 0102 computer and information sciences 02 engineering and technology Steiner tree problem 01 natural sciences Combinatorics symbols.namesake Planar Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) Flow map Logarithmic spiral Spiral Mathematics Discrete mathematics Applied Mathematics 020207 software engineering Computational geometry Tree (graph theory) Computer Science Applications Monotone polygon 010201 computation theory & mathematics symbols Computer Science - Computational Geometry |
| Zdroj: | Algorithms and Computation ISBN: 9783642255908 ISAAC Algorithmica, 72(2), 656-685. Springer Algorithms and Computation (22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings), 250-259 STARTPAGE=250;ENDPAGE=259;TITLE=Algorithms and Computation (22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings) ISSUE=27;STARTPAGE=35;ENDPAGE=38;TITLE=27th European Workshop on Computational Geometry (EuroCG 2011) |
| ISSN: | 0178-4617 |
| Popis: | Flow maps visualize the movement of objects between places. One or more sources are connected to several targets by arcs whose thickness corresponds to the amount of flow between a source and a target. Flow maps reduce visual clutter by merging (bundling) lines smoothly and by avoiding self-intersections. We present algorithms that compute crossing-free flows of high visual quality. To this end we introduce a new variant of the geometric Steiner arborescence problem. The goal is to connect the targets to a source with a tree of minimal length whose arcs obey a certain restriction on the angle they form with the source. Such an angle-restricted Steiner arborescence, or simply ow tree, naturally induces a clustering on the targets and smoothly bundles arcs. We study the properties of optimal flow trees and show that they consist of logarithmic spirals and straight lines. Computing optimal flow trees is NP-hard. Hence we consider a variant of flow trees which uses only logarithmic spirals, so called spiral trees. Spiral trees approximate flow trees within a factor depending on the angle restriction. Computing optimal spiral trees remains NP-hard. We present an efficient 2-approximation for spiral trees, which can be extended to avoid certain types of obstacles. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink