Journal article

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

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH | WILEY | Published : 2021

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.

Grants

Funding Acknowledgements

David Whittle is the grateful recipient of the 2015 Gilbert Rigg Scholarship, which supported his graduate research in underground mine plan optimization. In addition, David was awarded the 2016 John Collier Scholarship to support his research-related travel.