Mobile geometric graphs

Detection, coverage and percolation

Yuval Peres, Alistair Sinclair, Perla Sousi, Alexandre Stauffer

Research output: Contribution to journalArticle

18 Citations (Scopus)
80 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

Geometric Graphs
Coverage
Vertex of a graph
Graph in graph theory
Stochastic Geometry
Boolean Model
Precise Asymptotics
Poisson Point Process
Multiscale Analysis
Connected Components
Brownian motion
Dynamic Model
Fixed point
Node
Graph
Target

Cite this

Mobile geometric graphs : Detection, coverage and percolation. / Peres, Yuval; Sinclair, Alistair; Sousi, Perla; Stauffer, Alexandre.

In: Probability Theory and Related Fields, Vol. 156, No. 1-2, 06.2013, p. 273-305.

Research output: Contribution to journalArticle

Peres, Yuval ; Sinclair, Alistair ; Sousi, Perla ; Stauffer, Alexandre. / Mobile geometric graphs : Detection, coverage and percolation. In: Probability Theory and Related Fields. 2013 ; Vol. 156, No. 1-2. pp. 273-305.
@article{b4658abf2e874238a4eed2fbb933b642,
title = "Mobile geometric graphs: Detection, coverage and percolation",
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.",
author = "Yuval Peres and Alistair Sinclair and Perla Sousi and Alexandre Stauffer",
year = "2013",
month = "6",
doi = "10.1007/s00440-012-0428-1",
language = "English",
volume = "156",
pages = "273--305",
journal = "Probability Theory and Related Fields",
issn = "0178-8051",
publisher = "Springer New York",
number = "1-2",

}

TY - JOUR

T1 - Mobile geometric graphs

T2 - Detection, coverage and percolation

AU - Peres, Yuval

AU - Sinclair, Alistair

AU - Sousi, Perla

AU - Stauffer, Alexandre

PY - 2013/6

Y1 - 2013/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84878112315&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1007/s00440-012-0428-1

U2 - 10.1007/s00440-012-0428-1

DO - 10.1007/s00440-012-0428-1

M3 - Article

VL - 156

SP - 273

EP - 305

JO - Probability Theory and Related Fields

JF - Probability Theory and Related Fields

SN - 0178-8051

IS - 1-2

ER -