{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T12:10:10Z","timestamp":1791115810878,"version":"4.1.0"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We present a deterministic local routing algorithm that is guaranteed to find a path between any pair of vertices in a half-$\\theta_6$-graph (the half-$\\theta_6$-graph is equivalent to the Delaunay triangulation where the empty region is an equilateral triangle). The length of the path is at most $5\/\\sqrt{3} \\approx 2.887$ times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing algorithm can achieve a better routing ratio, thereby proving that our routing algorithm is optimal. This is somewhat surprising because the spanning ratio of the half-$\\theta_6$-graph is 2, meaning that even though there always exists a path whose length is at most twice the Euclidean distance, we cannot always find such a path when routing locally. Since every triangulation can be embedded in the plane as a half-$\\theta_6$-graph using $O(\\log n)$ bits per vertex coordinate via Schnyder's embedding scheme [W. Schnyder, Embedding planar graphs on the grid, in Proceedings of the 1st Annual ACM--SIAM Symposium on Discrete Algorithms (SODA 1990), ACM, New York, SIAM, Philadelphia, 1990, pp. 138--148], our result provides a competitive local routing algorithm for every such embedded triangulation. Finally, we show how our routing algorithm can be adapted to provide a routing ratio of $15\/\\sqrt{3} \\approx 8.660$ on two bounded degree subgraphs of the half-$\\theta_6$-graph.<\/jats:p>","DOI":"10.1137\/140988103","type":"journal-article","created":{"date-parts":[[2015,11,3]],"date-time":"2015-11-03T13:56:26Z","timestamp":1446558986000},"page":"1626-1649","source":"Crossref","is-referenced-by-count":22,"title":["Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles"],"prefix":"10.1137","volume":"44","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Fagerberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e9","family":"van Renssen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sander","family":"Verdonschot","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,11,3]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00197"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1054"},{"key":"atypb3","first-page":"19","volume":"6","author":"Barba L.","year":"2015","journal-title":"J. Comput. Geom."},{"key":"atypb4","first-page":"266","author":"Bonichon N.","year":"2010","journal-title":"Berlin"},{"key":"atypb5","first-page":"19","author":"Bonichon N.","year":"2010","journal-title":"Berlin"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1142\/S021819590200089X"},{"key":"atypb7","first-page":"305","author":"Bose P.","year":"2012","journal-title":"Canada"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369387"},{"key":"atypb9","first-page":"182","author":"Bose P.","year":"2013","journal-title":"Berlin"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90044-5"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9235-6"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90210-O"},{"key":"atypb13","first-page":"781","author":"Goodrich M. T.","year":"2009","journal-title":"Berlin"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.01.017"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9682-y"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187821"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9227-6"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"S. Mishra, I. Woungang, and S. C. Misra, eds.\n                      Guide to Wireless Sensor Networks\n                      , Springer, Berlin, 2009.","DOI":"10.1007\/978-1-84882-218-4"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.06.022"},{"key":"atypb20","first-page":"419","author":"R\u00e4cke H.","year":"2009","journal-title":"Berlin"},{"key":"atypb21","first-page":"138","author":"Schnyder W.","year":"1990","journal-title":"Philadelphia"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140988103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:48:36Z","timestamp":1787338116000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140988103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":21,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140988103"],"URL":"https:\/\/doi.org\/10.1137\/140988103","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}