On the Expected Size of the 2D Visibility Complex - Archive ouverte HAL Access content directly
Journal Articles International Journal of Computational Geometry and Applications Year : 2007

On the Expected Size of the 2D Visibility Complex

(1) , (1) , (1) , (1)
1

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.
Vignette du fichier
2007 Expected Size of the 2D Visibility Complex.png (33.08 Ko) Télécharger le fichier Fichier principal
Vignette du fichier
2Dcomplex_revised.pdf (221.87 Ko) Télécharger le fichier
Format : Figure, Image
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00103926 , version 1 (19-11-2007)

Identifiers

Cite

Hazel Everett, Sylvain Lazard, Sylvain Petitjean, Linqiao Zhang. On the Expected Size of the 2D Visibility Complex. International Journal of Computational Geometry and Applications, 2007, 17 (4), pp.361-381. ⟨10.1142/S0218195907002380⟩. ⟨inria-00103926⟩
106 View
122 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More