{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:24:04Z","timestamp":1787340244685,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1884\/16"],"award-info":[{"award-number":["1884\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-11-17336"],"award-info":[{"award-number":["CCF-11-17336"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-12-18791"],"award-info":[{"award-number":["CCF-12-18791"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-15-40656"],"award-info":[{"award-number":["CCF-15-40656"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2014\/170"],"award-info":[{"award-number":["2014\/170"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We consider a set of transmitters broadcasting simultaneously on the same frequency under the signal to interference plus noise ratio (SINR) model. Transmission power may vary from one transmitter to another, and a transmitter's signal strength at a given point is modeled by the transmitter's power divided by some constant power $\\alpha$ of the distance it traveled. Roughly, a receiver at a given location can hear a specific transmitter only if the transmitter's signal is stronger by a specified ratio than the signals of all other transmitters combined. An SINR query is to determine whether a receiver at a given location can hear any transmitter, and if yes, which one. An approximate answer to an SINR query is such that one gets a definite yes or definite no, when the ratio between the strongest signal and all other signals combined is well above or well below the reception threshold, while the answer in the intermediate range is allowed to be either yes or no. We describe compact data structures that support approximate SINR queries in the plane in a dynamic context, i.e., where transmitters may be inserted and deleted over time. We distinguish between two main variants---uniform power and nonuniform power. In both variants the preprocessing time is $O(n\\,{polylog} n)$ and the amortized update time is $O({\\rm polylog} n)$, while the query time is $O({polylog} n)$ for uniform power, and randomized time $O(\\sqrt{n}\\,{polylog} n)$ with high probability for nonuniform power. Finally, we observe that in the static context the latter data structure can be implemented differently, so that the query time is also $O({polylog} n)$, thus significantly improving all previous results for this problem.<\/jats:p>","DOI":"10.1137\/19m128733x","type":"journal-article","created":{"date-parts":[[2020,12,14]],"date-time":"2020-12-14T10:39:14Z","timestamp":1607942354000},"page":"1271-1290","source":"Crossref","is-referenced-by-count":0,"title":["Resolving SINR Queries in a Dynamic Setting"],"prefix":"10.1137","volume":"49","author":[{"given":"Boris","family":"Aronov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gali","family":"Bar-On","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,12,14]]},"reference":[{"key":"atypb1","first-page":"355","author":"Abdelkader A.","year":"2019","journal-title":"Philadelphia"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9177-z"},{"key":"atypb3","first-page":"809","author":"Agarwal P. K.","year":"2004","journal-title":"Chapman and Hall\/CRC"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/3209678"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2016.08.003"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/2339123.2339125"},{"key":"atypb7","first-page":"1","author":"Chan T. M.","year":"2019","journal-title":"OR"},{"key":"atypb8","unstructured":"T. M. Chan,\n                      Private communication\n                      , September 2019."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"atypb10","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, 2008,http:\/\/www.cs.uu.nl\/geobook\/.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/140959067"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.08.007"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"E. Kantor, Z. Lotker, M. Parter, and D. Peleg,\n                      The topology of wireless communication\n                      , in Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011, pp. 383-392,https:\/\/doi.acm.org\/10.1145\/1993636.1993688.","DOI":"10.1145\/1993636.1993688"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"E. Kantor, Z. Lotker, M. Parter, and D. Peleg,\n                      Nonuniform SINR+Voroni diagrams are effectively uniform\n                      , in Proceedings of the 29th International Symposium on Distributed Computing, 2015, pp. 588-601,https:\/\/doi.org\/10.1007\/978-3-662-48653-5_39.","DOI":"10.1007\/978-3-662-48653-5_39"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"H. Kaplan, W. Mulzer, L. Roditty, P. Seiferth, and M. Sharir,\n                      Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications\n                      , in Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 2495-2504,https:\/\/doi.org\/10.1137\/1.9781611974782.165.","DOI":"10.1137\/1.9781611974782.165"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293051"},{"key":"atypb17","unstructured":"W. Mulzer,\n                      Private communication\n                      , September 2019."},{"key":"atypb18","unstructured":"M. H. Overmars,\n                      The Design of Dynamic Data Structures\n                      , Lecture Notes in Comput. Sci. 156, Springer-Verlag, Heidelberg, 1983."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90093-4"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3839"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M128733X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:26:37Z","timestamp":1787336797000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M128733X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/19M128733X"],"URL":"https:\/\/doi.org\/10.1137\/19m128733x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}