Mobile geometric graphs: Detection, coverage and percolation

Yuval Peres, Alistair Sinclair, Perla Sousi, Alexandre Stauffer

Research output: Contribution to journalArticle

22 Citations (Scopus)
146 Downloads (Pure)

Abstract

We consider the following dynamic Boolean model introduced by van den Berg et al. (Stoch. Process. Appl. 69:247–257, 1997). At time 0, let the nodes of the graph be a Poisson point process in Rd with constant intensity and let each node move independently according to Brownian motion. At any time t, we put an edge between every pair of nodes whose distance is at most r. We study three fundamental problems in this model: detection (the time until a target point—fixed or moving—is within distance r of some node of the graph); coverage (the time until all points inside a finite box are detected by the graph); and percolation (the time until a given node belongs to the infinite connected component of the graph). We obtain precise asymptotics for these quantities by combining ideas from stochastic geometry, coupling and multi-scale analysis.
Original languageEnglish
Pages (from-to)273-305
Number of pages33
JournalProbability Theory and Related Fields
Volume156
Issue number1-2
DOIs
Publication statusPublished - Jun 2013

Fingerprint Dive into the research topics of 'Mobile geometric graphs: Detection, coverage and percolation'. Together they form a unique fingerprint.

Cite this