Smoothed complexity of convex hulls by witnesses and collectors - Archive ouverte HAL Access content directly
Journal Articles Journal of Computational Geometry Year : 2016

Smoothed complexity of convex hulls by witnesses and collectors

(1) , (2) , (3) , (4)
1
2
3
4
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
  • Function : Author
Geometric computing

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.

Domains

Computer Science [cs] Computational Geometry [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
Origin : Publisher files allowed on an open archive
Format : Figure, Image
Origin : Files produced by the author(s)

Olivier Devillers  : Connect in order to contact the contributor

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

Submitted on : Tuesday, March 8, 2016-4:13:15 PM

Last modification on : Friday, September 16, 2022-1:57:02 PM

Download

Dates and versions

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

Identifiers

Cite

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⟩

Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

Collections

ENPC CNRS INRIA IRISA PARISTECH LIGM LIGM_MOA UNIV-LORRAINE INRIA2 LORIA LORIA-ALGO UR1-MATH-STIC UNIV-PARIS-SACLAY UR1-UFR-ISTIC UNIV-COTEDAZUR ESIEE-PARIS ANR UR1-MATH-NUM GS-COMPUTER-SCIENCE UNIV-EIFFEL LIGM_ADA
551 View
215 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More