## 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*.

This is a preview of subscription content, access via your institution.

## Notes

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

## References

Bae SW, Choi S, Lee C, Tanigawa S (2011) Exact algorithms for the bottleneck Steiner tree problem. Algorithmica 61(4):924–948

Bae SW, Lee C, Choi S (2010) On exact solutions to the Euclidean bottleneck Steiner tree problem. Inf Process Lett 110(16):672–678

Bender MA, Farach-Colton M (2000) The LCA problem revisited. In: LATIN,

*Lecture Notes in Computer Science*, vol. 1776, pp. 88–94. Springerde Berg M, Cheong O, van Kreveld MJ, Overmars MH (2008) Computational geometry: algorithms and applications, 3rd edn. Springer, New York

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

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. SpringerBose P, Maheshwari A, Narasimhan G, Smid MHM, Zeh N (2004) Approximating geometric bottleneck shortest paths. Comput Geom 29(3):233–249

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–110

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–354

Brazil M, Ras CJ, Swanepoel KJ, Thomas DA (2015) Generalised k-Steiner tree problems in normed planes. Algorithmica 71(1):66–86

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–91

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–208

Brazil M, Thomas DA, Weng JF (2000) On the complexity of the Steiner problem. J Comb Optim 4(2):187–195

Brazil M, Zachariasen M (2015) Optimal interconnection trees in the plane: theory, algorithms and applications, vol 29. Springer, New York

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–260

Chazelle B, Guibas LJ, Lee DT (1985) The power of geometric duality. BIT Comput Sci Sect 25(1):76–90

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

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

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–346

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

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–429

Garey MR, Graham RL, Johnson DS (1977) The complexity of computing Steiner minimal trees. SIAM J Appl Math 32(4):835–859

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–29

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–355

Holby J (2017) Variations on the Euclidean Steiner tree problem and algorithms. Rose-Hulman Undergrad Math J 18(1):7

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–508

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

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–537

Rubinstein JH, Thomas DA, Wormald NC (1997) Steiner trees for terminals constrained to curves. SIAM J Discret Math 10(1):1–17

Schieber B, Vishkin U (1988) On finding lowest common ancestors: Simplification and parallelization. SIAM J Comput 17(6):1253–1262

Vanek J, Galicia JAG, Benes B (2014) Clever support: efficient support structure generation for digital fabrication. Comput Graph Forum 33(5):117–125

Winter P (1993) Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs. Discrete Appl. Math. 47(2):187–206

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–72

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

## Acknowledgements

The authors thank Jean-Lou De Carufel for helpful discussions.

## Author information

### Affiliations

### Corresponding author

## Ethics declarations

### Conflict of interest

The authors declare that they have no conflict of interest.

## Additional information

### Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of this paper appeared in COCOON 2020 under the title “On the restricted 1-Steiner tree problem” Bose et al. 2020.

This research was funded in part by the Natural Sciences and Engineering Research Council of Canada (NSERC).

## Rights and permissions

## About this article

### Cite this article

Bose, P., D’Angelo, A. & Durocher, S. On the restricted *k*-Steiner tree problem.
*J Comb Optim* (2021). https://doi.org/10.1007/s10878-021-00808-z

Accepted:

Published:

### Keywords

- Minimum
*k*-Steiner tree - Steiner point restrictions
- Computational geometry
- Combinatorial optimization