{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T06:46:45Z","timestamp":1787381205102,"version":"3.56.0"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1988,10]]},"abstract":"<jats:p>We consider the problem of constructing a Steiner minimal tree connecting a given set K of points and lying inside a polygonally bounded, not necessarily simply connected region R in the plane. We first define the path-convex hull of K in R, which is a \u201csufficiently small\u201d subregion of R guaranteed to contain the Steiner minimal tree. We then give an $\\varepsilon $-approximation scheme to find the Steiner minimal tree in R by reducing it to a Steiner tree problem on a \u201cvisibility graph\u201d associated with K and the path-convex hull of R. This will be a fully polynomial approximation scheme when K is restricted to lie on a small number of interior points and boundary polygons of R. Several techniques are given which further reduce the region in which the Steiner minimal tree is known to lie, and which extend known results for the Steiner minimal tree problem without obstacles.<\/jats:p>","DOI":"10.1137\/0217057","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:30:13Z","timestamp":1109226613000},"page":"920-934","source":"Crossref","is-referenced-by-count":28,"title":["An Approximation Scheme for Finding Steiner Trees with Obstacles"],"prefix":"10.1137","volume":"17","author":[{"given":"J. Scott","family":"Provan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230190107"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0217004"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/321724.321733"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70332-7"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0118014"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1985-0810173-6"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.4.634"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0132072"},{"key":"R11","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010203"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187919"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(81)90203-4"},{"key":"R16","unstructured":"A. L. Liestman, Masters Thesis,  Construction of Steiner trees with obstacles in the plane, Master's thesis, University of Illinois, Urbana-Champaign, Urbana, IL,  1978 0849.94031"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1961-016-2"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180108"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90129-4"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90028-9"},{"key":"R22","unstructured":"M. I. Shamos, Masters Thesis,  Computational Geometry, Ph.D. dissertation, Yale University, New Haven, CT,  1975"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0215014"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120309"},{"key":"R25","unstructured":"J. M. Smith,  Steiner minimal trees with obstacles, Tech. Report, Department of Industrial Engineering and Operations Research, University of Massachusetts, Amherst, MA,  1982"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110104"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130202"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.5957\/jsr.1974.18.1.46"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170203"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0217057","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:09Z","timestamp":1787337789000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0217057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,10]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1988,10]]}},"alternative-id":["10.1137\/0217057"],"URL":"https:\/\/doi.org\/10.1137\/0217057","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,10]]}}}