inria-00103926, version 1
On the Expected Size of the 2D Visibility Complex
Hazel Everett
a, 1Sylvain Lazard
b, 1Sylvain Petitjean c, 1Linqiao Zhang b, 1
International Journal of Computational Geometry & Applications 17, 4 (2007) 361-381
Résumé : 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.
- a – Université Nancy II
- b – INRIA
- c – CNRS
- 1 : VEGAS (INRIA Lorraine - LORIA)
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine
- Domaine : Informatique/Géométrie algorithmique
- inria-00103926, version 1
- http://hal.inria.fr/inria-00103926
- oai:hal.inria.fr:inria-00103926
- Contributeur : Sylvain Lazard
- Soumis le : Lundi 19 Novembre 2007, 17:36:06
- Dernière modification le : Dimanche 20 Décembre 2009, 16:08:34






Documents associés
Exporter