{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:09:16Z","timestamp":1757617756164,"version":"3.44.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T00:00:00Z","timestamp":1744761600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T00:00:00Z","timestamp":1744761600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP240101353"],"award-info":[{"award-number":["DP240101353"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100018694","name":"HORIZON EUROPE Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["101146276"],"award-info":[{"award-number":["101146276"]}],"id":[{"id":"10.13039\/100018694","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001774","name":"University of Sydney","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001774","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed using an equilateral triangle, a square, or a regular hexagon. However, all other shapes have remained elusive. In this paper, we extend the restricted class of spanners for which tight bounds are known. We prove that Delaunay triangulations constructed using rectangles with aspect ratio <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$A$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>A<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> have spanning ratio at most <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\sqrt{2} \\sqrt{1+A^2 + A\\sqrt{A^2 + 1}}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msqrt>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msqrt>\n                    <mml:msqrt>\n                      <mml:mrow>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:msup>\n                          <mml:mi>A<\/mml:mi>\n                          <mml:mn>2<\/mml:mn>\n                        <\/mml:msup>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mi>A<\/mml:mi>\n                        <mml:msqrt>\n                          <mml:mrow>\n                            <mml:msup>\n                              <mml:mi>A<\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:msqrt>\n                      <\/mml:mrow>\n                    <\/mml:msqrt>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, which matches the known lower bound.<\/jats:p>","DOI":"10.1007\/s00453-025-01308-w","type":"journal-article","created":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T08:42:15Z","timestamp":1744792935000},"page":"1060-1080","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Tight Spanning Ratio of the Rectangle Delaunay Triangulation"],"prefix":"10.1007","volume":"87","author":[{"given":"Andr\u00e9","family":"van Renssen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuan","family":"Sha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yucheng","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sampson","family":"Wong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,16]]},"reference":[{"key":"1308_CR1","unstructured":"van Renssen, A., Sha, Y., Sun, Y., Wong, S.: The tight spanning ratio of the rectangle Delaunay triangulation. In: Proceedings of the 31st European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics, vol. 274, pp. 99\u201319915 (2023)"},{"key":"1308_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)"},{"issue":"7","key":"1308_CR3","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1016\/j.comgeo.2013.04.002","volume":"46","author":"P Bose","year":"2013","unstructured":"Bose, P., Smid, M.: On plane geometric spanners: a survey and open problems. Comput. Geom. Theory Appl. 46(7), 818\u2013830 (2013)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"1","key":"1308_CR4","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/BF02187801","volume":"5","author":"DP Dobkin","year":"1990","unstructured":"Dobkin, D.P., Friedman, S.J., Supowit, K.J.: Delaunay graphs are almost as good as complete graphs. Discrete Comput. Geomet. (DCG) 5(1), 399\u2013407 (1990)","journal-title":"Discrete Comput. Geomet. (DCG)"},{"issue":"1","key":"1308_CR5","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF02187821","volume":"7","author":"JM Keil","year":"1992","unstructured":"Keil, J.M., Gutwin, C.A.: Classes of graphs which approximate the complete Euclidean graph. Discrete Comput. Geomet. (DCG) 7(1), 13\u201328 (1992)","journal-title":"Discrete Comput. Geomet. (DCG)"},{"issue":"4","key":"1308_CR6","doi-asserted-by":"publisher","first-page":"1620","DOI":"10.1137\/110832458","volume":"42","author":"G Xia","year":"2013","unstructured":"Xia, G.: The stretch factor of the Delaunay triangulation is less than 1.998. SIAM J. Comput. (SICOMP) 42(4), 1620\u20131659 (2013)","journal-title":"SIAM J. Comput. (SICOMP)"},{"issue":"2","key":"1308_CR7","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.comgeo.2010.09.009","volume":"44","author":"P Bose","year":"2011","unstructured":"Bose, P., Devroye, L., L\u00f6ffler, M., Snoeyink, J., Verma, V.: Almost all Delaunay triangulations have stretch factor greater than $$\\pi $$\/2. Comput. Geom. Theory Appl. 44(2), 121\u2013127 (2011)","journal-title":"Comput. Geom. Theory Appl."},{"key":"1308_CR8","unstructured":"Xia, G., Zhang, L.: Toward the tight bound of the stretch factor of Delaunay triangulations. In: Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), pp. 175\u2013180 (2011)"},{"issue":"3","key":"1308_CR9","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF02187695","volume":"1","author":"D-T Lee","year":"1986","unstructured":"Lee, D.-T., Lin, A.K.: Generalized Delaunay triangulation for planar graphs. Discrete Comput. Geomet. (DCG) 1(3), 201\u2013217 (1986)","journal-title":"Discrete Comput. Geomet. (DCG)"},{"issue":"1","key":"1308_CR10","first-page":"41","volume":"1","author":"P Bose","year":"2010","unstructured":"Bose, P., Carmi, P., Collette, S., Smid, M.: On the stretch factor of convex Delaunay graphs. J. Comput. Geomet. (JoCG) 1(1), 41\u201356 (2010)","journal-title":"J. Comput. Geomet. (JoCG)"},{"issue":"2","key":"1308_CR11","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"LP Chew","year":"1989","unstructured":"Chew, L.P.: There are planar graphs almost as good as the complete graph. J Comput Syst Sci (JCSS) 39(2), 205\u2013219 (1989)","journal-title":"J Comput Syst Sci (JCSS)"},{"key":"1308_CR12","doi-asserted-by":"crossref","unstructured":"Chew, L.P.: There is a planar graph almost as good as the complete graph. In: Proceedings of the 2nd Annual Symposium on Computational Geometry (SoCG), pp. 169\u2013177 (1986)","DOI":"10.1145\/10515.10534"},{"issue":"3","key":"1308_CR13","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/j.comgeo.2014.10.005","volume":"48","author":"N Bonichon","year":"2015","unstructured":"Bonichon, N., Gavoille, C., Hanusse, N., Perkovi\u0107, L.: Tight stretch factors for $${L}_1$$- and $${L}_{\\infty }$$-Delaunay triangulations. Comput. Geom. Theory Appl. (CGTA) 48(3), 237\u2013250 (2015)","journal-title":"Comput. Geom. Theory Appl. (CGTA)"},{"issue":"2","key":"1308_CR14","first-page":"86","volume":"12","author":"L Perkovi\u0107","year":"2021","unstructured":"Perkovi\u0107, L., Dennis, M., T\u00fcrko\u011flu, D.: The stretch factor of hexagon-Delaunay triangulations. J. Comput. Geomet. (JoCG) 12(2), 86\u2013125 (2021)","journal-title":"J. Comput. Geomet. (JoCG)"},{"key":"1308_CR15","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.comgeo.2018.06.006","volume":"74","author":"P Bose","year":"2018","unstructured":"Bose, P., De Carufel, J.-L., van Renssen, A.: Constrained generalized Delaunay graphs are plane spanners. Comput. Geom. Theory Appl. (CGTA) 74, 50\u201365 (2018)","journal-title":"Comput. Geom. Theory Appl. (CGTA)"},{"key":"1308_CR16","doi-asserted-by":"crossref","unstructured":"Bonichon, N., Bose, P., De Carufel, J.-L., Despr\u00e9, V., Hill, D., Smid, M.: Improved routing on the Delaunay triangulation. Discrete Comput. Geomet. (DCG) (2023)","DOI":"10.1007\/s00454-023-00499-9"},{"issue":"2","key":"1308_CR17","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/s00454-016-9842-y","volume":"58","author":"N Bonichon","year":"2017","unstructured":"Bonichon, N., Bose, P., De Carufel, J.-L., Perkovi\u0107, L., van Renssen, A.: Upper and lower bounds for online routing on Delaunay triangulations. Discrete Comput. Geomet. (DCG) 58(2), 482\u2013504 (2017)","journal-title":"Discrete Comput. Geomet. (DCG)"},{"issue":"6","key":"1308_CR18","doi-asserted-by":"publisher","first-page":"1626","DOI":"10.1137\/140988103","volume":"44","author":"P Bose","year":"2015","unstructured":"Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S.: Optimal local routing on Delaunay triangulations defined by empty equilateral triangles. SIAM J. Comput. (SICOMP) 44(6), 1626\u20131649 (2015)","journal-title":"SIAM J. Comput. (SICOMP)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01308-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01308-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01308-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T10:58:17Z","timestamp":1757156297000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01308-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,16]]},"references-count":18,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["1308"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01308-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,4,16]]},"assertion":[{"value":"18 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}