CONVEX HULLS OF PERTURBED RANDOM POINT SETS

• 成果类型: Article
• 署名作者: Calka, Pierre; Yukich, J. E.
• 署名单位: Universite de Rouen Normandie; Lehigh University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/20-AAP1627
• 发表日期: 2021
• 页码: 1598-1632
• 关键词: variance asymptotics; gaussian limits; polytopes; THEOREMS; numbers

摘要

We consider the convex hull of the perturbed point process comprised of n i.i.d. points, each distributed as the sum of a uniform point on the unit sphere Sd-1 and a uniform point in the d-dimensional ball centered at the origin and of radius n(alpha), alpha is an element of (-infinity,infinity). This model, inspired by the smoothed complexity analysis introduced in computational geometry (J. Comput. Geom. 7 (2016) 101-144; J. ACM 51 (2004) 385-463), is a perturbation of the classical random polytope. We show that the perturbed point process, after rescaling, converges in the scaling limit to one of five Poisson point processes according to whether alpha belongs to one of five regimes. The intensity measure of the limit Poisson point process undergoes a transition at the values alpha = -2/d-1 and alpha = 2/d+1 and it gives rise to four rescalings for the k-face functional on perturbed data. These rescalings are used to establish explicit expectation asymptotics for the number of k-dimensional faces of the convex hull of either perturbed binomial or Poisson data. In the case of Poisson input, we establish explicit variance asymptotics and a central limit theorem for the number of k-dimensional faces. Finally, it is shown that the rescaled boundary of the convex hull of the perturbed point process converges to the boundary of a parabolic hull process.