Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Combinatorial Optimization
Published in: Journal of Combinatorial Optimization 4/2022

21-09-2021

On the restricted k-Steiner tree problem

Authors: Prosenjit Bose, Anthony D’Angelo, Stephane Durocher

Published in: Journal of Combinatorial Optimization | Issue 4/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Given a set P of n points in \(\mathbb {R}^2\) and an input line \(\gamma \) in \(\mathbb {R}^2\), we present an algorithm that runs in optimal \(\varTheta (n\log n)\) time and \(\varTheta (n)\) space to solve a restricted version of the 1-Steiner tree problem. Our algorithm returns a minimum-weight tree interconnecting P using at most one Steiner point \(s \in \gamma \), where edges are weighted by the Euclidean distance between their endpoints. We then extend the result to j input lines. Following this, we show how the algorithm of Brazil et al. in Algorithmica 71(1):66–86 that solves the k-Steiner tree problem in \(\mathbb {R}^2\) in \(O(n^{2k})\) time can be adapted to our setting. For \(k>1\), restricting the (at most) k Steiner points to lie on an input line, the runtime becomes \(O(n^{k})\). Next we show how the results of Brazil et al. in Algorithmica 71(1):66–86 allow us to maintain the same time and space bounds while extending to some non-Euclidean norms and different tree cost functions. Lastly, we extend the result to j input curves.
previous article On the enumeration of minimal non-pairwise compatibility graphs
next article Measuring the influence and amplification of users on social network with unsupervised behaviors learning and efficient interaction-based knowledge graph

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
This means the length of their tree is at most 1.214 times the length of the optimal solution. Here they take advantage of the result of Chung and Graham (1985) showing that the MST is a 1.214-approximation (to three decimals) of the MStT.
 
2
Georgakopoulos and Papadimitriou (1987) refer to the overlaid OVD as Overlaid Oriented Dirichlet Cells.
 
3
This follows from the zone theorem (de Berg et al. 2008; Chazelle et al. 1985; Edelsbrunner et al. 1986, 1993).
 
4
In other words, each \(u \in I\) has the same constant-sized set of fixed candidate sub-topologies incident to u that could be the result of \({\text {MST}}(P \cup \{u\})\).
 
5
A similar result was shown in (Monma and Suri 1992, Lemma 4.1, pg. 277).
 
6
A simple cycle is a cycle where no vertex is repeated except the first vertex.
 
7
As summarized in the survey by Brazil and Zachariasen (2015), for the bottleneck k-Steiner tree problem, i.e., the k-Steiner tree problem where the goal is to minimize the length of the longest edge of the resultant tree for the given norm, Bae et al. (2010) presented a \(\varTheta (n\log n)\)-time and \(O(n^2)\)-time algorithm for \(k=1\) and \(k=2\) respectively in the Euclidean plane, while Bae et al. (2011) presented an \(O((k^{5k}2^{O(k)})(n^k + n\log n))\)-time algorithm for the \(L_p\) metric for a fixed rational p with \(1<p<\infty \), as well as an \(O(n\log n)\)-time algorithm for \(k=1\) in the \(L_1\) metric, and an \(O((7k+1)^{7k-1}k^4\cdot n\log ^2 n)\)-time algorithm for the \(L_1\) and \(L_{\infty }\) metrics.
 
8
In the pseudocode for this algorithm in Brazil et al. (2015) there is a typo saying this is \(O(n\log n)\) time, but the correct time bound, \(O(n^2)\), is stated in other parts of the paper.
 
9
Note that since Steiner points may lie on different input lines, we cannot simply run the basic algorithm j times as was done in Corollary 1.
 
10
For the reader trying to get a better understanding of the material from Brazil et al. (2015), the same material is presented a bit differently in the survey by Brazil and Zachariasen (2015).
 
11
We can even allow o to lie on C, but this means some points are infinitely far from o (Brazil and Zachariasen 2015, §4.3.1 pg. 258).
 
12
Once again, we assume that, using the x-monotone functions into which we have decomposed \(\gamma (x)\) in the equations outlined in the previous sections, the derivatives and roots required can be computed in constant time and space.
 
