Journal article
Geometric conditions for Euclidean Steiner trees in R-d
Computational geometry : theory and applications, Vol.46(5), pp.520-531
07/01/2013
DOI: 10.1016/j.comgeo.2011.11.007
Abstract
We present geometric conditions that can be used to restrict or eliminate candidate topologies for Euclidean Steiner minimal trees in R-d, d >= 2. Our emphasis is on conditions that are not restricted to the planar case (d = 2). For trees with a Steiner topology we give restrictions on terminal-Steiner connections that are based on the Voronoi diagram associated with the set of terminal nodes. We then describe more restrictive conditions for trees with a full Steiner topology and show how these conditions can be used to improve implicit enumeration algorithms for finding Euclidean Steiner minimal trees with d > 2. (C) 2011 Elsevier B.V. All rights reserved.
Details
- Title: Subtitle
- Geometric conditions for Euclidean Steiner trees in R-d
- Creators
- Jon W. Van Laarhoven - Daniel H. Wagner Associates (United States)Kurt M. Anstreicher - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Computational geometry : theory and applications, Vol.46(5), pp.520-531
- DOI
- 10.1016/j.comgeo.2011.11.007
- ISSN
- 0925-7721
- Publisher
- Elsevier
- Number of pages
- 12
- Grant note
- DMS-0602242 / University of Iowa Department of Mathematics NSF VIGRE
- Language
- English
- Date published
- 07/01/2013
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380531102771
Metrics
13 Record Views