{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T04:23:55Z","timestamp":1754108635830,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2023,4,8]],"date-time":"2023-04-08T00:00:00Z","timestamp":1680912000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"University of North Florida Academic Technology","award":["CCF-1947887"],"award-info":[{"award-number":["CCF-1947887"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            The construction of bounded-degree plane geometric spanners has been a focus of interest since 2002 when Bose, Gudmundsson, and Smid proposed the first algorithm to construct such spanners. To date, 11 algorithms have been designed with various tradeoffs in degree and stretch-factor. We have implemented these sophisticated spanner algorithms in\n            <jats:sans-serif>C<\/jats:sans-serif>\n            <jats:monospace>++<\/jats:monospace>\n            using the\n            <jats:sans-serif>CGAL<\/jats:sans-serif>\n            library and experimented with them using large synthetic and real-world pointsets. Our experiments have revealed their practical behavior and real-world efficacy. We share the implementations via\n            <jats:sans-serif>GitHub<\/jats:sans-serif>\n            for broader uses and future research.\n          <\/jats:p>\n          <jats:p>\n            We design and engineer\n            <jats:sc>EstimateStretchFactor<\/jats:sc>\n            , a simple practical algorithm, which can estimate stretch-factors (obtains lower bounds on the exact stretch-factors) of geometric spanners\u2014a challenging problem for which no practical algorithm is known yet. In our experiments with bounded-degree plane geometric spanners, we found that\n            <jats:sc>EstimateStretchFactor<\/jats:sc>\n            estimated stretch-factors almost precisely. Further, it gave linear runtime performance in practice for the pointset distributions considered in this work, making it much faster than the naive Dijkstra-based algorithm for calculating stretch-factors.\n          <\/jats:p>","DOI":"10.1145\/3582497","type":"journal-article","created":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T12:08:18Z","timestamp":1675253298000},"page":"1-36","source":"Crossref","is-referenced-by-count":1,"title":["Bounded-Degree Plane Geometric Spanners in Practice"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0674-7223","authenticated-orcid":false,"given":"Frederick","family":"Anderson","sequence":"first","affiliation":[{"name":"University of North Florida, Jacksonville, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0130-5968","authenticated-orcid":false,"given":"Anirban","family":"Ghosh","sequence":"additional","affiliation":[{"name":"University of North Florida, Jacksonville, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7742-0834","authenticated-orcid":false,"given":"Matthew","family":"Graham","sequence":"additional","affiliation":[{"name":"University of North Florida, Jacksonville, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4598-3704","authenticated-orcid":false,"given":"Lucas","family":"Mougeot","sequence":"additional","affiliation":[{"name":"University of North Florida, Jacksonville, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5463-1949","authenticated-orcid":false,"given":"David","family":"Wisnosky","sequence":"additional","affiliation":[{"name":"University of North Florida, Jacksonville, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,4,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-9019-9"},{"key":"e_1_3_2_3_2","volume-title":"Proceedings of the 37th International Symposium on Computational Geometry (SoCG\u201921)","author":"Anderson Fred","year":"2021","unstructured":"Fred Anderson, Anirban Ghosh, Matthew Graham, Lucas Mougeot, and David Wisnosky. 2021. An interactive tool for experimenting with bounded-degree plane geometric spanners (media exposition). In Proceedings of the 37th International Symposium on Computational Geometry (SoCG\u201921)."},{"issue":"6","key":"e_1_3_2_4_2","first-page":"3324","article-title":"A degree 3 plane 5.19-spanner for points in convex position","volume":"28","author":"Bakhshesh Davood","year":"2021","unstructured":"Davood Bakhshesh and Mohammad Farshi. 2021. A degree 3 plane 5.19-spanner for points in convex position. Scientia Iranica 28, 6 (2021), 3324\u20133331.","journal-title":"Scientia Iranica"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.4.387"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98564"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2020.101622"},{"issue":"1","key":"e_1_3_2_8_2","first-page":"11","article-title":"Towards plane spanners of degree 3","volume":"8","author":"Biniaz Ahmad","year":"2017","unstructured":"Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari, and Michiel Smid. 2017. Towards plane spanners of degree 3. Journal of Computational Geometry 8, 1 (2017), 11\u201331.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16926-7_25"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_3"},{"key":"e_1_3_2_11_2","first-page":"205","volume-title":"Proceedings of the European Symposium on Algorithms","author":"Bonichon Nicolas","year":"2012","unstructured":"Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perkovi\u0107. 2012. The stretch factor of \\({L}_1\\) -and \\({L}_\\infty\\) -Delaunay triangulations. In Proceedings of the European Symposium on Algorithms. 205\u2013216."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9676-z"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.03.004"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1168-8"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0305-5"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.04.002"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195909002861"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.12.018"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16988-5_2"},{"issue":"1","key":"e_1_3_2_21_2","first-page":"132","article-title":"Approximating the average stretch factor of geometric graphs","volume":"3","author":"Cheng Siu-Wing","year":"2012","unstructured":"Siu-Wing Cheng, Christian Knauer, Stefan Langerman, and Michiel Smid. 2012. Approximating the average stretch factor of geometric graphs. Journal of Computational Geometry 3, 1 (2012), 132\u2013153.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/10515.10534"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90044-5"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054196000105"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830916500518"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195916500059"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2021.101808"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1564499"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2022.101925"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34029-2_10"},{"key":"e_1_3_2_32_2","unstructured":"Itinerant Games. 2014. A 2D Procedural Galaxy with C++. Retrieved February 8 2023 from https:\/\/itinerantgames.tumblr.com\/post\/78592276402\/a-2d-procedural-galaxy-with-c."},{"issue":"2","key":"e_1_3_2_33_2","first-page":"3","article-title":"Degree four plane spanners: Simpler and better","volume":"8","author":"Kanj Iyad","year":"2017","unstructured":"Iyad Kanj, Ljubomir Perkovic, and Duru T\u00fcrko\u01e7lu. 2017. Degree four plane spanners: Simpler and better. Journal of Computational Geometry 8, 2 (2017), 3\u201331.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958035"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.05.027"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-014-9651-0"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195904001366"},{"key":"e_1_3_2_38_2","article-title":"Minimum Dilation Triangulations for the Regular n-Gon","author":"Mulzer Wolfgang","year":"2004","unstructured":"Wolfgang Mulzer. 2004. Minimum Dilation Triangulations for the Regular n-Gon. Master\u2019s Thesis. Freie Universit\u00e4t Berlin, Germany.","journal-title":"Master\u2019s Thesis. Freie Universit\u00e4t Berlin, Germany."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/586846.586967"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.5555\/1208237"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/945394.945400"},{"key":"e_1_3_2_42_2","volume-title":"CGAL User and Reference Manual (5.3 ed.)","author":"Project The CGAL","year":"2021","unstructured":"The CGAL Project. 2021. CGAL User and Reference Manual (5.3 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/5.3\/Manual\/packages.html."},{"key":"e_1_3_2_43_2","volume-title":"Handbook of Discrete and Computational Geometry","author":"Toth Csaba D.","year":"2017","unstructured":"Csaba D. Toth, Joseph O\u2019Rourke, and Jacob E. Goodman. 2017. Handbook of Discrete and Computational Geometry. Chapman & Hall\/CRC."},{"key":"e_1_3_2_44_2","unstructured":"TSP. 2022. Traveling Salesman Problem. Retrieved December 8 2022 from https:\/\/www.math.uwaterloo.ca\/tsp\/."},{"issue":"1","key":"e_1_3_2_45_2","first-page":"101","article-title":"Computing the maximum detour of a plane geometric graph in subquadratic time","volume":"1","author":"Wulff-Nilsen Christian","year":"2010","unstructured":"Christian Wulff-Nilsen. 2010. Computing the maximum detour of a plane geometric graph in subquadratic time. Journal of Computational Geometry 1, 1 (2010), 101\u2013122.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/110832458"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3582497","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3582497","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:50Z","timestamp":1750183730000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3582497"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,8]]},"references-count":45,"alternative-id":["10.1145\/3582497"],"URL":"https:\/\/doi.org\/10.1145\/3582497","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2023,4,8]]}}}