Smoothed complexity of convex hulls by witnesses and collectors

Olivier Devillers; Marc Glisse; Xavier Goaoc; Rémy Thomasse

doi:10.20382/jocg.v7i2a6

Smoothed complexity of convex hulls by witnesses and collectors

Olivier Devillers ¹ Marc Glisse ² Xavier Goaoc ³ Rémy Thomasse ⁴

1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility

LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry, Inria Nancy - Grand Est

2 DATASHAPE - Understanding the Shape of Data

CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France

3 LIGM - Laboratoire d'Informatique Gaspard-Monge

4 GEOMETRICA - Geometric computing

CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France

Abstract : We present a simple technique for analyzing the size of geometric hypergraphs dened 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.

Type de document :

Article dans une revue

Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2016, 7 (2), pp.101-144. 〈http://jocg.org/v7n2p6〉. 〈10.20382/jocg.v7i2a6〉

Domaine :

Informatique [cs] / Géométrie algorithmique [cs.CG]

Liste complète des métadonnées

Littérature citée [23 références] Voir Masquer Télécharger

https://hal.inria.fr/hal-01285120
Contributeur : Olivier Devillers <>
Soumis le : mardi 8 mars 2016 - 16:13:15
Dernière modification le : mercredi 11 avril 2018 - 12:12:03

265-1014-1-PB.pdf

Fichiers éditeurs autorisés sur une archive ouverte

Smoothed complexity of convex hulls by witnesses and collectors

Fichiers

Identifiants

Collections

Citation

Exporter

Métriques

493

104

Contact

Smoothed complexity of convex hulls by witnesses and collectors

Fichiers

Identifiants

Collections

Citation

Exporter

Partager

Métriques

493

104

Contact