{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:41:55Z","timestamp":1777596115475,"version":"3.51.4"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T00:00:00Z","timestamp":1343779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["894\/09"],"award-info":[{"award-number":["894\/09"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:p>\n            The rules governing the availability and quality of connections in a wireless network are described by\n            <jats:italic>physical<\/jats:italic>\n            models such as the\n            <jats:italic>signal-to-interference &amp; noise ratio (SINR)<\/jats:italic>\n            model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a\n            <jats:italic>reception zone<\/jats:italic>\n            for each station, consisting of the points where its transmission is received correctly. The resulting\n            <jats:italic>SINR diagram<\/jats:italic>\n            partitions the plane into a reception zone per station and the remaining plane where no station can be heard.\n          <\/jats:p>\n          <jats:p>\n            SINR diagrams appear to be fundamental to understanding the behavior of wireless networks, and may play a key role in the development of suitable algorithms for such networks, analogous perhaps to the role played by Voronoi diagrams in the study of proximity queries and related issues in computational geometry. So far, however, the properties of SINR diagrams have not been studied systematically, and most algorithmic studies in wireless networking rely on simplified\n            <jats:italic>graph-based<\/jats:italic>\n            models such as the\n            <jats:italic>unit disk graph (UDG)<\/jats:italic>\n            model, which conveniently abstract away interference-related complications, and make it easier to handle algorithmic issues, but consequently fail to capture accurately some important aspects of wireless networks.\n          <\/jats:p>\n          <jats:p>This article focuses on obtaining some basic understanding of SINR diagrams, their properties and their usability in algorithmic applications. Specifically, we have shown that assuming uniform power transmissions, the reception zones are convex and relatively well-rounded. These results are then used to develop an efficient approximation algorithm for a fundamental point location problem in wireless networks.<\/jats:p>","DOI":"10.1145\/2339123.2339125","type":"journal-article","created":{"date-parts":[[2012,9,4]],"date-time":"2012-09-04T12:50:47Z","timestamp":1346763047000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["SINR Diagrams"],"prefix":"10.1145","volume":"59","author":[{"given":"Chen","family":"Avin","sequence":"first","affiliation":[{"name":"Ben Gurion University of the Negev"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Emek","sequence":"additional","affiliation":[{"name":"ETH Zurich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erez","family":"Kantor","sequence":"additional","affiliation":[{"name":"Technion"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zvi","family":"Lotker","sequence":"additional","affiliation":[{"name":"Ben Gurion University of the Negev"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liam","family":"Roditty","sequence":"additional","affiliation":[{"name":"Bar Ilan University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Agarwal P. and Erickson J. 1999. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry. American Mathematical Society 1--56. Agarwal P. and Erickson J. 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","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100260"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 28th Conference. of IEEE Computer and Communications Societies (INFOCOM).","author":"Andrews M.","unstructured":"Andrews , M. and Dinitz , M . 2009. Maximizing capacity in arbitrary wireless networks in the SINR model: Complexity and game theory . In Proceedings of the 28th Conference. of IEEE Computer and Communications Societies (INFOCOM). Andrews, M. and Dinitz, M. 2009. Maximizing capacity in arbitrary wireless networks in the SINR model: Complexity and game theory. In Proceedings of the 28th Conference. of IEEE Computer and Communications Societies (INFOCOM)."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 17th Annual Europe Symposium on Algorithms (ESA","author":"Avin C.","year":"2009","unstructured":"Avin , C. , Lotker , Z. , and Pignolet , Y . 2009. On the power of uniform power: Capacity of wireless networks with bounded resources . In Proceedings of the 17th Annual Europe Symposium on Algorithms (ESA 2009 ). 373--384. Avin, C., Lotker, Z., and Pignolet, Y. 2009. On the power of uniform power: Capacity of wireless networks with bounded resources. In Proceedings of the 17th Annual Europe Symposium on Algorithms (ESA 2009). 373--384."},{"key":"e_1_2_1_5_1","volume-title":"Nonlinear programming","author":"Bertsekas D.","unstructured":"Bertsekas , D. 1999. Nonlinear programming . Athena Scientific . Bertsekas, D. 1999. Nonlinear programming. Athena Scientific."},{"key":"e_1_2_1_6_1","volume-title":"Mobile and Wireless Networks","author":"Black U.","unstructured":"Black , U. 1996. Mobile and Wireless Networks . Prentice Hall . Black, U. 1996. Mobile and Wireless Networks. Prentice Hall."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90261-Y"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1288107.1288122"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 28th Conference of IEEE Computer and Communications Societies (INFOCOM). 1872--1880","author":"Goussevskaia O.","unstructured":"Goussevskaia , O. , Wattenhofer , R. , Halld\u00f3rsson , M. , and Welzl , E . 2009. Capacity of arbitrary wireless networks . In Proceedings of the 28th Conference of IEEE Computer and Communications Societies (INFOCOM). 1872--1880 . Goussevskaia, O., Wattenhofer, R., Halld\u00f3rsson, M., and Welzl, E. 2009. Capacity of arbitrary wireless networks. In Proceedings of the 28th Conference of IEEE Computer and Communications Societies (INFOCOM). 1872--1880."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.825799"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_33"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_44"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/941079.941089"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 2011 INFOCOM. IEEE, 2525--2533","author":"Lotker Z.","unstructured":"Lotker , Z. , Parter , M. , Peleg , D. , and Pignolet , Y . 2011. Distributed power control in the SINR model . In Proceedings of the 2011 INFOCOM. IEEE, 2525--2533 . Lotker, Z., Parter, M., Peleg, D., and Pignolet, Y. 2011. Distributed power control in the SINR model. In Proceedings of the 2011 INFOCOM. IEEE, 2525--2533."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236360.1236362"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM","author":"Moscibroda T.","year":"2006","unstructured":"Moscibroda , T. and Wattenhofer , R . 2006. The complexity of connectivity in wireless networks . In Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM 2006 ). IEEE, 1--13. Moscibroda, T. and Wattenhofer, R. 2006. The complexity of connectivity in wireless networks. In Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM 2006). IEEE, 1--13."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 5th Workshop on Hot Topics in Networks (HOTNETS).","author":"Moscibroda T.","unstructured":"Moscibroda , T. , Wattenhofer , R. , and Weber , Y . 2006a. Protocol design beyond graph-based models . In Proceedings of the 5th Workshop on Hot Topics in Networks (HOTNETS). Moscibroda, T., Wattenhofer, R., and Weber, Y. 2006a. Protocol design beyond graph-based models. In Proceedings of the 5th Workshop on Hot Topics in Networks (HOTNETS)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132905.1132939"},{"key":"e_1_2_1_21_1","unstructured":"Pahlavan K. and Levesque A. 1995. Wireless information networks. Vol. 95. Wiley Online Library. Pahlavan K. and Levesque A. 1995. Wireless information networks . Vol. 95. Wiley Online Library."},{"key":"e_1_2_1_22_1","volume-title":"Wireless Communications-Principles and Practice","author":"Rappaport T. S.","unstructured":"Rappaport , T. S. 1996. Wireless Communications-Principles and Practice . Prentice-Hall . Rappaport, T. S. 1996. Wireless Communications-Principles and Practice. Prentice-Hall."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2005.65"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2339123.2339125","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2339123.2339125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:21:08Z","timestamp":1750238468000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2339123.2339125"}},"subtitle":["Convexity and Its Applications in Wireless Networks"],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1145\/2339123.2339125"],"URL":"https:\/\/doi.org\/10.1145\/2339123.2339125","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}