The expected number of 3D visibility events is linear

Abstract : In this paper, we show that, amongst n uniformly distributed unit balls in R^3, the expected number of maximal non-occluded line segments tangent to four balls is linear, considerably improving the previously known upper bound. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding the visibility information of a scene, providing evidence that the storage requirement for this data structure is not necessarily prohibitive. Our results generalize in various directions. We show that the linear bound on the expected number of maximal non-occluded line segments that are not too close to the boundary of the scene and tangent to four unit balls extends to balls of various but bounded radii, to polyhedra of bounded aspect ratio, and even to non-fat 3D objects such as polygons of bounded aspect ratio. We also prove that our results extend to other distributions such as the Poisson distribution. Finally, we indicate how our probabilistic analysis provides new insight on the expected size of other global visibility data structures, notably the aspect graph.
Type de document :
Rapport
[Research Report] RR-4671, INRIA. 2002
Liste complète des métadonnées

https://hal.inria.fr/inria-00071914
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 23 mai 2006 - 19:14:10
Dernière modification le : samedi 27 janvier 2018 - 01:31:24
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:44:18

Fichiers

Identifiants

  • HAL Id : inria-00071914, version 1

Collections

Citation

Olivier Devillers, Vida Dujmovic, Hazel Everett, Xavier Goaoc, Sylvain Lazard, et al.. The expected number of 3D visibility events is linear. [Research Report] RR-4671, INRIA. 2002. 〈inria-00071914〉

Partager

Métriques

Consultations de la notice

327

Téléchargements de fichiers

123