Angle-restricted Steiner arborescences for flow map layout

Onderzoeksoutput: Bijdrage aan congresAbstract

88 Downloads (Pure)


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.
Originele taal-2Engels
StatusGepubliceerd - 2011
Evenement27th European Workshop on Computational Geometry (EuroCG 2011) - Morschach, Zwitserland
Duur: 28 mrt 201130 mrt 2011
Congresnummer: 27


Workshop27th European Workshop on Computational Geometry (EuroCG 2011)
Verkorte titelEuroCG

Vingerafdruk Duik in de onderzoeksthema's van 'Angle-restricted Steiner arborescences for flow map layout'. Samen vormen ze een unieke vingerafdruk.

Citeer dit