{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T08:24:12Z","timestamp":1791188652291,"version":"4.1.0"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2003,1]]},"abstract":"<jats:p>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].<\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1137\/s0097539702419662","type":"journal-article","created":{"date-parts":[[2003,11,17]],"date-time":"2003-11-17T21:00:45Z","timestamp":1069102845000},"page":"1586-1620","source":"Crossref","is-referenced-by-count":9,"title":["The Expected Number of 3D Visibility Events Is Linear"],"prefix":"10.1137","volume":"32","author":[{"given":"Olivier","family":"Devillers","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vida","family":"Dujmovic","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hazel","family":"Everett","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xavier","family":"Goaoc","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sylvain","family":"Lazard","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hyeon-Suk","family":"Na","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sylvain","family":"Petitjean","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009427"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"B. Aronov, H. Br\u00f6nnimann, A. Chang, and Y.\u2010J. Chiang,\n                      Cost prediction for ray shooting\n                      , in Proceedings of the ACM Symposium on Computational Geometry, Barcelona, Spain, 2002, pp. 293\u2013302.","DOI":"10.1145\/513400.513438"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00020-0"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-8493(99)00093-X"},{"key":"R5","unstructured":"O. Devillers, B. Mourrain, F. P. Preparata, and P. Trebuchet,\n                      On Circular Cylinders by Four or Five Points in Space\n                      , Rapport de recherche 4195, INRIA, Le Chesnay Cedex, France, 2001."},{"key":"R6","unstructured":"O. Devillers and P. Ramos,\n                      private communication\n                      , 2001."},{"key":"R7","unstructured":"F. Durand,\n                      A Multidisciplinary Survey of Visibility\n                      , ACM SIGGRAPH course notes, Visibility, Problems, Techniques, and Applications, 2000."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"F. Durand, G. Drettakis, and C. Puech,\n                      The visibility skeleton: A powerful and efficient multi\u2010purpose global visibility tool\n                      , in Proceedings of ACM SIGGRAPH\u201997, Los Angeles, CA, 1997, pp. 89\u2013100.","DOI":"10.1145\/258734.258785"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/508357.508362"},{"key":"R10","volume-title":"Probability and random processes","author":"Grimmett G.","year":"1992"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"N. Holzschuch, F. Sillion, and G. Drettakis,\n                      An efficient progressive refinement strategy for hierarchical radiosity\n                      , in Photorealistic Rendering Techniques, G. Sakas, P. Shirley, and S. M\u00fcller, eds., Springer, Berlin, 1995, pp. 353\u2013357.","DOI":"10.1007\/978-3-642-87825-1_26"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1109\/34.273735"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010090"},{"key":"R14","unstructured":"The Maple System\n                      , Waterloo Maple Software, http:\/\/www.maplesoft.com\/."},{"key":"R15","volume-title":"An introduction to geometrical probability","author":"Mathai A.","year":"1999"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-8493(99)00089-8"},{"key":"R17","volume-title":"Probability, random variables, and stochastic processes","author":"Papoulis Athanasios","year":"1984"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187036"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Sylvain Petitjean, The number of views of piecewise\u2010smooth algebraic objects, Lecture Notes in Comput. Sci., Vol. 900, Springer, Berlin, 1995, 571\u201358296i:68084","DOI":"10.1007\/3-540-59042-0_106"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF00054919"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195996000204"},{"key":"R22","volume-title":"Integral geometry and geometric probability","author":"Santal\u00f3 Luis","year":"1976"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"L. Szirmay\u2010Kalos, V. Havran, B. Balazs, and L. Szecsi,\n                      On the efficiency of ray\u2010shooting acceleration schemes\n                      , in Proceedings of the Spring Conference on Computer Graphics, Budmerice, Slovakia, 2002, pp. 89\u201398.","DOI":"10.1145\/584458.584475"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02684409"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539702419662","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:21:05Z","timestamp":1787336465000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539702419662"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["10.1137\/S0097539702419662"],"URL":"https:\/\/doi.org\/10.1137\/s0097539702419662","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}