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 expected asymptotic number of free bitangents (which correspond to the 0-faces of the visibility complex) among unit discs or polygons of bounded aspect ratio 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 :
Rapport
[Research Report] RR-5822, INRIA. 2006, pp.17
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00070203
Contributeur : Rapport de Recherche Inria <>
Soumis le : vendredi 19 mai 2006 - 19:29:12
Dernière modification le : jeudi 11 janvier 2018 - 06:20:14
Document(s) archivé(s) le : dimanche 4 avril 2010 - 20:34:34

Fichiers

Identifiants

  • HAL Id : inria-00070203, version 1

Collections

Citation

Hazel Everett, Sylvain Lazard, Sylvain Petitjean, Linqiao Zhang. On the Expected Size of the 2D Visibility Complex. [Research Report] RR-5822, INRIA. 2006, pp.17. 〈inria-00070203〉

Partager

Métriques

Consultations de la notice

250

Téléchargements de fichiers

146