Please use this identifier to cite or link to this item:
http://doi.org/10.25358/openscience-5792| Authors: | Althaus, Ernst Rauterberg, Felix Ziegler, Sarah |
| Title: | Computing Euclidean Steiner trees over segments |
| Online publication date: | 11-May-2021 |
| Year of first publication: | 2020 |
| Language: | english |
| 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. |
| DDC: | 004 Informatik 004 Data processing 510 Mathematik 510 Mathematics |
| Institution: | Johannes Gutenberg-Universität Mainz |
| Department: | FB 08 Physik, Mathematik u. Informatik |
| Place: | Mainz |
| ROR: | https://ror.org/023b0x485 |
| DOI: | http://doi.org/10.25358/openscience-5792 |
| Version: | Published version |
| Publication type: | Zeitschriftenaufsatz |
| Document type specification: | Scientific article |
| License: | CC BY |
| Information on rights of use: | https://creativecommons.org/licenses/by/4.0/ |
| Journal: | EURO journal on computational optimization 8 |
| Pages or article number: | 309 325 |
| Publisher: | Springer |
| Publisher place: | Berlin u.a. |
| Issue date: | 2020 |
| ISSN: | 2192-4414 |
| Publisher URL: | https://doi.org/10.1007/s13675-020-00125-w |
| Publisher DOI: | 10.1007/s13675-020-00125-w |
| Appears in collections: | JGU-Publikationen |
Files in This Item:
| File | Description | Size | Format | ||
|---|---|---|---|---|---|
 | althaus_ernst-computing_eucl-20210421124547767.pdf | 1.04 MB | Adobe PDF | View/Open |