Smoothed complexity of convex hulls by witnesses and collectors - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue Journal of Computational Geometry Année : 2016

Smoothed complexity of convex hulls by witnesses and collectors

Olivier Devillers
Effective Geometric Algorithms for Surfaces and Visibility
CV
Marc Glisse
Understanding the Shape of Data
CV
Xavier Goaoc
Laboratoire d'Informatique Gaspard-Monge
CV
Rémy Thomasse
  • Fonction : Auteur
Geometric computing

Résumé

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.

Domaines

Géométrie algorithmique [cs.CG]
Fichier principal
Vignette du fichier
265-1014-1-PB.pdf (1.13 Mo) Télécharger le fichier
Vignette du fichier
vignette.png (22.37 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Format : Figure, Image
Origine : Fichiers produits par l'(les) auteur(s)

Olivier Devillers  : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-01285120

Soumis le : mardi 8 mars 2016-16:13:15

Dernière modification le : jeudi 28 mars 2024-03:26:05

Télécharger pour visualiser

Dates et versions

hal-01285120 , version 1 (08-03-2016)

Identifiants

Citer

Olivier Devillers, Marc Glisse, Xavier Goaoc, Rémy Thomasse. Smoothed complexity of convex hulls by witnesses and collectors. Journal of Computational Geometry, 2016, 7 (2), pp.101-144. ⟨10.20382/jocg.v7i2a6⟩. ⟨hal-01285120⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

ENPC UNIV-RENNES1 CNRS INRIA IRISA PARISTECH LIGM LIGM_MOA UNIV-LORRAINE INRIA2 LORIA LORIA-ALGO UR1-MATH-STIC UNIV-PARIS-SACLAY UR1-UFR-ISTIC UNIV-COTEDAZUR UNIV-RENNES ESIEE-PARIS ANR UR1-MATH-NUM GS-COMPUTER-SCIENCE UNIV-EIFFEL LIGM_ADA JSE2024
576 Consultations
255 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More