Central limit theorems for some graphs in computational geometry

• 成果类型: Article
• 署名作者: Penrose, MD; Yukich, JE
• 署名单位: Durham University; Lehigh University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 2001
• 页码: 1005-1041
• 关键词: nearest-neighbor; expected size; random sphere

摘要

Let (B-n) be an increasing sequence of regions in d-dimensional space with volume n and with union R-d. We prove a general central limit theorem for functionals of point sets, obtained either by restricting a homogeneous Poisson process to Bn, or by by taking n uniformly distributed points in B-n. The sets B-n could be all cubes but a more general class of regions B-n is considered. Using this general result we obtain central limit theorems for specific functionals such as total edge length and number of components, defined in terms of graphs such as the k-nearest neighbors graph, the sphere of influence graph and the Voronoi graph.