Explicit laws of large numbers for random nearest-neighbour-type graphs

Andrew Wade

Research output: Contribution to journalArticle

21 Citations (Scopus)

Abstract

Under the unifying umbrella of a general result of Penrose & Yukich [Ann. Appl. Probab., (2003) 13, 277--303] we give laws of large numbers (in the Lp sense) for the total power-weighted length of several nearest-neighbour type graphs on random point sets in Rd, d in N. Some of these results are known; some are new. We give limiting constants explicitly, where previously they have been evaluated in less generality or not at all. The graphs we consider include the k-nearest neighbours graph, the Gabriel graph, the minimal directed spanning forest, and the on-line nearest-neighbour graph.
LanguageEnglish
Pages326-342
Number of pages17
JournalAdvances in Applied Probability
Volume39
Issue number2
DOIs
Publication statusPublished - Jun 2007

Fingerprint

Law of large numbers
Nearest Neighbor Graph
Nearest Neighbor
Graph in graph theory
Spanning Forest
Random Sets
Point Sets
Limiting

Keywords

  • nearest-neighbour-type graph
  • law of large numbers
  • spanning forest
  • spatial network evolution
  • explicit laws
  • large numbers
  • random

Cite this

@article{391b069f084a4c76ad1248a73de91c04,
title = "Explicit laws of large numbers for random nearest-neighbour-type graphs",
abstract = "Under the unifying umbrella of a general result of Penrose & Yukich [Ann. Appl. Probab., (2003) 13, 277--303] we give laws of large numbers (in the Lp sense) for the total power-weighted length of several nearest-neighbour type graphs on random point sets in Rd, d in N. Some of these results are known; some are new. We give limiting constants explicitly, where previously they have been evaluated in less generality or not at all. The graphs we consider include the k-nearest neighbours graph, the Gabriel graph, the minimal directed spanning forest, and the on-line nearest-neighbour graph.",
keywords = "nearest-neighbour-type graph, law of large numbers, spanning forest, spatial network evolution, explicit laws, large numbers, random",
author = "Andrew Wade",
year = "2007",
month = "6",
doi = "10.1239/aap/1183667613",
language = "English",
volume = "39",
pages = "326--342",
journal = "Advances in Applied Probability",
issn = "0001-8678",
number = "2",

}

Explicit laws of large numbers for random nearest-neighbour-type graphs. / Wade, Andrew.

In: Advances in Applied Probability, Vol. 39, No. 2, 06.2007, p. 326-342.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Explicit laws of large numbers for random nearest-neighbour-type graphs

AU - Wade, Andrew

PY - 2007/6

Y1 - 2007/6

N2 - Under the unifying umbrella of a general result of Penrose & Yukich [Ann. Appl. Probab., (2003) 13, 277--303] we give laws of large numbers (in the Lp sense) for the total power-weighted length of several nearest-neighbour type graphs on random point sets in Rd, d in N. Some of these results are known; some are new. We give limiting constants explicitly, where previously they have been evaluated in less generality or not at all. The graphs we consider include the k-nearest neighbours graph, the Gabriel graph, the minimal directed spanning forest, and the on-line nearest-neighbour graph.

AB - Under the unifying umbrella of a general result of Penrose & Yukich [Ann. Appl. Probab., (2003) 13, 277--303] we give laws of large numbers (in the Lp sense) for the total power-weighted length of several nearest-neighbour type graphs on random point sets in Rd, d in N. Some of these results are known; some are new. We give limiting constants explicitly, where previously they have been evaluated in less generality or not at all. The graphs we consider include the k-nearest neighbours graph, the Gabriel graph, the minimal directed spanning forest, and the on-line nearest-neighbour graph.

KW - nearest-neighbour-type graph

KW - law of large numbers

KW - spanning forest

KW - spatial network evolution

KW - explicit laws

KW - large numbers

KW - random

UR - http://projecteuclid.org/euclid.aap/1183667613

UR - http://arxiv.org/abs/math/0603559

U2 - 10.1239/aap/1183667613

DO - 10.1239/aap/1183667613

M3 - Article

VL - 39

SP - 326

EP - 342

JO - Advances in Applied Probability

T2 - Advances in Applied Probability

JF - Advances in Applied Probability

SN - 0001-8678

IS - 2

ER -