{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T18:28:55Z","timestamp":1778783335220,"version":"3.51.4"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2016,11,2]],"date-time":"2016-11-02T00:00:00Z","timestamp":1478044800000},"content-version":"vor","delay-in-days":366,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","award":["2008348"],"award-info":[{"award-number":["2008348"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Israel Ministry of Science and Technology"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["894\/09"],"award-info":[{"award-number":["894\/09"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006461","name":"Citi Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006461","id-type":"DOI","asserted-by":"crossref"}]},{"name":"I-CORE program of the Israel PBC and ISF","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}]},{"DOI":"10.13039\/100000181","name":"AFOSR","doi-asserted-by":"crossref","award":["FA9550-13-1-0042 and FA9550-14-1-0403"],"award-info":[{"award-number":["FA9550-13-1-0042 and FA9550-14-1-0403"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["0939370-CCF, CCF-1217506 and CCF-AF-0937274"],"award-info":[{"award-number":["0939370-CCF, CCF-1217506 and CCF-AF-0937274"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,11,2]]},"abstract":"<jats:p>\n                    This article studies the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multistation network, we use the convenient representation of a reception map, which partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard.\n                    <jats:italic toggle=\"yes\">SINR diagrams<\/jats:italic>\n                    have been studied in Avin et al. [2009] for the specific case where all stations use the same power. It was shown that the reception zones are convex (hence connected) and fat, and this was used to devise an efficient algorithm for the fundamental problem of point location. Here we consider the more general (and common) case where transmission energies are arbitrary (or nonuniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques for the nonuniform setting, as well as the theoretical challenge of understanding the geometry of SINR diagrams (e.g., the maximal number of connected components they might have). Our key result exhibits a striking contrast between\n                    <jats:italic toggle=\"yes\">d<\/jats:italic>\n                    - and (\n                    <jats:italic toggle=\"yes\">d<\/jats:italic>\n                    +1)-dimensional maps for a network embedded in\n                    <jats:italic toggle=\"yes\">d<\/jats:italic>\n                    -dimensional space. Specifically, it is shown that whereas the\n                    <jats:italic toggle=\"yes\">d<\/jats:italic>\n                    -dimensional map might be highly fractured, drawing the map in one dimension higher \u201cheals\u201d the zones, which become connected (in fact, hyperbolically connected). We also provide bounds for the fatness of reception zones. Subsequently, we consider algorithmic applications and propose a new variant of approximate point location.\n                  <\/jats:p>","DOI":"10.1145\/2807693","type":"journal-article","created":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T12:09:35Z","timestamp":1446466175000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["The Topology of Wireless Communication"],"prefix":"10.1145","volume":"62","author":[{"given":"Erez","family":"Kantor","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zvi","family":"Lotker","sequence":"additional","affiliation":[{"name":"Ben Gurion University, Beer-Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Merav","family":"Parter","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal and J. Erickson. 1999. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry. American Mathematical Society 1--56.","DOI":"10.1090\/conm\/223\/03131"},{"key":"e_1_2_1_2_1","unstructured":"B. Aronov and M. J. Katz. 2014. Batched point location in SINR diagrams via algebraic tools. CoRR abs\/1412.0962 (2014). http:\/\/arxiv.org\/abs\/1412.0962."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(84)90064-5"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582750"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339123.2339125"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1561\/1300000006"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1197095"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.883617"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1561\/1300000009"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 22th Conference on IEEE Computer and Communications Societies (INFOCOM).","author":"Cruz R. L.","unstructured":"R. L. Cruz and A. V. Santhanam. 2003. Optimal routing, link scheduling and power control in multi-hop wireless networks. In Proceedings of the 22th Conference on IEEE Computer and Communications Societies (INFOCOM)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdm012"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/993515"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/1300000019"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133155"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","unstructured":"E. Kantor Z. Lotker M. Parter and D. Peleg. 2011. The topology of wireless communication. arXiv: 1103.4566. http:\/\/arxiv.org\/abs\/1103.4566. 10.1145\/1993636.1993688","DOI":"10.1145\/1993636.1993688"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133156"},{"key":"e_1_2_1_17_1","article-title":"Downlink power control algorithms for cellular radio systems","author":"Lee T.-H.","year":"1995","unstructured":"T.-H. Lee, J.-C. Lin, and Y. T. Su. 1995. Downlink power control algorithms for cellular radio systems. IEEE Trans. Vehic. Technol. 44, (Feb. 1995), 89--94.","journal-title":"IEEE Trans. Vehic. Technol. 44"},{"key":"e_1_2_1_18_1","volume-title":"A Treatise on Electricity and Magnetism","author":"Maxwell J. C.","unstructured":"J. C. Maxwell. 1954. A Treatise on Electricity and Magnetism. Vol. 1, Dover, New York."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1964-0161339-9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236360.1236362"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 26th INFOCOM.","author":"Moscibroda T.","unstructured":"T. Moscibroda, Y. Oswald, and R. Wattenhofer. 2007. How optimal are wireless scheduling protocols? In Proceedings of the 26th INFOCOM."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 25th INFOCOM.","author":"Moscibroda T.","unstructured":"T. Moscibroda and R. Wattenhofer. 2006. The complexity of connectivity in wireless networks. In Proceedings of the 25th INFOCOM."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 5th HOTNETS.","author":"Moscibroda T.","unstructured":"T. Moscibroda, R. Wattenhofer, and Y. Weber. 2006. Protocol design beyond graph-based models. In Proceedings of the 5th HOTNETS."},{"key":"e_1_2_1_24_1","volume-title":"Integral Geometry and Geometric Probability","author":"Santal\u00f3 L. A.","unstructured":"L. A. Santal\u00f3. 2004. Integral Geometry and Geometric Probability. Cambridge University Press."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"R. Thom. 1965. Sur l'homologie des variets algbriques relles. Diff. Comb. Topol. (1965).","DOI":"10.1515\/9781400874842-016"},{"key":"e_1_2_1_26_1","volume-title":"Three-Dimensional Geometry and Topology","author":"Thurston W. P.","unstructured":"W. P. Thurston. 1997. Three-Dimensional Geometry and Topology. Princeton University Press."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","unstructured":"D. Tse and P. Viswanath. 2005. Fundamentals of Wireless Communication. Cambridge University Press.","DOI":"10.5555\/1111206"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/242072.242940"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1155\/ASP.2005.144"},{"key":"e_1_2_1_30_1","volume-title":"Mathematica Edition: Version 8.0. Wolfram Research","year":"2010","unstructured":"Wolfram. 2010. Mathematica Edition: Version 8.0. Wolfram Research, Inc., Champaign, IL."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/25.120145"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2807693","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2807693","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2807693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:37:24Z","timestamp":1763458644000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2807693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,11,2]]}},"alternative-id":["10.1145\/2807693"],"URL":"https:\/\/doi.org\/10.1145\/2807693","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,2]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-07-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}