Premium
On smallest triangles
Author(s) -
Grimmett Geoffrey,
Janson Svante
Publication year - 2003
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10092
Subject(s) - mathematics , lebesgue measure , measure (data warehouse) , absolute continuity , regular polygon , poisson distribution , probability measure , combinatorics , lebesgue integration , constant (computer programming) , discrete mathematics , pure mathematics , geometry , statistics , database , computer science , programming language
Pick n points independently at random in ℝ 2 , according to a prescribed probability measure μ, and let Δ n 1≤ Δ n 2≤ … be the areas of the ( n 3 ) triangles thus formed, in nondecreasing order. If μ is absolutely continuous with respect to Lebesgue measure, then, under weak conditions, the set { n 3 Δ n i: i ≥ 1} converges as n → ∞ to a Poisson process with a constant intensity κ(μ). This result, and related conclusions, are proved using standard arguments of Poisson approximation, and may be extended to functionals more general than the area of a triangle. It is proved in addition that if μ is the uniform probability measure on the region S , then κ(μ) ≤ 2/| S |, where | S | denotes the area of S . Equality holds in that κ(μ) = 2/| S | if S is convex, and essentially only then. This work generalizes and extends considerably the conclusions of a recent paper of Jiang, Li, and Vitányi. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 206–223, 2003