inria-00099810, version 1
The expected number of 3D visibility events is linear
Olivier Devillers
a, 1Vida Dujmovic b, 2Hazel Everett
c, 3Xavier Goaoc
c, 3Sylvain Lazard
d, 3Hyeon-Suk Na e, 4Sylvain Petitjean f, 3
SIAM Journal on Computing 32, 6 (2003) 1586-1620
Résumé : In this paper, we show that, amongst $n$ uniformly distributed unit balls in $\mathbb{R}^3$, the expected number of maximal non-occluded line segments tangent to four balls is linear. 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. These results significantly improve the best previously known bounds of $O(n^{8/3})$. 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.
- a – INRIA SOPHIA-ANTIPOLIS
- b – MCGILL UNIVERSITY, MONTREAL, CANADA
- c – UNIVERSITE NANCY 2
- d – INRIA
- e – SOONGSIL UNIVERSITY, SEOUL,SOUTH KOREA
- f – CNRS
- 1 : PRISME (INRIA Sophia Antipolis)
- INRIA
- 2 : School of computer science [Ottawa] (SCS)
- Carleton University
- 3 : ISA (INRIA Lorraine - LORIA)
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine
- 4 : School of Computing - Soongsil University, Séoul
- Soongsil University, Seoul
- Domaine : Informatique/Autre
- Mots-clés : computational geometry – 3d visibility – visibility complex – visual events – probabilistic analysis – expected complexity || géométrie algorithmique – visibilité 3d – complexe de visibilité – évènements visuels – analyse probabiliste – complexité en moyenne
- Référence interne : A03-R-083 || devillers03a
- Commentaire : Article dans revue scientifique avec comité de lecture. internationale.
- inria-00099810, version 1
- http://hal.inria.fr/inria-00099810
- oai:hal.inria.fr:inria-00099810
- Contributeur : Sylvain Lazard
- Soumis le : Mardi 15 Décembre 2009, 14:43:55
- Dernière modification le : Jeudi 17 Décembre 2009, 17:20:17






Documents associés
Exporter