Asymptotics for the length of a minimal triangulation on a random sample

• 成果类型: Article
• 署名作者: Yukich, JE
• 署名单位: Lehigh University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 1999
• 页码: 27-45
• 关键词: euclidean functionals

摘要

Given F subset of [0, 1](2) and finite, let a(F) denote the length of the minimal Steiner triangulation of points in F. By showing that minimal Steiner triangulations fit into the theory of subadditive and superadditive Euclidean functionals, we prove under a mild regularity condition that lim(n --> infinity) sigma(X-1..., X-n)/n(1/2) = beta integral([0, 1]2)f(x)(1/2) DX c.c., where X-1,...,X-n are i.i.d. random variables with values in [0, 1](2), beta is a positive constant, f is the density of the absolutely continuous part of the law of X-1, and c.c. denotes complete convergence. This extends the work of Steele. The result extends naturally to dimension three and describes the asymptotics for the probabilistic Plateau functional, thus making progress on a question of Beardwood, Halton and Hammersley. Rates of convergence are also found.