On the Size of the 3D Visibility Skeleton: Experimental Results

Abstract : The 3D visibility skeleton is a data structure used to encode global visibility information about a set of objects. Previous theoretical results have shown that for $k$ convex polytopes with $n$ edges in total, the worst case size complexity of this data structure is $\Theta(n^2 k^2) $ [Brˆnnimann et al. 07]; whereas for $k$ uniformly distributed unit spheres, the expected size is $\Theta(k)$ [Devillers et al. 03]. In this paper, we study the size of the visibility skeleton experimentally. Our results indicate that the size of the 3D visibility skeleton, in our setting, is $ C\,k\sqrt{n\,k}$, where $C$ varies with the scene density but remains small. % This is the first experimentally determined asymptotic estimate of the size of the 3D visibility skeleton for reasonably large $n$ and expressed in terms of both $n$ and $k$. We suggest theoretical explanations for the experimental results we obtained. Our experiments also indicate that the running time of our implementation is $O(n^{3/2} k\log k)$, while its worst-case running time complexity is $O(n^2k^2 \log k)$.
Type de document :
Communication dans un congrès
16th Annual European Symposium on Algorithms - ESA 2008, Sep 2008, Karlsruhe, Germany. Springer, LNCS 5193/2008, pp.805--816, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-87744-8_67〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00336502
Contributeur : Sylvain Lazard <>
Soumis le : mardi 4 novembre 2008 - 12:18:13
Dernière modification le : jeudi 11 janvier 2018 - 06:20:14
Document(s) archivé(s) le : lundi 7 juin 2010 - 22:43:13

Fichier

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

Identifiants

Collections

Citation

Linqiao Zhang, Hazel Everett, Sylvain Lazard, Christophe Weibel, Sue Whitesides. On the Size of the 3D Visibility Skeleton: Experimental Results. 16th Annual European Symposium on Algorithms - ESA 2008, Sep 2008, Karlsruhe, Germany. Springer, LNCS 5193/2008, pp.805--816, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-87744-8_67〉. 〈inria-00336502〉

Partager

Métriques

Consultations de la notice

269

Téléchargements de fichiers

114