{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:23:48Z","timestamp":1787505828981,"version":"build-2736575974"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,8,9]],"date-time":"2018-08-09T00:00:00Z","timestamp":1533772800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-11-17336,CCF-12-18791,CCF-15-40656"],"award-info":[{"award-number":["CCF-11-17336,CCF-12-18791,CCF-15-40656"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","award":["2014\/170"],"award-info":[{"award-number":["2014\/170"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001742","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1045\/10,1884\/16"],"award-info":[{"award-number":["1045\/10,1884\/16"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"<jats:p>\n                    The\n                    <jats:italic>SINR (Signal to Interference plus Noise Ratio) model<\/jats:italic>\n                    for the quality of wireless connections has been the subject of extensive recent study. It attempts to predict whether a particular transmitter is heard at a specific location, in a setting consisting of\n                    <jats:italic>n<\/jats:italic>\n                    simultaneous transmitters and background noise. The SINR model gives rise to a natural geometric object, the\n                    <jats:italic>SINR diagram<\/jats:italic>\n                    , which partitions the space into\n                    <jats:italic>n<\/jats:italic>\n                    regions where each of the transmitters can be heard and the remaining space where no transmitter can be heard.\n                  <\/jats:p>\n                  <jats:p>\n                    Efficient\n                    <jats:italic>point location<\/jats:italic>\n                    in the SINR diagram, i.e., being able to build a data structure that facilitates determining, for a query point, whether any transmitter is heard there, and if so, which one, has been recently investigated in several articles. These planar data structures are constructed in time at least quadratic in\n                    <jats:italic>n<\/jats:italic>\n                    and support logarithmic-time approximate queries. Moreover, the performance of some of the proposed structures depends strongly not only on the number\n                    <jats:italic>n<\/jats:italic>\n                    of transmitters and on the approximation parameter\n                    <jats:italic>\u03b5<\/jats:italic>\n                    , but also on some geometric parameters that cannot be bounded\n                    <jats:italic>a priori<\/jats:italic>\n                    as a function of\n                    <jats:italic>n<\/jats:italic>\n                    or\n                    <jats:italic>\u03b5<\/jats:italic>\n                    .\n                  <\/jats:p>\n                  <jats:p>\n                    In this article, we address the question of\n                    <jats:italic>batched<\/jats:italic>\n                    point location queries, i.e., answering many queries simultaneously. Specifically, in one dimension, we can answer\n                    <jats:italic>n<\/jats:italic>\n                    queries\n                    <jats:italic>exactly<\/jats:italic>\n                    in amortized polylogarithmic time per query, while in the plane we can do it approximately.\n                  <\/jats:p>\n                  <jats:p>\n                    In another result, we show how to answer\n                    <jats:italic>n<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    queries\n                    <jats:italic>exactly<\/jats:italic>\n                    in amortized polylogarithmic time per query, assuming the queries are located on a possibly non-uniform\n                    <jats:italic>n<\/jats:italic>\n                    \u00d7\n                    <jats:italic>n<\/jats:italic>\n                    grid.\n                  <\/jats:p>\n                  <jats:p>\n                    All these results can handle\n                    <jats:italic>arbitrary<\/jats:italic>\n                    power assignments to the transmitters. Moreover, the amortized query time in these results depends only on\n                    <jats:italic>n<\/jats:italic>\n                    and\n                    <jats:italic>\u03b5<\/jats:italic>\n                    .\n                  <\/jats:p>\n                  <jats:p>We also show how to speed up the preprocessing in a previously proposed point-location structure in SINR diagram for uniform-power sites, by almost a full order of magnitude. For this, we obtain results on the sensitivity of the reception regions to slight changes in the reception threshold, which are of independent interest.<\/jats:p>\n                  <jats:p>Finally, these results demonstrate the (so far underutilized) power of combining algebraic tools with those of computational geometry and other fields.<\/jats:p>","DOI":"10.1145\/3209678","type":"journal-article","created":{"date-parts":[[2018,8,13]],"date-time":"2018-08-13T08:29:41Z","timestamp":1534148981000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Batched Point Location in SINR Diagrams via Algebraic Tools"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3110-4702","authenticated-orcid":false,"given":"Boris","family":"Aronov","sequence":"first","affiliation":[{"name":"New York University, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beer-Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394893.2394955"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM\u201909)","author":"Andrews M.","unstructured":"M. Andrews and M. Dinitz. 2009. Maximizing capacity in arbitrary wireless networks in the SINR model: Complexity and game theory. In Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM\u201909). 1332--1340."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of Automata, Languages, and Programming\u201442nd International Colloquium (ICALP\u201915)","author":"Aronov Boris","year":"2014","unstructured":"Boris Aronov and Matthew J. Katz. 2015. Batched point location in SINR diagrams via algebraic tools. In Proceedings of Automata, Languages, and Programming\u201442nd International Colloquium (ICALP\u201915), Part I. 65--77. See also arXiv:1412.0962 {cs.CG}, 2014."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of Algorithms for Sensor Systems\u201410th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS\u201914)","author":"Aschner Rom","unstructured":"Rom Aschner, Gui Citovsky, and Matthew J. Katz. 2014. Exploiting geometry in the SINRk model. In Proceedings of Algorithms for Sensor Systems\u201410th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS\u201914). 125--135."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90055-4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(84)90064-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Franz Aurenhammer Rolf Klein and D.-T. Lee. 2013. Voronoi Diagrams and Delaunay Triangulations. World Scientific. http:\/\/www.worldscientific.com\/worldscibooks\/10.1142\/8685.","DOI":"10.5555\/2563475"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/3034197.3034361"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339123.2339125"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/184671"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2805882.2806035"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM\u201909). 1872","author":"Goussevskaia O.","year":"1880","unstructured":"O. Goussevskaia, M. M. Halld\u00f3rsson, R. Wattenhofer, and E. Welzl. 2009. Capacity of arbitrary wireless networks. In Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM\u201909). 1872--1880."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1288107.1288122"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.825799"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2390176.2390183"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133155"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_44"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/140959067"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993688"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133156"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1814370.1814391"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847257"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM\u201906)","author":"Moscibroda T.","unstructured":"T. Moscibroda and R. Wattenhofer. 2006. The complexity of connectivity in wireless networks. In Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM\u201906). 25--37."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_49"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1994.1042"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","unstructured":"M. Sharir and P. K. Agarwal. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press New York. http:\/\/us.cambridge.org\/titles\/catalogue.asp?isbn=0521470250.","DOI":"10.5555\/235229"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/304952"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03417-6_17"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45078-8_13"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209678","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209678","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209678","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:39:33Z","timestamp":1750196373000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209678"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,9]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3209678"],"URL":"https:\/\/doi.org\/10.1145\/3209678","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,9]]},"assertion":[{"value":"2017-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}