Published October 2015
| Version v1
Report
Smoothed complexity of convex hulls by witnesses and collectors
Contributors
Others:
- Effective Geometric Algorithms for Surfaces and Visibility (VEGAS) ; Centre Inria de l'Université de Lorraine ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO) ; Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
- Geometric computing (GEOMETRICA) ; Centre Inria d'Université Côte d'Azur (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre Inria de Saclay ; Institut National de Recherche en Informatique et en Automatique (Inria)
- Laboratoire d'Informatique Gaspard-Monge (LIGM) ; Université Paris-Est Marne-la-Vallée (UPEM)-École nationale des ponts et chaussées (ENPC)-ESIEE Paris-Fédération de Recherche Bézout (BEZOUT) ; Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)
- INRIA
- ANR-11-BS02-0003,PRESAGE,méthodes PRobabilistes pour l'Éfficacité des Structures et Algorithmes GEométriques(2011)
Description
We present a simple technique for analyzing the size of geometric hypergraphs defined by random point sets. As an application we obtain upper and lower bounds on the smoothed number of faces of the convex hull under Euclidean and Gaussian noise and related results.
Abstract (French)
Nous présentons une méthode simple pour l'analyse de la tailled'hypergraphes géométriques définis par des ensembles de pointsaléatoires.En appliquant cette technique nous obtenons des bornes inférieures etsupérieurespour l'analyse lissée de du nombre de faces de l'enveloppe convexe depoints soumis à un bruit euclidien ou gaussien.Additional details
Identifiers
- URL
- https://inria.hal.science/hal-01214021
- URN
- urn:oai:HAL:hal-01214021v2
Origin repository
- Origin repository
- UNICA