{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:42:31Z","timestamp":1787341351532,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["MU\/3501\/1"],"award-info":[{"award-number":["MU\/3501\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["1161"],"award-info":[{"award-number":["1161"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Let $P \\subset \\mathbb{R}^2$ be a planar $n$-point set such that each point $p \\in P$ has an associated radius $r_p &gt; 0$. The transmission graph $G$ for $P$ is the directed graph with vertex set $P$ such that for any $p, q \\in P$, there is an edge from $p$ to $q$ if and only if $d(p, q) \\leq r_p$. Let $t &gt; 1$ be a constant. A $t$-spanner for $G$ is a subgraph $H \\subseteq G$ with vertex set $P$ so that for any two vertices $p,q \\in P$, we have $d_H(p, q) \\leq t d_G(p, q)$, where $d_H$ and $d_G$ denote the shortest path distance in $H$ and $G$, respectively (with Euclidean edge lengths). We show how to compute a $t$-spanner for $G$ with $O(n)$ edges in $O(n (\\log n + \\log \\Psi))$ time, where $\\Psi$ is the ratio of the largest and smallest radius of a point in $P$. Using more advanced data structures, we obtain a construction that runs in $O(n \\log^5 n)$ time, independent of $\\Psi$. We give two applications for our spanners. First, we show how to use our spanner to find a BFS tree in $G$ from any given start vertex in $O(n \\log n)$ time (in addition to the time it takes to build the spanner). Second, we show how to use our spanner to extend a reachability oracle to answer geometric reachability queries. In a geometric reachability query we ask whether a vertex $p$ in $G$ can \u201creach\u201d a target $q$ which is an arbitrary point in the plane (rather than restricted to be another vertex $q$ of $G$ in a standard reachability query). Our spanner allows the reachability oracle to answer geometric reachability queries with an additive overhead of $O(\\log n\\log \\Psi)$ to the query time and $O(n \\log \\Psi)$ to the space.<\/jats:p>","DOI":"10.1137\/16m1059692","type":"journal-article","created":{"date-parts":[[2018,8,7]],"date-time":"2018-08-07T12:12:01Z","timestamp":1533643921000},"page":"1585-1609","source":"Crossref","is-referenced-by-count":5,"title":["Spanners for Directed Transmission Graphs"],"prefix":"10.1137","volume":"47","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1948-5840","authenticated-orcid":true,"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liam","family":"Roditty","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Seiferth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,7]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.21"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"M. de Berg, O. Cheong, M. van Kreveld, and M. H. Overmars,\n                      Computational Geometry: Algorithms and Applications\n                      , 3rd ed., Springer-Verlag, Berlin, Heidelberg, 2008.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195912600047"},{"key":"atypb4","unstructured":"A. Boukerche,\n                      Algorithms and Protocols for Wireless Sensor Networks\n                      , 1st ed., Wiley Series on Parallel and Distributed Computing, John Wiley and Sons, New York, 2009."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.12.003"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"atypb7","unstructured":"P. Carmi, 2014, personal communication."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706596"},{"key":"atypb9","unstructured":"T. M. Chan and K. A. Tsakalidis,\n                      Optimal deterministic algorithms for 2-d and 3-d shallow cuttings\n                      , in Proceedings of the 31st International Symposium on Computational Geometry (SoCG 2015), 2015, pp. 719-732."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90054-2"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"atypb12","first-page":"31","volume":"3","author":"F\u00fcrer M.","year":"2012","journal-title":"J. Comput. Geom."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"S. Har-Peled,\n                      Geometric Approximation Algorithms\n                      , Math. Surveys Monogr. 173, AMS, Providence, RI, 2011.","DOI":"10.1090\/surv\/173"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"J. Holm, E. Rotenberg, and M. Thorup,\n                      Planar reachability in linear space and constant time\n                      , in Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS), 2015, pp. 370-389.","DOI":"10.1109\/FOCS.2015.30"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/0214006"},{"key":"atypb16","unstructured":"H. Kaplan, W. Mulzer, L. Roditty, and P. Seiferth,\n                      Spanners and reachability oracles for directed transmission graphs\n                      , in Proceedings of the 31st International Symposium on Computational Geometry (SoCG), 2015, pp. 156-170."},{"key":"atypb17","unstructured":"H. Kaplan, W. Mulzer, L. Roditty, and P. Seiferth,\n                      Reachability Oracles for Directed Transmission Graphs\n                      , preprint,https:\/\/arxiv.org\/abs\/1601.07797, 2016."},{"key":"atypb18","first-page":"2495","author":"Kaplan H.","year":"2017","journal-title":"Philadelphia"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187683"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/110825698"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"G. Narasimhan and M. H. M. Smid,\n                      Geometric Spanner Networks\n                      , Cambridge University Press, Cambridge, 2007.","DOI":"10.1017\/CBO9780511546884"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/1807048.1807054"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and M. I. Shamos,\n                      Computational Geometry. An Introduction\n                      , Springer-Verlag, New York, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"atypb25","unstructured":"M. Sharir and P. K. Agarwal,\n                      Davenport-Schinzel Sequences and Their Geometric Applications\n                      , Cambridge University Press, Cambridge, 1995."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2008.926506"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/0211059"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1059692","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:14:48Z","timestamp":1787339688000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1059692"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1059692"],"URL":"https:\/\/doi.org\/10.1137\/16m1059692","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}