Skip to main content
SpringerLink
Log in

Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

A random geometric graph (RGG) is defined by placing n points uniformly at random in [0,n 1/d]d, and joining two points by an edge whenever their Euclidean distance is at most some fixed r. We assume that r is larger than the critical value for the emergence of a connected component with Ω(n) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of \(\omega (\frac{\log n}{r^{d-1}} )\), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is Θ(n 1/d/r) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight.

We also analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that w.h.p. this algorithm informs every node in the largest connected component of an RGG within Θ(n 1/d/r+logn) rounds.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. By “with high probability” (short: w.h.p.), we denote an event that holds with probability at least \(1-\mathcal{O}(n^{-1})\).

References

  1. Akyildiz, I., Pompili, D., Melodia, T.: Underwater acoustic sensor networks: research challenges. Ad Hoc Netw. 3, 257–279 (2005)

    Article  Google Scholar 

  2. Antal, P., Pisztora, A.: On the chemical distance for supercritical Bernoulli percolation. Ann. Probab. 24, 1036–1048 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  3. Avin, C., Ercal, G.: On the cover time and mixing time of random geometric graphs. Theor. Comput. Sci. 380(1–2), 2–22 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bradonjić, M., Elsässer, R., Friedrich, T., Sauerwald, T., Stauffer, A.: Efficient broadcast on random geometric graphs. In: 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’10), pp. 1412–1421 (2010)

    Google Scholar 

  5. Cooper, C., Frieze, A.: The cover time of the giant component of a random graph. Random Struct. Algorithms 32(4), 401–439 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  6. Cooper, C., Frieze, A.: The cover time of random geometric graphs. In: 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’09), pp. 48–57 (2009)

    Google Scholar 

  7. Deuschel, J.-D., Pisztora, A.: Surface order large deviations for high-density percolation. Probab. Theory Relat. Fields 104, 467–482 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  8. Ellis, R.B., Martin, J.L., Yan, C.: Random geometric graph diameter in the unit ball. Algorithmica 47(4), 421–438 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Elsässer, R., Sauerwald, T.: Broadcasting vs. mixing and information dissemination on Cayley graphs. In: 24th International Symposium on Theoretical Aspects of Computer Science (STACS’07), pp. 163–174 (2007)

    Google Scholar 

  10. Elsässer, R., Sauerwald, T.: On the runtime and robustness of randomized broadcasting. Theor. Comput. Sci. 410(36), 3414–3427 (2009)

    Article  MATH  Google Scholar 

  11. Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. Random Struct. Algorithms 1(4), 447–460 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fontes, L., Newman, C.: First passage percolation for random colorings of ℤd. Ann. Appl. Probab. 3(3), 746–762 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  13. Fountoulakis, N., Panagiotou, K.: Rumor spreading on random regular graphs and expanders. In: 14th Inter. Workshop on Randomization and Comput. (RANDOM). LNCS, vol. 6302, pp. 560–573 (2010)

    Google Scholar 

  14. Frieze, A., Grimmett, G.: The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math. 10, 57–77 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  15. Grimmett, G.: Percolation, 2nd edn. Springer, Berlin (1999)

    MATH  Google Scholar 

  16. Higham, D., Rašajski, M., Pržulj, N.: Fitting a geometric graph to a protein–protein interaction network. Bioinformatics 24(8), 1093 (2008)

    Article  Google Scholar 

  17. Liggett, T., Schonmann, R., Stacey, A.: Domination by product measures. Ann. Probab. 25(1), 71–95 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  18. Meester, R., Roy, R.: Continuum Percolation. Cambridge University Press, Cambridge (1996)

    Book  MATH  Google Scholar 

  19. Muthukrishnan, S., Pandurangan, G.: The bin-covering technique for thresholding random geometric graph properties. J. Comput. Syst. Sci. 76, 686–696 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  20. Ou, C.-H., Ssu, K.-F.: Sensor position determination with flying anchors in three-dimensional wireless sensor networks. IEEE Trans. Mob. Comput. 7, 1084–1097 (2008)

    Article  Google Scholar 

  21. Penrose, M., Pisztora, A.: Large deviations for discrete and continuous percolation. Adv. Appl. Probab. 28, 29–52 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  22. Penrose, M.D.: The longest edge of the random minimal spanning tree. Ann. Appl. Probab. 7(2), 340–361 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  23. Penrose, M.D.: On k-connectivity for a geometric random graph. Random Struct. Algorithms 15(2), 145–164 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  24. Penrose, M.D.: Random Geometric Graphs. Oxford University Press, Oxford (2003)

    Book  MATH  Google Scholar 

  25. Pittel, B.: On spreading a rumor. SIAM J. Appl. Math. 47(1), 213–223 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  26. Pottie, G.J., Kaiser, W.J.: Wireless integrated network sensors. Commun. ACM 43(5), 51–58 (2000)

    Article  Google Scholar 

  27. Sauerwald, T.: On mixing and edge expansion properties in randomized broadcasting. Algorithmica 56, 51–88 (2010)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Friedrich-Schiller-Universität Jena, Jena, Germany

    Tobias Friedrich

  2. Max-Planck-Institut für Informatik, Saarbrücken, Germany

    Thomas Sauerwald

  3. Microsoft Research, Redmond, WA, USA

    Alexandre Stauffer

Authors
  1. Tobias Friedrich
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thomas Sauerwald
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alexandre Stauffer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tobias Friedrich.

Additional information

A conference version with slightly weaker results appeared in the 22nd International Symposium on Algorithms and Computation. This work was initiated while the first two authors were at the International Computer Science Institute Berkeley supported by the German Academic Exchange Service (DAAD) and the third author was at the Computer Science Division of the University of California Berkeley.

Appendix: Standard Large Deviation Results

Appendix: Standard Large Deviation Results

Lemma 21

(Chernoff bound for sums of geometric variables)

Let X 1,…,X n be independent geometric random variables, each having parameter p (and thus mean 1/p), and let \(X = \sum_{i=1}^{n} X_{i}\). Then, for any ϵ>0,

$$\Pr{X \ge (1+\epsilon) \, \frac{n}{p} } \leq \exp \left(- \frac{\epsilon^2}{2(1+\epsilon)} \, n \right). $$

Rights and permissions

Reprints and permissions

About this article

Cite this article

Friedrich, T., Sauerwald, T. & Stauffer, A. Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions. Algorithmica 67, 65–88 (2013). https://doi.org/10.1007/s00453-012-9710-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-012-9710-y

Keywords

Search

Navigation