On the Expected Size of the 2D Visibility Complex

Hazel Everett 1 Sylvain Lazard 1 Sylvain Petitjean 1 Linqiao Zhang 1
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We study the expected size of the 2D visibility complex of randomly distributed objects in the plane. We prove that the asymptotic expected number of free bitangents (which correspond to 0-faces of the visibility complex) among unit discs (or polygons of bounded aspect ratio and similar size) is linear and exhibit bounds in terms of the density of the objects. We also make an experimental assessment of the size of the visibility complex for disjoint random unit discs. We provide experimental estimates of the onset of the linear behavior and of the asymptotic slope and $y$-intercept of the number of free bitangents in terms of the density of discs. Finally, we analyze the quality of our estimates in terms of the density of discs.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2007, 17 (4), pp.361-381. 〈10.1142/S0218195907002380〉
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger

2007 Expected Size of the 2D Visibility Complex.png
2007 Expected Size of the 2D Visibility Complex.png
https://hal.inria.fr/inria-00103926
Contributeur : Sylvain Lazard <>
Soumis le : lundi 19 novembre 2007 - 17:36:06
Dernière modification le : mardi 30 octobre 2018 - 10:28:22

Fichiers

2Dcomplex_revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | LORIA | UNIV-LORRAINE

Citation

Hazel Everett, Sylvain Lazard, Sylvain Petitjean, Linqiao Zhang. On the Expected Size of the 2D Visibility Complex. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2007, 17 (4), pp.361-381. 〈10.1142/S0218195907002380〉. 〈inria-00103926〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

303

Téléchargements de fichiers

150

Contact


archive-ouverte@inria.fr