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