Generalized Hanan Grids for Geometric Steiner Trees in Uniform Orientation Metrics

Matthias Müller-Hannemann ()
Additional contact information
Matthias Müller-Hannemann: Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik

A chapter in Gems of Combinatorial Optimization and Graph Algorithms, 2015, pp 37-47 from Springer

Abstract: Abstract Given a finite set of points in some metric space, a fundamental task is to find a shortest network interconnecting all of them. The network may include additional points, so-called Steiner points, which can be inserted at arbitrary places in order to minimize the total length with respect to the given metric. This paper focuses on uniform orientation metrics where the edges of the network are restricted to lie within a given set of legal directions. We here review the crucial insight that many versions of geometric network design problems can be reduced to the Steiner tree problem in finite graphs, namely the Hanan grid or its extensions.

Keywords: Steiner Tree; Steiner Point; Steiner Tree Problem; Steiner Minimum Tree; Rectilinear Polygon (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-24971-1_4

Ordering information: This item can be ordered from
http://www.springer.com/9783319249711

DOI: 10.1007/978-3-319-24971-1_4

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().