The expected number of 3D visibility events is linear
Identifieur interne : 008657 ( Main/Curation ); précédent : 008656; suivant : 008658The expected number of 3D visibility events is linear
Auteurs : Olivier Devillers ; Vida Dujmovic ; Hazel Everett ; Xavier Goaoc ; Sylvain Lazard ; Hyeon-Suk Na ; Sylvain PetitjeanSource :
English descriptors
- KwdEn :
Abstract
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, 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.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: Pour aller vers cette notice dans l'étape Curation :003692
- to stream Crin, to step Curation: Pour aller vers cette notice dans l'étape Curation :003692
- to stream Crin, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :001345
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :008B13
Links to Exploration step
CRIN:devillers02aLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="120">The expected number of 3D visibility events is linear</title></titleStmt><publicationStmt><idno type="RBID">CRIN:devillers02a</idno><date when="2002" year="2002">2002</date><idno type="wicri:Area/Crin/Corpus">003692</idno><idno type="wicri:Area/Crin/Curation">003692</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">003692</idno><idno type="wicri:Area/Crin/Checkpoint">001345</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">001345</idno><idno type="wicri:Area/Main/Merge">008B13</idno><idno type="wicri:Area/Main/Curation">008657</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">The expected number of 3D visibility events is linear</title><author><name sortKey="Devillers, Olivier" sort="Devillers, Olivier" uniqKey="Devillers O" first="Olivier" last="Devillers">Olivier Devillers</name></author><author><name sortKey="Dujmovic, Vida" sort="Dujmovic, Vida" uniqKey="Dujmovic V" first="Vida" last="Dujmovic">Vida Dujmovic</name></author><author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name></author><author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name></author><author><name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name></author><author><name sortKey="Petitjean, Sylvain" sort="Petitjean, Sylvain" uniqKey="Petitjean S" first="Sylvain" last="Petitjean">Sylvain Petitjean</name></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term> visibility complex</term><term>3d visibility</term><term>computational geometry</term><term>expected complexity</term><term>probabilistic analysis</term><term>visual events</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="3625">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, 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.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 008657 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 008657 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Curation
|type= RBID
|clé= CRIN:devillers02a
|texte= The expected number of 3D visibility events is linear
}}
| This area was generated with Dilib version V0.6.33. |  |