{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:11Z","timestamp":1740109331928,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,1,9]],"date-time":"2024-01-09T00:00:00Z","timestamp":1704758400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,9]],"date-time":"2024-01-09T00:00:00Z","timestamp":1704758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["KARST, project number 101071836"],"award-info":[{"award-number":["KARST, project number 101071836"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["P1-0297, J1-1693, J1-2452, N1-0218, N1-0285","P1-0297, J1-1693, J1-2452, N1-0218, N1-0285"],"award-info":[{"award-number":["P1-0297, J1-1693, J1-2452, N1-0218, N1-0285","P1-0297, J1-1693, J1-2452, N1-0218, N1-0285"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,5]]},"abstract":"Abstract<\/jats:title>For a set $${\\mathcal {Q}}$$<\/jats:tex-math>\n Q<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of points in the plane and a real number $$\\delta \\ge 0$$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n \u2265<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, let $${\\mathbb {G}}_\\delta ({\\mathcal {Q}})$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n \u03b4<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n Q<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be the graph defined on $${\\mathcal {Q}}$$<\/jats:tex-math>\n Q<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> by connecting each pair of points at distance at most $$\\delta $$<\/jats:tex-math>\n \u03b4<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.We consider the connectivity of $${\\mathbb {G}}_\\delta ({\\mathcal {Q}})$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n \u03b4<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n Q<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in the best scenario when the location of a few of the points is uncertain, but we know for each uncertain point a line segment that contains it. More precisely, we consider the following optimization problem: given a set $${\\mathcal {P}}$$<\/jats:tex-math>\n P<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of $$n-k$$<\/jats:tex-math>\n \n n<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> points in the plane and a set $${\\mathcal {S}}$$<\/jats:tex-math>\n S<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of k<\/jats:italic> line segments in the plane, find the minimum $$\\delta \\ge 0$$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n \u2265<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with the property that we can select one point $$p_s\\in s$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n \u2208<\/mml:mo>\n s<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for each segment $$s\\in {\\mathcal {S}}$$<\/jats:tex-math>\n \n s<\/mml:mi>\n \u2208<\/mml:mo>\n S<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and the corresponding graph $${\\mathbb {G}}_\\delta ( {\\mathcal {P}}\\cup \\{ p_s\\mid s\\in {\\mathcal {S}}\\})$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n \u03b4<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n P<\/mml:mi>\n \u222a<\/mml:mo>\n \n {<\/mml:mo>\n \n p<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n \u2223<\/mml:mo>\n s<\/mml:mi>\n \u2208<\/mml:mo>\n S<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is connected. It is known that the problem is NP-hard. We provide an algorithm to exactly compute an optimal solution in $${{\\,\\mathrm{{\\mathcal {O}}}\\,}}(f(k) n \\log n)$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n \n <\/mml:mrow>\n (<\/mml:mo>\n f<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, for a computable function $$f(\\cdot )$$<\/jats:tex-math>\n \n f<\/mml:mi>\n (<\/mml:mo>\n \u00b7<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This implies that the problem is FPT when parameterized by k<\/jats:italic>. The best previous algorithm uses $${{\\,\\mathrm{{\\mathcal {O}}}\\,}}((k!)^k k^{k+1}\\cdot n^{2k})$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n \n <\/mml:mrow>\n (<\/mml:mo>\n \n \n (<\/mml:mo>\n k<\/mml:mi>\n !<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n k<\/mml:mi>\n <\/mml:msup>\n \n k<\/mml:mi>\n \n k<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n 2<\/mml:mn>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time and computes the solution up to fixed precision.\n<\/jats:p>","DOI":"10.1007\/s00453-023-01200-5","type":"journal-article","created":{"date-parts":[[2024,1,9]],"date-time":"2024-01-09T06:02:33Z","timestamp":1704780153000},"page":"1512-1544","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Connectivity with Uncertainty Regions Given as Line Segments"],"prefix":"10.1007","volume":"86","author":[{"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Gajser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,9]]},"reference":[{"key":"1200_CR1","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/BF02574698","volume":"6","author":"PK Agarwal","year":"1991","unstructured":"Agarwal, P.K., Edelsbrunner, H., Schwarzkopf, O.: Euclidean minimum spanning trees and bichromatic closest pairs. Discret. Comput. Geom. 6, 407\u2013422 (1991). https:\/\/doi.org\/10.1007\/BF02574698","journal-title":"Discret. Comput. Geom."},{"issue":"4","key":"1200_CR2","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1007\/s00453-011-9553-y","volume":"61","author":"SW Bae","year":"2011","unstructured":"Bae, S.W., Choi, S., Lee, C., Tanigawa, S.: Exact algorithms for the bottleneck Steiner tree problem. Algorithmica 61(4), 924\u2013948 (2011). https:\/\/doi.org\/10.1007\/s00453-011-9553-y","journal-title":"Algorithmica"},{"issue":"16","key":"1200_CR3","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1016\/j.ipl.2010.05.014","volume":"110","author":"SW Bae","year":"2010","unstructured":"Bae, S.W., Lee, C., Choi, S.: On exact solutions to the Euclidean bottleneck Steiner tree problem. Inf. Process. Lett. 110(16), 672\u2013678 (2010). https:\/\/doi.org\/10.1016\/j.ipl.2010.05.014","journal-title":"Inf. Process. Lett."},{"key":"1200_CR4","doi-asserted-by":"crossref","unstructured":"Bandyapadhyay, S., Lochet, W., Lokshtanov, D., Saurabh, S., Xue, J.: Euclidean bottleneck Steiner tree is fixed-parameter tractable, 2023. To appear in SODA (2024). Preprint available at https:\/\/arxiv.org\/abs\/2312.01589","DOI":"10.1137\/1.9781611977912.27"},{"key":"1200_CR5","doi-asserted-by":"crossref","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in real algebraic geometry, volume\u00a010 of Algorithms and Computation in Mathematics. Springer, Berlin, 2nd edition, (2006)","DOI":"10.1007\/3-540-33099-2"},{"issue":"4","key":"1200_CR6","doi-asserted-by":"publisher","first-page":"2893","DOI":"10.1007\/s10878-021-00808-z","volume":"44","author":"P Bose","year":"2022","unstructured":"Bose, P., D\u2019Angelo, A., Durocher, S.: On the restricted k-steiner tree problem. J. Comb. Optim. 44(4), 2893\u20132918 (2022). https:\/\/doi.org\/10.1007\/s10878-021-00808-z","journal-title":"J. Comb. Optim."},{"issue":"1","key":"1200_CR7","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/s00453-013-9780-5","volume":"71","author":"M Brazil","year":"2015","unstructured":"Brazil, M., Ras, C.J., Swanepoel, K.J., Thomas, D.A.: Generalised k-Steiner tree problems in normed planes. Algorithmica 71(1), 66\u201386 (2015). https:\/\/doi.org\/10.1007\/s00453-013-9780-5","journal-title":"Algorithmica"},{"issue":"1","key":"1200_CR8","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/s00453-007-9132-4","volume":"55","author":"C Burnikel","year":"2009","unstructured":"Burnikel, C., Funke, S., Mehlhorn, K., Schirra, S., Schmitt, S.: A separation bound for real algebraic expressions. Algorithmica 55(1), 14\u201328 (2009). https:\/\/doi.org\/10.1007\/s00453-007-9132-4","journal-title":"Algorithmica"},{"issue":"3","key":"1200_CR9","doi-asserted-by":"publisher","first-page":"990","DOI":"10.1007\/s00453-016-0191-2","volume":"78","author":"EW Chambers","year":"2017","unstructured":"Chambers, E.W., Erickson, A., Fekete, S.P., Lenchner, J., Sember, J., Venkatesh, S., Stege, U., Stolpner, S., Weibel, C., Whitesides, S.: Connectivity graphs of uncertainty regions. Algorithmica 78(3), 990\u20131019 (2017). https:\/\/doi.org\/10.1007\/s00453-016-0191-2","journal-title":"Algorithmica"},{"issue":"1","key":"1200_CR10","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1145\/7531.7537","volume":"34","author":"R Cole","year":"1987","unstructured":"Cole, R.: Slowing down sorting networks to obtain faster sorting algorithms. J. ACM 34(1), 200\u2013208 (1987). https:\/\/doi.org\/10.1145\/7531.7537","journal-title":"J. ACM"},{"key":"1200_CR11","doi-asserted-by":"publisher","unstructured":"de\u00a0Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, 3rd edition, (2008). https:\/\/doi.org\/10.1007\/978-3-540-77974-2","DOI":"10.1007\/978-3-540-77974-2"},{"key":"1200_CR12","unstructured":"Eppstein, D.: Quasiconvex programming. In Goodman, J.E. Pach J. and Welzl E., editors, Combinatorial and Computational Geometry, volume\u00a052 of MSRI Publications. Cambridge Univ. Press, 2005. Preprint at http:\/\/arxiv.org\/abs\/cs\/0412046"},{"issue":"5","key":"1200_CR13","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0167-6377(96)00028-4","volume":"19","author":"JL Ganley","year":"1996","unstructured":"Ganley, J.L., Salowe, J.S.: Optimal and approximate bottleneck Steiner trees. Oper. Res. Lett. 19(5), 217\u2013224 (1996). https:\/\/doi.org\/10.1016\/S0167-6377(96)00028-4","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1200_CR14","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/0196-6774(87)90032-0","volume":"8","author":"G Georgakopoulos","year":"1987","unstructured":"Georgakopoulos, G., Papadimitriou, C.H.: The 1-Steiner tree problem. J. Algorithms 8(1), 122\u2013130 (1987). https:\/\/doi.org\/10.1016\/0196-6774(87)90032-0","journal-title":"J. Algorithms"},{"key":"1200_CR15","unstructured":"Joseph, F.: J\u00e1J\u00e1. Addison-Wesley, An Introduction to Parallel Algorithms (1992)"},{"issue":"1","key":"1200_CR16","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.comgeo.2007.06.003","volume":"40","author":"L Kettner","year":"2008","unstructured":"Kettner, L., Mehlhorn, K., Pion, S., Schirra, S., Yap, C.-K.: Classroom examples of robustness problems in geometric computations. Comput. Geom. 40(1), 61\u201378 (2008). https:\/\/doi.org\/10.1016\/j.comgeo.2007.06.003","journal-title":"Comput. Geom."},{"issue":"1","key":"1200_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jlap.2004.07.006","volume":"64","author":"C Li","year":"2005","unstructured":"Li, C., Pion, S., Yap, C.-K.: Recent progress in exact geometric computation. J. Log. Algebraic Methods Program. 64(1), 85\u2013111 (2005). https:\/\/doi.org\/10.1016\/j.jlap.2004.07.006","journal-title":"J. Log. Algebraic Methods Program."},{"issue":"2","key":"1200_CR18","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00453-008-9174-2","volume":"56","author":"M L\u00f6ffler","year":"2010","unstructured":"L\u00f6ffler, M., van Kreveld, M.: Largest and smallest convex hulls for imprecise points. Algorithmica 56(2), 235\u2013269 (2010). https:\/\/doi.org\/10.1007\/s00453-008-9174-2","journal-title":"Algorithmica"},{"issue":"4","key":"1200_CR19","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.comgeo.2009.03.007","volume":"43","author":"M L\u00f6ffler","year":"2010","unstructured":"L\u00f6ffler, M., van Kreveld, M.: Largest bounding box, smallest diameter, and related problems on imprecise points. Comput. Geom. 43(4), 419\u2013433 (2010). https:\/\/doi.org\/10.1016\/j.comgeo.2009.03.007","journal-title":"Comput. Geom."},{"issue":"4","key":"1200_CR20","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"N Megiddo","year":"1979","unstructured":"Megiddo, N.: Combinatorial optimization with rational objective functions. Math. Oper. Res. 4(4), 414\u2013424 (1979). https:\/\/doi.org\/10.1287\/moor.4.4.414","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1200_CR21","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N Megiddo","year":"1983","unstructured":"Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. J. ACM 30(4), 852\u2013865 (1983). https:\/\/doi.org\/10.1145\/2157.322410","journal-title":"J. ACM"},{"key":"1200_CR22","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Schirra, S.: Exact computation with leda_real\u2014theory and geometric applications. In Alefeld, G., Rohn, J., Rump, S. and Yamamoto T., editors, Symbolic Algebraic Methods and Verification Methods, pages 163\u2013172. Springer, (2001)","DOI":"10.1007\/978-3-7091-6280-4_16"},{"issue":"3","key":"1200_CR23","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02293049","volume":"8","author":"C Monma","year":"1992","unstructured":"Monma, C., Suri, S.: Transitions in geometric minimum spanning trees. Discret. Comput. Geom. 8(3), 265\u2013293 (1992)","journal-title":"Discret. Comput. Geom."},{"issue":"3","key":"1200_CR24","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1109\/12.127452","volume":"41","author":"M Sarrafzadeh","year":"1992","unstructured":"Sarrafzadeh, M., Wong, C.K.: Bottleneck Steiner trees in the plane. IEEE Trans. Comput. 41(3), 370\u2013374 (1992). https:\/\/doi.org\/10.1109\/12.127452","journal-title":"IEEE Trans. Comput."},{"key":"1200_CR25","doi-asserted-by":"publisher","unstructured":"Shamos, M.I., Hoey, D.: Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science (SFCS 1975), pages 151\u2013162, (1975). URL: https:\/\/doi.org\/10.1109\/SFCS.1975.8","DOI":"10.1109\/SFCS.1975.8"},{"key":"1200_CR26","doi-asserted-by":"publisher","unstructured":"Sharma, V., Yap, C.K.: Robust geometric computation. In Goodman, J.E. O\u2019Rourke, J. and T\u00f3th, C.D. editors, Handbook of Discrete and Computational Geometry, pages 1189\u20131223. Chapman and Hall\/CRC, 3rd edition, (2017). URL: https:\/\/doi.org\/10.1201\/9781315119601","DOI":"10.1201\/9781315119601"},{"issue":"4","key":"1200_CR27","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/j.jda.2008.04.002","volume":"6","author":"M van Kreveld","year":"2008","unstructured":"van Kreveld, M., L\u00f6ffler, M.: Approximating largest convex hulls for imprecise points. J. Discrete Algorithms 6(4), 583\u2013594 (2008). https:\/\/doi.org\/10.1016\/j.jda.2008.04.002","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"1200_CR28","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/s00453-001-0089-4","volume":"32","author":"L Wang","year":"2002","unstructured":"Wang, L., Ding-Zhu, D.: Approximations for a bottleneck steiner tree problem. Algorithmica 32(4), 554\u2013561 (2002). https:\/\/doi.org\/10.1007\/s00453-001-0089-4","journal-title":"Algorithmica"},{"issue":"3","key":"1200_CR29","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0020-0190(01)00209-5","volume":"81","author":"L Wang","year":"2002","unstructured":"Wang, L., Li, Z.: An approximation algorithm for a bottleneck k-steiner tree problem in the euclidean plane. Inf. Process. Lett. 81(3), 151\u2013156 (2002). https:\/\/doi.org\/10.1016\/S0020-0190(01)00209-5","journal-title":"Inf. Process. Lett."},{"key":"1200_CR30","unstructured":"Yap, C.-K.: Fundamental problems of algorithmic algebra. Oxford University Press, (1999)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01200-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01200-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01200-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,21]],"date-time":"2024-04-21T03:03:10Z","timestamp":1713668590000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01200-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,9]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1200"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01200-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,1,9]]},"assertion":[{"value":"17 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}