Complexity analysis of random geometric structures made simpler

Olivier Devillers 1 Marc Glisse 1 Xavier Goaoc 2
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : Average-case analysis of data-structures or algorithms is commonly used in compu- tational geometry when the, more classical, worst-case analysis is deemed overly pessimistic. Since these analyses are often intricate, the models of random geometric data that can be handled are often simplistic and far from "realistic inputs". We present a new simple scheme for the analy- sis of geometric structures. While this scheme only produces results up to a polylog factor, it is much simpler to apply than the classical techniques and therefore succeeds in analyzing new input distributions related to smoothed complexity analysis. Abstract: We illustrate our method on two classical structures: convex hulls and Delaunay triangulations. Specifically, we give short and elementary proofs of the classical results that n points uniformly distributed in a ball in Rd have a convex hull and a Delaunay triangulation of respective expected complexities Θ~(n^((d+1)/(d-1)) ) and Θ~(n). We then prove that if we start with n points well-spread on a sphere, e.g. an (ε,κ)-sample of that sphere, and perturb that sample by moving each point ran- domly and uniformly within distance at most δ of its initial position, then the expected complexity of the convex hull of the resulting point set is Θ~( sqrt(n)^(1−1/d) δ^(-(d-1/d)/4)). .
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-00761171
Contributor : Olivier Devillers <>
Submitted on : Wednesday, December 5, 2012 - 9:39:10 AM
Last modification on : Friday, September 20, 2019 - 4:56:39 PM
Long-term archiving on : Saturday, December 17, 2016 - 8:29:50 PM

File

RR-8168.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00761171, version 1

Citation

Olivier Devillers, Marc Glisse, Xavier Goaoc. Complexity analysis of random geometric structures made simpler. [Research Report] RR-8168, INRIA. 2012. ⟨hal-00761171⟩

Share

Metrics

Record views

558

Files downloads

401