The Expected Number of 3D Visibility Events Is Linear
| Autor: | Xavier Goaoc, Sylvain Petitjean, Vida Dujmović, Hazel Everett, Hyeon-Suk Na, Sylvain Lazard, Olivier Devillers |
|---|---|
| Přispěvatelé: | Geometry, Algorithms and Robotics (PRISME), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), School of computer science [Ottawa] (SCS), Carleton University, Models, algorithms and geometry for computer graphics and vision (ISA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), School of Computing - Soongsil University, Séoul, Soongsil University, Seoul |
| Rok vydání: | 2003 |
| Předmět: |
complexe de visibilité
visibilité 3d General Computer Science Aspect ratio General Mathematics [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] Boundary (topology) 0102 computer and information sciences 02 engineering and technology Expected value évènements visuels 01 natural sciences visibility complex Combinatorics Polyhedron analyse probabiliste 3d visibility Line segment computational geometry 0202 electrical engineering electronic engineering information engineering visual events complexité en moyenne Mathematics expected complexity géométrie algorithmique Visibility (geometry) Tangent 020207 software engineering probabilistic analysis 010201 computation theory & mathematics Bounded function |
| Zdroj: | SIAM Journal on Computing SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2003, 32 (6), pp.1586-1620. ⟨10.1137/S0097539702419662⟩ SIAM Journal on Computing, 2003, 32 (6), pp.1586-1620. ⟨10.1137/S0097539702419662⟩ |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/s0097539702419662 |
| Popis: | In this paper, we show that, amongst $n$ uniformly distributed unit balls in $\mathbb{R}^3$, the expected number of maximal nonoccluded 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})$ [F. Durand, G. Drettakis, and C. Puech, {ACM Transactions on Graphics}, 21 (2002), pp. 176--206]. Our results generalize in various directions. We show that the linear bound on the expected number of maximal nonoccluded 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 nonfat three-dimensional 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|