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

doi:10.1111/itor.13055

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 journal › Article › Research › peer-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 language	English
Pages (from-to)	2201-2225
Number of pages	25
Journal	International Transactions in Operational Research
Volume	29
Issue number	4
DOIs	https://doi.org/10.1111/itor.13055
Publication status	Published - Jul 2022
Externally published	Yes

Access to Document

10.1111/itor.13055

Cite this

@article{bed998d7b9084d8db57b84473e116b88,

title = "Minimum Steiner trees on a set of concyclic points and their center",

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

author = "David Whittle and Marcus Brazil and Grossman, {Peter Alexander} and Rubinstein, {Joachim Hyam} and Thomas, {Doreen A.}",

note = "Funding Information: 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. Publisher Copyright: {\textcopyright} 2021 The Authors. International Transactions in Operational Research {\textcopyright} 2021 International Federation of Operational Research Societies",

year = "2022",

month = jul,

doi = "10.1111/itor.13055",

language = "English",

volume = "29",

pages = "2201--2225",

journal = "International Transactions in Operational Research",

issn = "0969-6016",

publisher = "Wiley-Blackwell",

number = "4",

}

TY - JOUR

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

AU - Whittle, David

AU - Brazil, Marcus

AU - Grossman, Peter Alexander

AU - Rubinstein, Joachim Hyam

AU - Thomas, Doreen A.

N1 - Funding Information: 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. Publisher Copyright: © 2021 The Authors. International Transactions in Operational Research © 2021 International Federation of Operational Research Societies

PY - 2022/7

Y1 - 2022/7

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

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

UR - http://www.scopus.com/inward/record.url?scp=85114725983&partnerID=8YFLogxK

U2 - 10.1111/itor.13055

DO - 10.1111/itor.13055

M3 - Article

AN - SCOPUS:85114725983

SN - 0969-6016

VL - 29

SP - 2201

EP - 2225

JO - International Transactions in Operational Research

JF - International Transactions in Operational Research

IS - 4

ER -

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

Abstract

Access to Document

Other files and links

Cite this