Minimum Steiner trees on a set of concyclic points and their center

David Whittle, Marcus Brazil, Peter Alexander Grossman, Joachim Hyam Rubinstein, Doreen A. Thomas

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Consider a configuration of points comprising a point q and a set of concyclic points R that are all a given distance r from q in the Euclidean plane. In this paper, we investigate the relationship between the length of a minimum Steiner tree (MStT) on (Formula presented.) and a minimum spanning tree on R. We show that if the degree of q in the MStT is 1, then the difference between these two lengths is at least (Formula presented.), and that this lower bound is tight. This bound can be applied as part of an efficient algorithm to find the solution to the prize-collecting Euclidean Steiner tree problem, as outlined in an earlier paper.

Original languageEnglish
Pages (from-to)2201-2225
Number of pages25
JournalInternational Transactions in Operational Research
Volume29
Issue number4
DOIs
Publication statusPublished - Jul 2022
Externally publishedYes

Cite this