The expected number of 3D visibility events is linear
Identifieur interne : 007F28 ( Main/Merge ); précédent : 007F27; suivant : 007F29The expected number of 3D visibility events is linear
Auteurs : Olivier Devillers [France] ; Vida Dujmovic [Canada] ; Hazel Everett [France] ; Xavier Goaoc [France] ; Sylvain Lazard [France] ; Hyeon-Suk Na [Corée du Sud] ; Sylvain Petitjean [France]Source :
- SIAM journal on computing : (Print) [ 0097-5397 ] ; 2003.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
In this paper, we show that, amongst n uniformly distributed unit balls in R3, 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(n8/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.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000731
- to stream PascalFrancis, to step Curation: 000310
- to stream PascalFrancis, to step Checkpoint: 000669
Links to Exploration step
Pascal:04-0091723Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">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><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>INRIA Sophia-Antipolis, BP 93</s1><s2>06902 Sophia-Antipolis</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Provence-Alpes-Côte d'Azur</region><settlement type="city">Sophia-Antipolis</settlement></placeName></affiliation></author><author><name sortKey="Dujmovic, Vida" sort="Dujmovic, Vida" uniqKey="Dujmovic V" first="Vida" last="Dujmovic">Vida Dujmovic</name><affiliation wicri:level="4"><inist:fA14 i1="02"><s1>School of Computer Science, McGill University</s1><s2>Ottawa, ON</s2><s3>CAN</s3><sZ>2 aut.</sZ></inist:fA14><country>Canada</country><placeName><settlement type="city">Montréal</settlement><region type="state">Québec</region></placeName><orgName type="university">Université McGill</orgName></affiliation></author><author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name><affiliation wicri:level="3"><inist:fA14 i1="03"><s1>LORIA - INRIA Lorraine, CNRS, Univ.</s1><s2>Nancy</s2><s3>FRA</s3><sZ>3 aut.</sZ><sZ>4 aut.</sZ><sZ>5 aut.</sZ><sZ>7 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name><affiliation wicri:level="3"><inist:fA14 i1="03"><s1>LORIA - INRIA Lorraine, CNRS, Univ.</s1><s2>Nancy</s2><s3>FRA</s3><sZ>3 aut.</sZ><sZ>4 aut.</sZ><sZ>5 aut.</sZ><sZ>7 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="3"><inist:fA14 i1="03"><s1>LORIA - INRIA Lorraine, CNRS, Univ.</s1><s2>Nancy</s2><s3>FRA</s3><sZ>3 aut.</sZ><sZ>4 aut.</sZ><sZ>5 aut.</sZ><sZ>7 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name><affiliation wicri:level="3"><inist:fA14 i1="04"><s1>School of Computing, Soongsil University</s1><s2>Seoul</s2><s3>KOR</s3><sZ>6 aut.</sZ></inist:fA14><country>Corée du Sud</country><placeName><settlement type="city">Séoul</settlement><region type="capital">Région capitale de Séoul</region></placeName></affiliation></author><author><name sortKey="Petitjean, Sylvain" sort="Petitjean, Sylvain" uniqKey="Petitjean S" first="Sylvain" last="Petitjean">Sylvain Petitjean</name><affiliation wicri:level="3"><inist:fA14 i1="03"><s1>LORIA - INRIA Lorraine, CNRS, Univ.</s1><s2>Nancy</s2><s3>FRA</s3><sZ>3 aut.</sZ><sZ>4 aut.</sZ><sZ>5 aut.</sZ><sZ>7 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">04-0091723</idno><date when="2003">2003</date><idno type="stanalyst">PASCAL 04-0091723 INIST</idno><idno type="RBID">Pascal:04-0091723</idno><idno type="wicri:Area/PascalFrancis/Corpus">000731</idno><idno type="wicri:Area/PascalFrancis/Curation">000310</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000669</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000669</idno><idno type="wicri:doubleKey">0097-5397:2003:Devillers O:the:expected:number</idno><idno type="wicri:Area/Main/Merge">007F28</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">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><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>INRIA Sophia-Antipolis, BP 93</s1><s2>06902 Sophia-Antipolis</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Provence-Alpes-Côte d'Azur</region><settlement type="city">Sophia-Antipolis</settlement></placeName></affiliation></author><author><name sortKey="Dujmovic, Vida" sort="Dujmovic, Vida" uniqKey="Dujmovic V" first="Vida" last="Dujmovic">Vida Dujmovic</name><affiliation wicri:level="4"><inist:fA14 i1="02"><s1>School of Computer Science, McGill University</s1><s2>Ottawa, ON</s2><s3>CAN</s3><sZ>2 aut.</sZ></inist:fA14><country>Canada</country><placeName><settlement type="city">Montréal</settlement><region type="state">Québec</region></placeName><orgName type="university">Université McGill</orgName></affiliation></author><author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name><affiliation wicri:level="3"><inist:fA14 i1="03"><s1>LORIA - INRIA Lorraine, CNRS, Univ.</s1><s2>Nancy</s2><s3>FRA</s3><sZ>3 aut.</sZ><sZ>4 aut.</sZ><sZ>5 aut.</sZ><sZ>7 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name><affiliation wicri:level="3"><inist:fA14 i1="03"><s1>LORIA - INRIA Lorraine, CNRS, Univ.</s1><s2>Nancy</s2><s3>FRA</s3><sZ>3 aut.</sZ><sZ>4 aut.</sZ><sZ>5 aut.</sZ><sZ>7 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="3"><inist:fA14 i1="03"><s1>LORIA - INRIA Lorraine, CNRS, Univ.</s1><s2>Nancy</s2><s3>FRA</s3><sZ>3 aut.</sZ><sZ>4 aut.</sZ><sZ>5 aut.</sZ><sZ>7 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name><affiliation wicri:level="3"><inist:fA14 i1="04"><s1>School of Computing, Soongsil University</s1><s2>Seoul</s2><s3>KOR</s3><sZ>6 aut.</sZ></inist:fA14><country>Corée du Sud</country><placeName><settlement type="city">Séoul</settlement><region type="capital">Région capitale de Séoul</region></placeName></affiliation></author><author><name sortKey="Petitjean, Sylvain" sort="Petitjean, Sylvain" uniqKey="Petitjean S" first="Sylvain" last="Petitjean">Sylvain Petitjean</name><affiliation wicri:level="3"><inist:fA14 i1="03"><s1>LORIA - INRIA Lorraine, CNRS, Univ.</s1><s2>Nancy</s2><s3>FRA</s3><sZ>3 aut.</sZ><sZ>4 aut.</sZ><sZ>5 aut.</sZ><sZ>7 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author></analytic><series><title level="j" type="main">SIAM journal on computing : (Print)</title><title level="j" type="abbreviated">SIAM j. comput. : (Print)</title><idno type="ISSN">0097-5397</idno><imprint><date when="2003">2003</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">SIAM journal on computing : (Print)</title><title level="j" type="abbreviated">SIAM j. comput. : (Print)</title><idno type="ISSN">0097-5397</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computational geometry</term><term>Computer graphics</term><term>Data structure</term><term>Expected complexity</term><term>Graphics</term><term>Poisson distribution</term><term>Polygon</term><term>Polyhedron</term><term>Probabilistic approach</term><term>Three dimensional visibility</term><term>Visibility complex</term><term>Visual event</term><term>Worst case method</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Géométrie algorithmique</term><term>Approche probabiliste</term><term>Structure donnée</term><term>Représentation graphique</term><term>Infographie</term><term>Méthode cas pire</term><term>Loi Poisson</term><term>Polyèdre</term><term>Polygone</term><term>Visibilité 3 dimensions</term><term>Evénement visuel</term><term>Complexe visibilité</term><term>Complexité probable</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">In this paper, we show that, amongst n uniformly distributed unit balls in R<sup>3</sup>, 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<sup>8/3</sup>) [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.</div></front></TEI><affiliations><list><country><li>Canada</li><li>Corée du Sud</li><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li><li>Provence-Alpes-Côte d'Azur</li><li>Québec</li><li>Région capitale de Séoul</li></region><settlement><li>Montréal</li><li>Nancy</li><li>Sophia-Antipolis</li><li>Séoul</li></settlement><orgName><li>Université McGill</li></orgName></list><tree><country name="France"><region name="Provence-Alpes-Côte d'Azur"><name sortKey="Devillers, Olivier" sort="Devillers, Olivier" uniqKey="Devillers O" first="Olivier" last="Devillers">Olivier Devillers</name></region><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><name sortKey="Petitjean, Sylvain" sort="Petitjean, Sylvain" uniqKey="Petitjean S" first="Sylvain" last="Petitjean">Sylvain Petitjean</name></country><country name="Canada"><region name="Québec"><name sortKey="Dujmovic, Vida" sort="Dujmovic, Vida" uniqKey="Dujmovic V" first="Vida" last="Dujmovic">Vida Dujmovic</name></region></country><country name="Corée du Sud"><region name="Région capitale de Séoul"><name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 007F28 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 007F28 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= Pascal:04-0091723
|texte= The expected number of 3D visibility events is linear
}}
| This area was generated with Dilib version V0.6.33. |  |