On the Smoothed Complexity of Convex Hulls

We establish an upper bound on the smoothed complexity of convex hulls in Rd under uniform Euclidean (l²) noise. Specifically, let {p∗₁ , p∗₂ , . . . , p∗_n} be an arbitrary set of n points in the unit ball in ℝ^d and let p_i = p∗_i + x_i, where x₁, x₂, . . . , xn are chosen independently from the unit ball of radius . We show that the expected complexity, measured as the number of faces of all dimensions, of the convex hull of {p₁, p₂, . . . , p_n} is O (n²-4/d+1 (1 + 1/δ)^d-1); the magnitude δ of the noise may vary with n. For d = 2 this bound improves to O (n2/3 (1 + δ-2/3). We also analyze the expected complexity of the convex hull of l² and Gaussian perturbations of a nice sample of a sphere, giving a lower-bound for the smoothed complexity. We identify the different regimes in terms of the scale, as a function of n, and show that as the magnitude of the noise increases, that complexity varies monotonically for Gaussian noise but non-monotonically for 2 noise.