nach oben

Journal of Combinatorial Optimization

Erschienen in:

21.09.2021

On the restricted k-Steiner tree problem

verfasst von: Prosenjit Bose, Anthony D’Angelo, Stephane Durocher

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel On the enumeration of minimal non-pairwise compatibility graphs

Nächster Artikel Measuring the influence and amplification of users on social network with unsupervised behaviors learning and efficient interaction-based knowledge graph

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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.

Georgakopoulos and Papadimitriou (1987) refer to the overlaid OVD as Overlaid Oriented Dirichlet Cells.

This follows from the zone theorem (de Berg et al. 2008; Chazelle et al. 1985; Edelsbrunner et al. 1986, 1993).

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\})\).

A similar result was shown in (Monma and Suri 1992, Lemma 4.1, pg. 277).

A simple cycle is a cycle where no vertex is repeated except the first vertex.

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.

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.

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.

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).

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).

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.

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

Booth RS, Weng JF (1992) Steiner minimal trees for a class of zigzag lines. Algorithmica 7(2 & 3):231–246MathSciNetCrossRef

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, Thomas DA, Weng JF (2000) On the complexity of the Steiner problem. J Comb Optim 4(2):187–195MathSciNetCrossRef

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

Chen G, Zhang G (2000) A constrained minimum spanning tree problem. Comput Oper Res 27(9):867–875MathSciNetCrossRef

Cheriton DR, Tarjan RE (1976) Finding minimum spanning trees. SIAM J Comput 5(4):724–742MathSciNetCrossRef

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

Du D, Hwang F, Weng J (1983) Steiner minimal trees on zig-zag lines. Trans Am Math Soc 278(1):149–156MathSciNetCrossRef

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

Gilbert E, Pollak H (1968) Steiner minimal trees. SIAM J Appl Math 16(1):1–29MathSciNetCrossRef

Goodman JE, O’Rourke J, Tóth CD (eds.) (2017) Handbook of Discrete and Computational Geometry, Third Edition. Chapman and Hall/CRC Press

Harel D, Tarjan RE (1984) Fast algorithms for finding nearest common ancestors. SIAM J Comput 13(2):338–355MathSciNetCrossRef

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

Monma CL, Suri S (1992) Transitions in geometric minimum spanning trees. Discret Comput Geom 8:265–293MathSciNetCrossRef

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

Winter P, Zachariasen M, Nielsen J (2002) Short trees in polygons. Discret Appl Math 118(1–2):55–72MathSciNetCrossRef

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

Titel: On the restricted k-Steiner tree problem
verfasst von: Prosenjit Bose
Anthony D’Angelo
Stephane Durocher
Publikationsdatum: 21.09.2021
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2022
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-021-00808-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2022

Approximation approach for robust vessel fleet deployment problem with ambiguous demands

A tight approximation algorithm for problem

Truthful mechanism design for bin packing with applications on cloud computing

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

On the enumeration of minimal non-pairwise compatibility graphs

Parameterized algorithms and complexity for the traveling purchaser problem and its variants

Premium Partner