{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T20:29:50Z","timestamp":1764361790274,"version":"3.46.0"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T00:00:00Z","timestamp":1757289600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T00:00:00Z","timestamp":1757289600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100008131","name":"Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008131","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The\n                    <jats:italic>geodesic edge center<\/jats:italic>\n                    of a simple polygon is a point\n                    <jats:italic>c<\/jats:italic>\n                    inside the polygon that minimizes the maximum geodesic distance from\n                    <jats:italic>c<\/jats:italic>\n                    to any edge of the polygon, where\n                    <jats:italic>geodesic distance<\/jats:italic>\n                    is the shortest path distance inside the polygon. We give a linear-time algorithm to find a geodesic edge center of a simple polygon. This improves on the previous\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n \\log n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time algorithm by Lubiw and Naredla [European Symposium on Algorithms, 2021]. The algorithm builds on an algorithm to find the geodesic\n                    <jats:italic>vertex<\/jats:italic>\n                    center of a simple polygon due to Pollack, Sharir, and Rote [Discrete &amp; Computational Geometry, 1989] and an improvement to linear time by Ahn, Barba, Bose, De Carufel, Korman, and Oh [Discrete &amp; Computational Geometry, 2016]. The geodesic edge center can easily be found from the geodesic farthest-edge Voronoi diagram of the polygon. Finding that Voronoi diagram in linear time is an open question, although the geodesic\n                    <jats:italic>nearest<\/jats:italic>\n                    edge Voronoi diagram (the medial axis) can be found in linear time. As a first step of our geodesic edge center algorithm, we give a linear-time algorithm to find the geodesic farthest-edge Voronoi diagram restricted to the polygon boundary.\n                  <\/jats:p>","DOI":"10.1007\/s00454-025-00768-9","type":"journal-article","created":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T20:29:31Z","timestamp":1757363371000},"page":"944-998","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Geodesic Edge Center of a Simple Polygon"],"prefix":"10.1007","volume":"74","author":[{"given":"Anna","family":"Lubiw","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3577-903X","authenticated-orcid":false,"given":"Anurag Murty","family":"Naredla","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,8]]},"reference":[{"issue":"1","key":"768_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3284355","volume":"15","author":"M Abrahamsen","year":"2018","unstructured":"Abrahamsen, M., Walczak, B.: Common tangents of two disjoint polygons in linear time and constant workspace. ACM Transactions on Algorithms (TALG) 15(1), 1\u201321 (2018). https:\/\/doi.org\/10.1145\/3284355","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"6","key":"768_CR2","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/bf02187749","volume":"4","author":"A Aggarwal","year":"1989","unstructured":"Aggarwal, A., Guibas, L.J., Saxe, J., Shor, P.W.: A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete & Computational Geometry 4(6), 591\u2013604 (1989). https:\/\/doi.org\/10.1007\/bf02187749","journal-title":"Discrete & Computational Geometry"},{"issue":"1\u20134","key":"768_CR3","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/bf01840359","volume":"2","author":"A Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M.M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica 2(1\u20134), 195\u2013208 (1987). https:\/\/doi.org\/10.1007\/bf01840359","journal-title":"Algorithmica"},{"issue":"4","key":"768_CR4","doi-asserted-by":"publisher","first-page":"836","DOI":"10.1007\/s00454-016-9796-0","volume":"56","author":"H-K Ahn","year":"2016","unstructured":"Ahn, H.-K., Barba, L., Bose, P., De Carufel, J.-L., Korman, M., Eunjin, O.: A linear-time algorithm for the geodesic center of a simple polygon. Discrete & Computational Geometry 56(4), 836\u2013859 (2016). https:\/\/doi.org\/10.1007\/s00454-016-9796-0","journal-title":"Discrete & Computational Geometry"},{"issue":"8","key":"768_CR5","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1016\/j.comgeo.2010.04.004","volume":"43","author":"O Aichholzer","year":"2010","unstructured":"Aichholzer, O., Aigner, W., Aurenhammer, F., Hackl, T., J\u00fcttler, B., Pilgerstorfer, E., Rabl, M.: Divide-and-conquer for Voronoi diagrams revisited. Comput. Geom. 43(8), 688\u2013699 (2010). https:\/\/doi.org\/10.1016\/j.comgeo.2010.04.004","journal-title":"Comput. Geom."},{"issue":"3","key":"768_CR6","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/bf02189321","volume":"9","author":"B Aronov","year":"1993","unstructured":"Aronov, B., Fortune, S., Wilfong, G.: The furthest-site geodesic Voronoi diagram. Discrete & Computational Geometry 9(3), 217\u2013255 (1993). https:\/\/doi.org\/10.1007\/bf02189321","journal-title":"Discrete & Computational Geometry"},{"issue":"6","key":"768_CR7","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.ipl.2006.07.008","volume":"100","author":"F Aurenhammer","year":"2006","unstructured":"Aurenhammer, F., Drysdale, R.L.S., Krasser, H.: Farthest line segment Voronoi diagrams. Inf. Process. Lett. 100(6), 220\u2013225 (2006). https:\/\/doi.org\/10.1016\/j.ipl.2006.07.008","journal-title":"Inf. Process. Lett."},{"key":"768_CR8","doi-asserted-by":"publisher","DOI":"10.1142\/8685","author":"F Aurenhammer","year":"2013","unstructured":"Aurenhammer, F., Klein, R., Lee, D.-T.: Voronoi diagrams and Delaunay triangulations. World Scientific Publishing Company (2013). https:\/\/doi.org\/10.1142\/8685","journal-title":"World Scientific Publishing Company"},{"key":"768_CR9","doi-asserted-by":"publisher","unstructured":"Barba, L.: Optimal algorithm for geodesic farthest-point voronoi diagrams. In Gill Barequet and Yusu Wang, editors, 35th International Symposium on Computational Geometry (SoCG 2019), volume 129 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1\u201312:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2019.12","DOI":"10.4230\/LIPIcs.SoCG.2019.12"},{"issue":"3","key":"768_CR10","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/bf02246508","volume":"52","author":"BK Bhattacharya","year":"1994","unstructured":"Bhattacharya, B.K., Jadhav, S., Mukhopadhyay, A., Robert, J.-M.: Optimal algorithms for some intersection radius problems. Computing 52(3), 269\u2013279 (1994). https:\/\/doi.org\/10.1007\/bf02246508","journal-title":"Computing"},{"issue":"2","key":"768_CR11","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/bf02189314","volume":"9","author":"B Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete & Computational Geometry 9(2), 145\u2013158 (1993). https:\/\/doi.org\/10.1007\/bf02189314","journal-title":"Discrete & Computational Geometry"},{"key":"768_CR12","doi-asserted-by":"publisher","unstructured":"Chazelle, B.: Cuttings. In Dinesh\u00a0P. Mehta and Sartaj Sahni, editors, Handbook of Data Structures and Applications, chapter\u00a026, pages 397\u2013404. Chapman and Hall\/CRC, 2nd edition, (2018). https:\/\/doi.org\/10.1201\/9781315119335","DOI":"10.1201\/9781315119335"},{"issue":"6","key":"768_CR13","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/bf02187747","volume":"4","author":"B Chazelle","year":"1989","unstructured":"Chazelle, B., Guibas, L.J.: Visibility and intersection problems in plane geometry. Discrete & Computational Geometry 4(6), 551\u2013581 (1989). https:\/\/doi.org\/10.1007\/bf02187747","journal-title":"Discrete & Computational Geometry"},{"issue":"4","key":"768_CR14","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1016\/j.comgeo.2010.11.004","volume":"44","author":"O Cheong","year":"2011","unstructured":"Cheong, O., Everett, H., Glisse, M., Gudmundsson, J., Hornus, S., Lazard, S., Lee, M., Na, H.-S.: Farthest-polygon Voronoi diagrams. Comput. Geom. 44(4), 234\u2013247 (2011). https:\/\/doi.org\/10.1016\/j.comgeo.2010.11.004","journal-title":"Comput. Geom."},{"issue":"3","key":"768_CR15","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/pl00009429","volume":"21","author":"F Chin","year":"1999","unstructured":"Chin, F., Snoeyink, J., Wang, C.A.: Finding the medial axis of a simple polygon in linear time. Discrete & Computational Geometry 21(3), 405\u2013420 (1999). https:\/\/doi.org\/10.1007\/pl00009429","journal-title":"Discrete & Computational Geometry"},{"key":"768_CR16","doi-asserted-by":"publisher","unstructured":"Choi, H.I., Han, C.Y.: The medial axis transform. In Gerald Farin, Josef Hoschek, and M.-S. Kim, editors, Handbook of Computer Aided Geometric Design, chapter\u00a019. Elsevier, (2002) https:\/\/doi.org\/10.1016\/b978-044451104-1\/50020-4","DOI":"10.1016\/b978-044451104-1\/50020-4"},{"issue":"2","key":"768_CR17","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.ipl.2007.08.004","volume":"105","author":"RLS Drysdale","year":"2008","unstructured":"Drysdale, R.L.S., Mukhopadhyay, A.: An $${O}(n \\log n)$$ algorithm for the all-farthest-segments problem for a planar set of points. Inf. Process. Lett. 105(2), 47\u201351 (2008). https:\/\/doi.org\/10.1016\/j.ipl.2007.08.004","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"768_CR18","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1137\/0213003","volume":"13","author":"ME Dyer","year":"1984","unstructured":"Dyer, M.E.: Linear time algorithms for two- and three-variable linear programs. SIAM J. Comput. 13(1), 31\u201345 (1984). https:\/\/doi.org\/10.1137\/0213003","journal-title":"SIAM J. Comput."},{"issue":"2","key":"768_CR19","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., O\u2019Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15(2), 341\u2013363 (1986). https:\/\/doi.org\/10.1137\/0215024","journal-title":"SIAM J. Comput."},{"issue":"1\u20134","key":"768_CR20","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/bf01840360","volume":"2","author":"L Guibas","year":"1987","unstructured":"Guibas, L., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.E.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2(1\u20134), 209\u2013233 (1987). https:\/\/doi.org\/10.1007\/bf01840360","journal-title":"Algorithmica"},{"issue":"2","key":"768_CR21","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/0022-0000(89)90041-X","volume":"39","author":"LJ Guibas","year":"1989","unstructured":"Guibas, L.J., Hershberger, J.: Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci. 39(2), 126\u2013152 (1989). https:\/\/doi.org\/10.1016\/0022-0000(89)90041-X","journal-title":"J. Comput. Syst. Sci."},{"key":"768_CR22","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/173","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. American Mathematical Society (2011). https:\/\/doi.org\/10.1090\/surv\/173","journal-title":"American Mathematical Society"},{"issue":"2","key":"768_CR23","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"Dov Harel and Robert Endre Tarjan","year":"1984","unstructured":"Dov Harel and Robert Endre Tarjan: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984). https:\/\/doi.org\/10.1137\/0213024","journal-title":"SIAM J. Comput."},{"issue":"2","key":"768_CR24","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/bf02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $$\\epsilon $$-nets and simplex range queries. Discrete & Computational Geometry 2(2), 127\u2013151 (1987). https:\/\/doi.org\/10.1007\/bf02187876","journal-title":"Discrete & Computational Geometry"},{"issue":"6","key":"768_CR25","doi-asserted-by":"publisher","first-page":"1612","DOI":"10.1137\/s0097539793253577","volume":"26","author":"J Hershberger","year":"1997","unstructured":"Hershberger, J., Suri, S.: Matrix searching with the shortest-path metric. SIAM J. Comput. 26(6), 1612\u20131634 (1997). https:\/\/doi.org\/10.1137\/s0097539793253577","journal-title":"SIAM J. Comput."},{"issue":"2","key":"768_CR26","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1006\/jagm.1996.0013","volume":"20","author":"S Jadhav","year":"1996","unstructured":"Jadhav, S., Mukhopadhyay, A., Bhattacharya, B.: An optimal algorithm for the intersection radius of a set of convex polygons. J. Algorithms 20(2), 244\u2013267 (1996). https:\/\/doi.org\/10.1006\/jagm.1996.0013","journal-title":"J. Algorithms"},{"key":"768_CR27","doi-asserted-by":"publisher","unstructured":"Khramtcova, E., Papadopoulou, E.: An expected linear-time algorithm for the farthest-segment Voronoi diagram. arXiv, (2014) https:\/\/doi.org\/10.48550\/arxiv.1411.2816","DOI":"10.48550\/arxiv.1411.2816"},{"issue":"3","key":"768_CR28","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"D-T Lee","year":"1984","unstructured":"Lee, D.-T., Preparata, F.P.: Euclidean shortest paths in the presence of rectilinear barriers. Networks 14(3), 393\u2013410 (1984). https:\/\/doi.org\/10.1002\/net.3230140304","journal-title":"Networks"},{"key":"768_CR29","doi-asserted-by":"publisher","unstructured":"Lubiw, A., Naredla, A.M.: The visibility center of a simple polygon. arXiv, (2021) https:\/\/doi.org\/10.48550\/arxiv.2108.07366","DOI":"10.48550\/arxiv.2108.07366"},{"key":"768_CR30","doi-asserted-by":"publisher","unstructured":"Lubiw, A., Naredla, A.M.: The visibility center of a simple polygon. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms (ESA 2021), volume 204 of Leibniz International Proceedings in Informatics (LIPIcs), pages 65:1\u201365:14, Dagstuhl, Germany, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik. (2021) https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.65","DOI":"10.4230\/LIPIcs.ESA.2021.65"},{"key":"768_CR31","doi-asserted-by":"publisher","unstructured":"Lubiw, A., Naredla, A.M.: The Geodesic Edge Center of a Simple Polygon. In Erin\u00a0W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry (SoCG 2023), volume 258 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1\u201349:15, Dagstuhl, Germany, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik. (2023) https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2023.49","DOI":"10.4230\/LIPIcs.SoCG.2023.49"},{"key":"768_CR32","doi-asserted-by":"publisher","unstructured":"Matou\u0161ek, J.: Construction of epsilon nets. In Kurt Mehlhorn, editor, Proceedings of the Fifth Annual Symposium on Computational Geometry, pages 1\u201310, (1989). https:\/\/doi.org\/10.1145\/73833.73834","DOI":"10.1145\/73833.73834"},{"issue":"3","key":"768_CR33","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/bf02574697","volume":"6","author":"J Matou\u0161ek","year":"1991","unstructured":"Matou\u0161ek, J.: Cutting hyperplane arrangements. Discrete & Computational Geometry 6(3), 385\u2013406 (1991). https:\/\/doi.org\/10.1007\/bf02574697","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"768_CR34","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1006\/jcss.1995.1018","volume":"50","author":"J Matou\u0161ek","year":"1995","unstructured":"Matou\u0161ek, J.: Approximations and optimal geometric divide-and-conquer. J. Comput. Syst. Sci. 50(2), 203\u2013208 (1995). https:\/\/doi.org\/10.1006\/jcss.1995.1018","journal-title":"J. Comput. Syst. Sci."},{"key":"768_CR35","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry, volume 212 of Graduate Texts in Mathematics. Springer Verlag (2002). https:\/\/doi.org\/10.1007\/978-1-4613-0039-7","journal-title":"Springer Verlag"},{"issue":"4","key":"768_CR36","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N Megiddo","year":"1983","unstructured":"Megiddo, N.: Linear-time algorithms for linear programming in $${R}^3$$ and related problems. SIAM J. Comput. 12(4), 759\u2013776 (1983). https:\/\/doi.org\/10.1137\/0212052","journal-title":"SIAM J. Comput."},{"issue":"6","key":"768_CR37","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/bf02187750","volume":"4","author":"N Megiddo","year":"1989","unstructured":"Megiddo, N.: On the ball spanned by balls. Discrete & Computational Geometry 4(6), 605\u2013610 (1989). https:\/\/doi.org\/10.1007\/bf02187750","journal-title":"Discrete & Computational Geometry"},{"key":"768_CR38","unstructured":"Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, (1994)"},{"key":"768_CR39","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/265","author":"NH Mustafa","year":"2022","unstructured":"Mustafa, N.H.: Sampling in Combinatorial and Geometric Set Systems, volume 265 of Mathematical Surveys and Monographs. American Mathematical Society (2022). https:\/\/doi.org\/10.1090\/surv\/265","journal-title":"American Mathematical Society"},{"key":"768_CR40","doi-asserted-by":"publisher","unstructured":"Mustafa, N.H., Varadarajan, K.: Epsilon-approximations & epsilon-nets. In Csaba\u00a0D. Toth, Joseph O\u2019Rourke, and Jacob\u00a0E. Goodman, editors, Handbook of Discrete and Computational Geometry, chapter\u00a047, pages 1241\u20131267. Chapman and Hall\/CRC, 3rd edition, (2017). https:\/\/doi.org\/10.1201\/9781315119601","DOI":"10.1201\/9781315119601"},{"key":"768_CR41","unstructured":"Naredla, A.M.: Algorithms for Geometric Facility Location: Centers in a Polygon and Dispersion on a Line. PhD thesis, University of Waterloo, (2023) URL: http:\/\/hdl.handle.net\/10012\/19182"},{"issue":"2","key":"768_CR42","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1007\/s00454-019-00063-4","volume":"63","author":"O Eunjin","year":"2020","unstructured":"Eunjin, O., Ahn, H.-K.: Voronoi diagrams for a moderate-sized point-set in a simple polygon. Discrete & Computational Geometry 63(2), 418\u2013454 (2020). https:\/\/doi.org\/10.1007\/s00454-019-00063-4","journal-title":"Discrete & Computational Geometry"},{"issue":"5","key":"768_CR43","doi-asserted-by":"publisher","first-page":"1434","DOI":"10.1007\/s00453-019-00651-z","volume":"82","author":"O Eunjin","year":"2020","unstructured":"Eunjin, O., Barba, L., Ahn, H.-K.: The geodesic farthest-point Voronoi diagram in a simple polygon. Algorithmica 82(5), 1434\u20131473 (2020). https:\/\/doi.org\/10.1007\/s00453-019-00651-z","journal-title":"Algorithmica"},{"issue":"06","key":"768_CR44","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/978-3-642-35261-4_22","volume":"23","author":"Evanthia Papadopoulou and Sandeep Kumar Dey","year":"2013","unstructured":"Evanthia Papadopoulou and Sandeep Kumar Dey: On the farthest line-segment Voronoi diagram. International Journal of Computational Geometry & Applications 23(06), 443\u2013459 (2013). https:\/\/doi.org\/10.1007\/978-3-642-35261-4_22","journal-title":"International Journal of Computational Geometry & Applications"},{"issue":"6","key":"768_CR45","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/bf02187751","volume":"4","author":"R Pollack","year":"1989","unstructured":"Pollack, R., Sharir, M., Rote, G.: Computing the geodesic center of a simple polygon. Discrete & Computational Geometry 4(6), 611\u2013626 (1989). https:\/\/doi.org\/10.1007\/bf02187751","journal-title":"Discrete & Computational Geometry"},{"key":"768_CR46","doi-asserted-by":"publisher","unstructured":"Shamos, M.I., Hoey, D.: Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science (FOCS 1975), pages 151\u2013162. IEEE, (1975). https:\/\/doi.org\/10.1109\/sfcs.1975.8","DOI":"10.1109\/sfcs.1975.8"},{"key":"768_CR47","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(89)90045-7","volume":"39","author":"S Suri","year":"1989","unstructured":"Suri, S.: Computing geodesic furthest neighbors in simple polygons. J. Comput. Syst. Sci. 39, 220\u2013235 (1989). https:\/\/doi.org\/10.1016\/0022-0000(89)90045-7","journal-title":"J. Comput. Syst. Sci."},{"key":"768_CR48","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-022-00424-6","author":"H Wang","year":"2022","unstructured":"Wang, H.: An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons. Discrete & Computational Geometry (2022). https:\/\/doi.org\/10.1007\/s00454-022-00424-6","journal-title":"Discrete & Computational Geometry"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00768-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-025-00768-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00768-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T20:26:12Z","timestamp":1764361572000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-025-00768-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,8]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["768"],"URL":"https:\/\/doi.org\/10.1007\/s00454-025-00768-9","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2025,9,8]]},"assertion":[{"value":"29 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 September 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}