26. November – 01. Dezember 2006, Dagstuhl Seminar 06481
Geometric Networks and Metric Space Embeddings
Joachim Gudmundsson (NICTA – Sydney, AU)
Rolf Klein (Universität Bonn, DE)
Giri Narasimhan (Florida International University – Miami, US)
Michiel Smid (Carleton University – Ottawa, CA)
Alexander Wolff (KIT – Karlsruher Institut für Technologie, DE)
Auskunft zu diesem Dagstuhl Seminar erteilt
This seminar has, for the first time, brought together scientists from three different communities who are actively working on distance problems.
Geometric networks are at the core of any model for the flows of goods, traffic or information. They also play an important role in telecommunication, VLSI design, motion planning (robotics), pattern matching, data compression, bio-informatics (gene analysis), and sensor networks. One is interested in spanners with other useful properties like a linear number of edges, small total edge length, small node degree, few crossings, or small link diameter. Apart from these applications, geometric spanners have had great impact on the construction of approximation algorithms, e.g., for the traveling salesman problem. Such problems have been investigated by researchers in computational geometry and combinatorial optimization. For storage, visualization, and retrieval of high-dimensional data the question of reducing the dimension plays a crucial rôle. This has led to a theory of metric space embeddings that was most actively developed by scientists in discrete geometry and mathematics. Finally, mathematicians and biologists are interested in metric properties and the visualization of phylogenetic networks.
For each of the three fields, a survey talk was given at the seminar (Michiel Smid: Geometric Spanner Networks, Anupam Gupta: Metric Embeddings, Daniel Huson: Application of Phylogenetic Networks in Evolutionary Studies). In addition, twenty-two regular talks were given by the seminar participants. They encouraged a fruitful exchange of ideas and stimulated interesting discussions and co-operations.
The range of interesting topics that came up during this seminar is well documented by the list of problems that were discussed in two open-problem sessions and attacked by small groups of participants in the corresponding problem-solving sessions.
Related Dagstuhl Seminar
- Data Structures
- Geometric networks
- Metric space embeddings