{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:40Z","timestamp":1760202580054},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"1-2","license":[{"start":{"date-parts":[[2009,3,1]],"date-time":"2009-03-01T00:00:00Z","timestamp":1235865600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:p>Random geometric graphs have been one of the fundamental models for reasoning about wireless networks: one places <jats:italic>n<\/jats:italic> points at random in a region of the plane (typically a square or circle), and then connects pairs of points by an edge if they are within a fixed distance of one another. In addition to giving rise to a range of basic theoretical questions, this class of random graphs has been a central analytical tool in the wireless networking community.<\/jats:p><jats:p>For many of the primary applications of wireless networks, however, the underlying environment has a large number of obstacles, and communication can only take place among nodes when they are close in space <jats:italic>and<\/jats:italic> when they have line-of-sight access to one another \u2013 consider, for example, urban settings or large indoor environments. In such domains, the standard model of random geometric graphs is not a good approximation of the true constraints, since it is not designed to capture the line-of-sight restrictions.<\/jats:p><jats:p>Here we propose a random-graph model incorporating both range limitations and line-of-sight constraints, and we prove asymptotically tight results for <jats:italic>k<\/jats:italic>-connectivity. Specifically, we consider points placed randomly on a grid (or torus), such that each node can see up to a fixed distance along the row and column it belongs to. (We think of the rows and columns as \u2018streets\u2019 and \u2018avenues\u2019 among a regularly spaced array of obstructions.) Further, we show that when the probability of node placement is a constant factor larger than the threshold for connectivity, near-shortest paths between pairs of nodes can be found, with high probability, by an algorithm using only local information. In addition to analysing connectivity and <jats:italic>k<\/jats:italic>-connectivity, we also study the emergence of a giant component, as well an approximation question, in which we seek to connect a set of given nodes in such an environment by adding a small set of additional \u2018relay\u2019 nodes.<\/jats:p>","DOI":"10.1017\/s0963548308009334","type":"journal-article","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T10:57:38Z","timestamp":1218538658000},"page":"145-163","source":"Crossref","is-referenced-by-count":15,"title":["Line-of-Sight Networks"],"prefix":"10.1017","volume":"18","author":[{"given":"ALAN","family":"FRIEZE","sequence":"first","affiliation":[]},{"given":"JON","family":"KLEINBERG","sequence":"additional","affiliation":[]},{"given":"R.","family":"RAVI","sequence":"additional","affiliation":[]},{"given":"WARREN","family":"DEBANY","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2009,3,1]]},"reference":[{"key":"S0963548308009334_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01060430"},{"key":"S0963548308009334_ref16","doi-asserted-by":"publisher","DOI":"10.1109\/18.825799"},{"key":"S0963548308009334_ref13","doi-asserted-by":"crossref","unstructured":"[13] Goel A. , Rai S. and Krishnamachari B. (2004) Sharp thresholds for monotone properties in random geometric graphs. In Proc. ACM Symposium on Theory of Computing, pp. 580\u2013586.","DOI":"10.1145\/1007352.1007441"},{"key":"S0963548308009334_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01198162"},{"key":"S0963548308009334_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02897056"},{"key":"S0963548308009334_ref8","unstructured":"[8] Efrat A. and Har-Peled S. (2002) Locating guards in art galleries. In 2nd IFIP International Conference on Theoretical Computer Science, pp. 181\u2013192."},{"key":"S0963548308009334_ref22","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"S0963548308009334_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03981-6"},{"key":"S0963548308009334_ref5","unstructured":"[5] Bollob\u00e1s B. , Janson S. and Riordan O. Line-of-sight percolation. Combin. Probab. Comput., this issue."},{"key":"S0963548308009334_ref24","doi-asserted-by":"crossref","unstructured":"[24] Royer E. and Toh C.-K. (1999) A review of current routing protocols for ad-hoc mobile wireless networks. IEEE Personal Communications, April 1999.","DOI":"10.1109\/98.760423"},{"key":"S0963548308009334_ref9","doi-asserted-by":"crossref","unstructured":"[9] Efrat A. , Har-Peled S. and Mitchell J. S. B. (2005) Approximation algorithms for two optimal location problems in sensor networks. In Broadnets 2005, pp. 767\u2013776.","DOI":"10.1109\/ICBN.2005.1589677"},{"key":"S0963548308009334_ref3","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/47.4.432"},{"key":"S0963548308009334_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548308009334_ref2","doi-asserted-by":"crossref","unstructured":"[2] Bettstetter C. (2002) On the minimum node degree and connectivity of a wireless multihop network. In Proc. 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '02), pp. 80\u201391.","DOI":"10.1145\/513800.513811"},{"key":"S0963548308009334_ref12","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1023"},{"key":"S0963548308009334_ref19","doi-asserted-by":"publisher","DOI":"10.1109\/65.967595"},{"key":"S0963548308009334_ref15","first-page":"547","volume-title":"Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming","author":"Gupta","year":"1998"},{"key":"S0963548308009334_ref20","unstructured":"[20] Mobile ad-hoc networks (MANET) charter. http:\/\/www.ietf.org\/html.charters\/manet-charter.html"},{"key":"S0963548308009334_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760925"},{"key":"S0963548308009334_ref23","unstructured":"[23] Robins G. and Zelikovsky A. (2000) Improved Steiner tree approximation in graphs. In Proc. 10th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 770\u2013779."},{"key":"S0963548308009334_ref18","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1029"},{"key":"S0963548308009334_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51542-9_13"},{"key":"S0963548308009334_ref11","unstructured":"[11] Frieze A. M. , Kleinberg J. , Ravi R. and Debany W. (2007) Line-of-sight networks. In Proc. 18th ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 968\u2013977."},{"key":"S0963548308009334_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"S0963548308009334_ref21","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548308009334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,9]],"date-time":"2019-04-09T19:16:58Z","timestamp":1554837418000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548308009334\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":25,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["S0963548308009334"],"URL":"https:\/\/doi.org\/10.1017\/s0963548308009334","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2009,3]]}}}