Literature
Bae SW, Choi S, Lee C, Tanigawa S (2011) Exact algorithms for the bottleneck Steiner tree problem. Algorithmica 61(4):924–948MathSciNetCrossRef
Bae SW, Lee C, Choi S (2010) On exact solutions to the Euclidean bottleneck Steiner tree problem. Inf Process Lett 110(16):672–678MathSciNetCrossRef
Bender MA, Farach-Colton M (2000) The LCA problem revisited. In: LATIN, Lecture Notes in Computer Science, vol. 1776, pp. 88–94. Springer
de Berg M, Cheong O, van Kreveld MJ, Overmars MH (2008) Computational geometry: algorithms and applications, 3rd edn. Springer, New YorkCrossRef
Bose P, D’Angelo A, Durocher S (2020) On the restricted 1-Steiner tree problem. In: COCOON, Lecture Notes in Computer Science, vol. 12273, pp. 448–459. Springer
Bose P, Maheshwari A, Narasimhan G, Smid MHM, Zeh N (2004) Approximating geometric bottleneck shortest paths. Comput Geom 29(3):233–249MathSciNetCrossRef
Brazil M, Cole T, Rubinstein JH, Thomas DA, Weng JF, Wormald NC (1996) Minimal Steiner trees for \(2^{{ k}} \times 2^{{ k}}\) square lattices. J Comb Theory Ser A 73(1):91–110CrossRef
Brazil M, Graham RL, Thomas DA, Zachariasen M (2014) On the history of the Euclidean Steiner tree problem. Arch. History Exact Sci. 68(3):327–354MathSciNetCrossRef
Brazil M, Ras CJ, Swanepoel KJ, Thomas DA (2015) Generalised k-Steiner tree problems in normed planes. Algorithmica 71(1):66–86MathSciNetCrossRef
Brazil M, Rubinstein JH, Thomas DA, Weng JF, Wormald NC (1997a) Full minimal Steiner trees on lattice sets. J Comb Theory Ser A 78(1):51–91MathSciNetCrossRef
Brazil M, Rubinstein JH, Thomas DA, Weng JF, Wormald NC (1997b) Minimal Steiner trees for rectangular arrays of lattice points. J Comb Theory Ser A 79(2):181–208MathSciNetCrossRef
Brazil M, Zachariasen M (2015) Optimal interconnection trees in the plane: theory, algorithms and applications, vol 29. Springer, New YorkMATH
Chang M, Huang N, Tang CY (1990) An optimal algorithm for constructing oriented Voronoi diagrams and geographic neighborhood graphs. Inf Process Lett 35(5):255–260MathSciNetCrossRef
Chazelle B, Guibas LJ, Lee DT (1985) The power of geometric duality. BIT Comput Sci Sect 25(1):76–90MathSciNetMATH
Chew LP, Drysdale III RL (1985) Voronoi diagrams based on convex distance functions. In: Symposium on Computational Geometry, pp. 235–244. ACM
Chung FRK, Graham RL (1978) Steiner trees for ladders. Annal Discrete Math 2:173–200
Chung FRK, Graham RL (1985) A new bound for Euclidean Steiner minimal trees. Annal New York Acad Sci 440(1):328–346MathSciNetCrossRef
Edelsbrunner H, O’Rourke J, Seidel R (1986) Constructing arrangements of lines and hyperplanes with applications. SIAM J Comput 15(2):341–363
Edelsbrunner H, Seidel R, Sharir M (1993) On the zone theorem for hyperplane arrangements. SIAM J Comput 22(2):418–429MathSciNetCrossRef
Garey MR, Graham RL, Johnson DS (1977) The complexity of computing Steiner minimal trees. SIAM J Appl Math 32(4):835–859MathSciNetCrossRef
Georgakopoulos GK, Papadimitriou CH (1987) The 1-Steiner tree problem. J Algorithms 8(1):122–130
Goodman JE, O’Rourke J, Tóth CD (eds.) (2017) Handbook of Discrete and Computational Geometry, Third Edition. Chapman and Hall/CRC Press
Holby J (2017) Variations on the Euclidean Steiner tree problem and algorithms. Rose-Hulman Undergrad Math J 18(1):7MathSciNetMATH
Li J, Liu S, Lichen J, Wang W, Zheng Y (2020) Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem. J Comb Optim 39(2):492–508MathSciNetCrossRef
Preparata FP, Shamos MI (1985) Computational Geometry - An Introduction. Texts and Monographs in Computer Science. Springer
Rubinstein JH, Thomas DA, Weng JF (1992) Degree-five Steiner points cannot reduce network costs for planar sets. Networks 22(6):531–537MathSciNetCrossRef
Rubinstein JH, Thomas DA, Wormald NC (1997) Steiner trees for terminals constrained to curves. SIAM J Discret Math 10(1):1–17MathSciNetCrossRef
Schieber B, Vishkin U (1988) On finding lowest common ancestors: Simplification and parallelization. SIAM J Comput 17(6):1253–1262MathSciNetCrossRef
Vanek J, Galicia JAG, Benes B (2014) Clever support: efficient support structure generation for digital fabrication. Comput Graph Forum 33(5):117–125CrossRef
Winter P (1993) Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs. Discrete Appl. Math. 47(2):187–206MathSciNetCrossRef
Winter P (1995a) Euclidean Steiner minimum trees for 3 terminals in a simple polygon. In: Proceedings of the Seventh Canadian Conference on Computational Geometry, Univ. Laval, Quebec, Canada, pp. 247–255
Winter P (1995b) Steiner minimum trees in simple polygons. DIMACS Technical Report 95–43
Zachariasen M, Winter P (1999) Obstacle-avoiding Euclidean Steiner trees in the plane: An exact algorithm. In: ALENEX, Lecture Notes in Computer Science, vol. 1619, pp. 282–295. Springer
Metadata
Title
On the restricted k-Steiner tree problem
Authors
Prosenjit Bose
Anthony D’Angelo
Stephane Durocher
Publication date
21-09-2021
Publisher
Springer US
Published in
Journal of Combinatorial Optimization / Issue 4/2022
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-021-00808-z

Other articles of this Issue 4/2022

Journal of Combinatorial Optimization 4/2022 Go to the issue

OriginalPaper

Optimal frequency assignment and planar list L(2, 1)-labeling

OriginalPaper

Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane

OriginalPaper

HM-EIICT: Fairness-aware link prediction in complex networks using community information

OriginalPaper

A new lower bound for the eternal vertex cover number of graphs

OriginalPaper

On zero-error codes produced by greedy algorithms

OriginalPaper

On the enumeration of minimal non-pairwise compatibility graphs

Premium Partner

    Image Credits