Computing Euclidean Steiner trees over segments
- PDF / 1,078,529 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 98 Downloads / 194 Views
Computing Euclidean Steiner trees over segments Ernst Althaus1
· Felix Rauterberg2 · Sarah Ziegler1
Received: 5 November 2019 / Accepted: 18 May 2020 © The Author(s) 2020
Abstract In the classical Euclidean Steiner minimum tree (SMT) problem, we are given a set of points in the Euclidean plane and we are supposed to find the minimum length tree that connects all these points, allowing the addition of arbitrary additional points. We investigate the variant of the problem where the input is a set of line segments. We allow these segments to have length 0, i.e., they are points and hence we generalize the classical problem. Furthermore, they are allowed to intersect such that we can model polygonal input. As in the GeoSteiner approach of Juhl et al. (Math Program Comput 10(2):487–532, 2018) for the classical case, we use a two-phase approach where we construct a superset of so-called full components of an SMT in the first phase. We prove a structural theorem for these full components, which allows us to use almost the same GeoSteiner algorithm as in the classical SMT problem. The second phase, the selection of a minimal cost subset of constructed full components, is exactly the same as in GeoSteiner approach. Finally, we report some experimental results that show that our approach is more efficient than the approximate solution that is obtained by sampling the segments. Keywords Euclidean Steiner minimum tree · Exact algorithm · Structural theorem Mathematics Subject Classification Computational geometry
B
Ernst Althaus [email protected] Felix Rauterberg [email protected] Sarah Ziegler [email protected]
1
Johannes Gutenberg Universität Mainz, Mainz, Germany
2
Technische Universität Darmstadt, Darmstadt, Germany
123
E. Althaus et al.
1 Introduction We are interested in the following problem: Given a set of segments in the Euclidean plane, connect these segments by additional segments of minimum total length, where we are allowed to use additional points, called the Steiner points. We will call this problem the Euclidean Steiner minimum tree (SMT) problem over segments and formally define it later (see Fig. 1 for an example). We allow these segments to have length 0, i.e., they are points and hence we generalize the classical problem. Furthermore, they are allowed to intersect such that we can model polygonal input. The problem at hand was motivated by the need of a geography student who wanted to connect a set of highly interconnected areas, described as polygons in a plane. The situation that parts of the network that is to be constructed is already existent can also appear in other applications, e.g., when constructing an electrical network or some pipelines. In the classical Euclidean Steiner minimum tree problem, the input is just a set of points called the terminals. It has many applications and has been widely investigated since its introduction. The most efficient publicly available implementation is the GeoSteiner package of Juhl et al. (2018), which implements a two-phase approach fi
Data Loading...
