InforLorV4, PascalFrancis, Corpus, bibRecord, 000731

The expected number of 3D visibility events is linear

Identifieur interne : 000731 ( PascalFrancis/Corpus ); précédent : 000730; suivant : 000732

The expected number of 3D visibility events is linear

Auteurs : Olivier Devillers ; Vida Dujmovic ; Hazel Everett ; Xavier Goaoc ; Sylvain Lazard ; Hyeon-Suk Na ; Sylvain Petitjean

Source :

SIAM journal on computing : (Print) [ 0097-5397 ] ; 2003.

RBID : Pascal:04-0091723

Descripteurs français

Pascal (Inist)
- Géométrie algorithmique, Approche probabiliste, Structure donnée, Représentation graphique, Infographie, Méthode cas pire, Loi Poisson, Polyèdre, Polygone, Visibilité 3 dimensions, Evénement visuel, Complexe visibilité, Complexité probable.

English descriptors

KwdEn :
- Computational geometry, Computer graphics, Data structure, Expected complexity, Graphics, Poisson distribution, Polygon, Polyhedron, Probabilistic approach, Three dimensional visibility, Visibility complex, Visual event, Worst case method.

Abstract

In this paper, we show that, amongst n uniformly distributed unit balls in R³, 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.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0097-5397`
A03		`1`		`@0 SIAM j. comput. : (Print)`
A05				`@2 32`
A06				`@2 6`
A08	`01`	`1`	`ENG`	`@1 The expected number of 3D visibility events is linear`
A11	`01`	`1`		`@1 DEVILLERS (Olivier)`
A11	`02`	`1`		`@1 DUJMOVIC (Vida)`
A11	`03`	`1`		`@1 EVERETT (Hazel)`
A11	`04`	`1`		`@1 GOAOC (Xavier)`
A11	`05`	`1`		`@1 LAZARD (Sylvain)`
A11	`06`	`1`		`@1 NA (Hyeon-Suk)`
A11	`07`	`1`		`@1 PETITJEAN (Sylvain)`
A14	`01`			`@1 INRIA Sophia-Antipolis, BP 93 @2 06902 Sophia-Antipolis @3 FRA @Z 1 aut.`
A14	`02`			`@1 School of Computer Science, McGill University @2 Ottawa, ON @3 CAN @Z 2 aut.`
A14	`03`			`@1 LORIA - INRIA Lorraine, CNRS, Univ. @2 Nancy @3 FRA @Z 3 aut. @Z 4 aut. @Z 5 aut. @Z 7 aut.`
A14	`04`			`@1 School of Computing, Soongsil University @2 Seoul @3 KOR @Z 6 aut.`
A20				`@1 1586-1620`
A21				`@1 2003`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 16063 @5 354000118836430110`
A44				`@0 0000 @1 © 2004 INIST-CNRS. All rights reserved.`
A45				`@0 24 ref.`
A47	`01`	`1`		`@0 04-0091723`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 SIAM journal on computing : (Print)`
A66	`01`			`@0 USA`
C01	`01`		`ENG`	@0 In this paper, we show that, amongst n uniformly distributed unit balls in R³, 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.
C02	`01`	`X`		`@0 001D02C03`
C02	`02`	`X`		`@0 001A02H01E`
C03	`01`	`X`	`FRE`	`@0 Géométrie algorithmique @5 01`
C03	`01`	`X`	`ENG`	`@0 Computational geometry @5 01`
C03	`01`	`X`	`SPA`	`@0 Geometría computacional @5 01`
C03	`02`	`X`	`FRE`	`@0 Approche probabiliste @5 02`
C03	`02`	`X`	`ENG`	`@0 Probabilistic approach @5 02`
C03	`02`	`X`	`SPA`	`@0 Enfoque probabilista @5 02`
C03	`03`	`X`	`FRE`	`@0 Structure donnée @5 03`
C03	`03`	`X`	`ENG`	`@0 Data structure @5 03`
C03	`03`	`X`	`SPA`	`@0 Estructura datos @5 03`
C03	`04`	`X`	`FRE`	`@0 Représentation graphique @5 04`
C03	`04`	`X`	`ENG`	`@0 Graphics @5 04`
C03	`04`	`X`	`SPA`	`@0 Grafo (curva) @5 04`
C03	`05`	`X`	`FRE`	`@0 Infographie @5 05`
C03	`05`	`X`	`ENG`	`@0 Computer graphics @5 05`
C03	`05`	`X`	`SPA`	`@0 Gráfico computadora @5 05`
C03	`06`	`X`	`FRE`	`@0 Méthode cas pire @5 06`
C03	`06`	`X`	`ENG`	`@0 Worst case method @5 06`
C03	`06`	`X`	`SPA`	`@0 Método caso peor @5 06`
C03	`07`	`X`	`FRE`	`@0 Loi Poisson @5 07`
C03	`07`	`X`	`ENG`	`@0 Poisson distribution @5 07`
C03	`07`	`X`	`SPA`	`@0 Ley Poisson @5 07`
C03	`08`	`X`	`FRE`	`@0 Polyèdre @5 08`
C03	`08`	`X`	`ENG`	`@0 Polyhedron @5 08`
C03	`08`	`X`	`SPA`	`@0 Poliedro @5 08`
C03	`09`	`X`	`FRE`	`@0 Polygone @5 09`
C03	`09`	`X`	`ENG`	`@0 Polygon @5 09`
C03	`09`	`X`	`SPA`	`@0 Polígono @5 09`
C03	`10`	`X`	`FRE`	`@0 Visibilité 3 dimensions @4 CD @5 96`
C03	`10`	`X`	`ENG`	`@0 Three dimensional visibility @4 CD @5 96`
C03	`11`	`X`	`FRE`	`@0 Evénement visuel @4 CD @5 97`
C03	`11`	`X`	`ENG`	`@0 Visual event @4 CD @5 97`
C03	`12`	`X`	`FRE`	`@0 Complexe visibilité @4 CD @5 98`
C03	`12`	`X`	`ENG`	`@0 Visibility complex @4 CD @5 98`
C03	`13`	`X`	`FRE`	`@0 Complexité probable @4 CD @5 99`
C03	`13`	`X`	`ENG`	`@0 Expected complexity @4 CD @5 99`
N21				`@1 061`

Format Inist (serveur)

NO :	PASCAL 04-0091723 INIST
ET :	The expected number of 3D visibility events is linear
AU :	DEVILLERS (Olivier); DUJMOVIC (Vida); EVERETT (Hazel); GOAOC (Xavier); LAZARD (Sylvain); NA (Hyeon-Suk); PETITJEAN (Sylvain)
AF :	INRIA Sophia-Antipolis, BP 93/06902 Sophia-Antipolis/France (1 aut.); School of Computer Science, McGill University/Ottawa, ON/Canada (2 aut.); LORIA - INRIA Lorraine, CNRS, Univ./Nancy/France (3 aut., 4 aut., 5 aut., 7 aut.); School of Computing, Soongsil University/Seoul/Corée, République de (6 aut.)
DT :	Publication en série; Niveau analytique
SO :	SIAM journal on computing : (Print); ISSN 0097-5397; Etats-Unis; Da. 2003; Vol. 32; No. 6; Pp. 1586-1620; Bibl. 24 ref.
LA :	Anglais
EA :	In this paper, we show that, amongst n uniformly distributed unit balls in R³, 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.
CC :	001D02C03; 001A02H01E
FD :	Géométrie algorithmique; Approche probabiliste; Structure donnée; Représentation graphique; Infographie; Méthode cas pire; Loi Poisson; Polyèdre; Polygone; Visibilité 3 dimensions; Evénement visuel; Complexe visibilité; Complexité probable
ED :	Computational geometry; Probabilistic approach; Data structure; Graphics; Computer graphics; Worst case method; Poisson distribution; Polyhedron; Polygon; Three dimensional visibility; Visual event; Visibility complex; Expected complexity
SD :	Geometría computacional; Enfoque probabilista; Estructura datos; Grafo (curva); Gráfico computadora; Método caso peor; Ley Poisson; Poliedro; Polígono
LO :	INIST-16063.354000118836430110
ID :	04-0091723

Links to Exploration step

Pascal:04-0091723

Le 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><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>
</affiliation>
</author>
<author><name sortKey="Dujmovic, Vida" sort="Dujmovic, Vida" uniqKey="Dujmovic V" first="Vida" last="Dujmovic">Vida Dujmovic</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation><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>
</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><inist:fA14 i1="04"><s1>School of Computing, Soongsil University</s1>
<s2>Seoul</s2>
<s3>KOR</s3>
<sZ>6 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Petitjean, Sylvain" sort="Petitjean, Sylvain" uniqKey="Petitjean S" first="Sylvain" last="Petitjean">Sylvain Petitjean</name>
<affiliation><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>
</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>
</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><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>
</affiliation>
</author>
<author><name sortKey="Dujmovic, Vida" sort="Dujmovic, Vida" uniqKey="Dujmovic V" first="Vida" last="Dujmovic">Vida Dujmovic</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation><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>
</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><inist:fA14 i1="04"><s1>School of Computing, Soongsil University</s1>
<s2>Seoul</s2>
<s3>KOR</s3>
<sZ>6 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Petitjean, Sylvain" sort="Petitjean, Sylvain" uniqKey="Petitjean S" first="Sylvain" last="Petitjean">Sylvain Petitjean</name>
<affiliation><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>
</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>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0097-5397</s0>
</fA01>
<fA03 i2="1"><s0>SIAM j. comput. : (Print)</s0>
</fA03>
<fA05><s2>32</s2>
</fA05>
<fA06><s2>6</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>The expected number of 3D visibility events is linear</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>DEVILLERS (Olivier)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>DUJMOVIC (Vida)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>EVERETT (Hazel)</s1>
</fA11>
<fA11 i1="04" i2="1"><s1>GOAOC (Xavier)</s1>
</fA11>
<fA11 i1="05" i2="1"><s1>LAZARD (Sylvain)</s1>
</fA11>
<fA11 i1="06" i2="1"><s1>NA (Hyeon-Suk)</s1>
</fA11>
<fA11 i1="07" i2="1"><s1>PETITJEAN (Sylvain)</s1>
</fA11>
<fA14 i1="01"><s1>INRIA Sophia-Antipolis, BP 93</s1>
<s2>06902 Sophia-Antipolis</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>School of Computer Science, McGill University</s1>
<s2>Ottawa, ON</s2>
<s3>CAN</s3>
<sZ>2 aut.</sZ>
</fA14>
<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>
</fA14>
<fA14 i1="04"><s1>School of Computing, Soongsil University</s1>
<s2>Seoul</s2>
<s3>KOR</s3>
<sZ>6 aut.</sZ>
</fA14>
<fA20><s1>1586-1620</s1>
</fA20>
<fA21><s1>2003</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>16063</s2>
<s5>354000118836430110</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 2004 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>24 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>04-0091723</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>SIAM journal on computing : (Print)</s0>
</fA64>
<fA66 i1="01"><s0>USA</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>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.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02C03</s0>
</fC02>
<fC02 i1="02" i2="X"><s0>001A02H01E</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Géométrie algorithmique</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Computational geometry</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Geometría computacional</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Approche probabiliste</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Probabilistic approach</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Enfoque probabilista</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Structure donnée</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Data structure</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Estructura datos</s0>
<s5>03</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Représentation graphique</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Graphics</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Grafo (curva)</s0>
<s5>04</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Infographie</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Computer graphics</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Gráfico computadora</s0>
<s5>05</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Méthode cas pire</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG"><s0>Worst case method</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA"><s0>Método caso peor</s0>
<s5>06</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Loi Poisson</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Poisson distribution</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="SPA"><s0>Ley Poisson</s0>
<s5>07</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE"><s0>Polyèdre</s0>
<s5>08</s5>
</fC03>
<fC03 i1="08" i2="X" l="ENG"><s0>Polyhedron</s0>
<s5>08</s5>
</fC03>
<fC03 i1="08" i2="X" l="SPA"><s0>Poliedro</s0>
<s5>08</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE"><s0>Polygone</s0>
<s5>09</s5>
</fC03>
<fC03 i1="09" i2="X" l="ENG"><s0>Polygon</s0>
<s5>09</s5>
</fC03>
<fC03 i1="09" i2="X" l="SPA"><s0>Polígono</s0>
<s5>09</s5>
</fC03>
<fC03 i1="10" i2="X" l="FRE"><s0>Visibilité 3 dimensions</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="10" i2="X" l="ENG"><s0>Three dimensional visibility</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="11" i2="X" l="FRE"><s0>Evénement visuel</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03>
<fC03 i1="11" i2="X" l="ENG"><s0>Visual event</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03>
<fC03 i1="12" i2="X" l="FRE"><s0>Complexe visibilité</s0>
<s4>CD</s4>
<s5>98</s5>
</fC03>
<fC03 i1="12" i2="X" l="ENG"><s0>Visibility complex</s0>
<s4>CD</s4>
<s5>98</s5>
</fC03>
<fC03 i1="13" i2="X" l="FRE"><s0>Complexité probable</s0>
<s4>CD</s4>
<s5>99</s5>
</fC03>
<fC03 i1="13" i2="X" l="ENG"><s0>Expected complexity</s0>
<s4>CD</s4>
<s5>99</s5>
</fC03>
<fN21><s1>061</s1>
</fN21>
</pA>
</standard>
<server><NO>PASCAL 04-0091723 INIST</NO>
<ET>The expected number of 3D visibility events is linear</ET>
<AU>DEVILLERS (Olivier); DUJMOVIC (Vida); EVERETT (Hazel); GOAOC (Xavier); LAZARD (Sylvain); NA (Hyeon-Suk); PETITJEAN (Sylvain)</AU>
<AF>INRIA Sophia-Antipolis, BP 93/06902 Sophia-Antipolis/France (1 aut.); School of Computer Science, McGill University/Ottawa, ON/Canada (2 aut.); LORIA - INRIA Lorraine, CNRS, Univ./Nancy/France (3 aut., 4 aut., 5 aut., 7 aut.); School of Computing, Soongsil University/Seoul/Corée, République de (6 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>SIAM journal on computing : (Print); ISSN 0097-5397; Etats-Unis; Da. 2003; Vol. 32; No. 6; Pp. 1586-1620; Bibl. 24 ref.</SO>
<LA>Anglais</LA>
<EA>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.</EA>
<CC>001D02C03; 001A02H01E</CC>
<FD>Géométrie algorithmique; Approche probabiliste; Structure donnée; Représentation graphique; Infographie; Méthode cas pire; Loi Poisson; Polyèdre; Polygone; Visibilité 3 dimensions; Evénement visuel; Complexe visibilité; Complexité probable</FD>
<ED>Computational geometry; Probabilistic approach; Data structure; Graphics; Computer graphics; Worst case method; Poisson distribution; Polyhedron; Polygon; Three dimensional visibility; Visual event; Visibility complex; Expected complexity</ED>
<SD>Geometría computacional; Enfoque probabilista; Estructura datos; Grafo (curva); Gráfico computadora; Método caso peor; Ley Poisson; Poliedro; Polígono</SD>
<LO>INIST-16063.354000118836430110</LO>
<ID>04-0091723</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000731 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000731 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Corpus
   |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.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

The expected number of 3D visibility events is linear

The expected number of 3D visibility events is linear

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri