3532 articles – 5253 Notices  [english version]

inria-00336502, version 1

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

Linqiao Zhang () a1, Hazel Everett () b1, Sylvain Lazard () 1, Christophe Weibel c2, Sue Whitesides 3

16th Annual European Symposium on Algorithms - ESA 2008 LNCS 5193/2008 (2008) 805--816

Résumé : 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)$.

  • a –  INRIA
  • b –  Université Nancy II
  • c –  McGill University
  • 1 :  VEGAS (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 2 :  Math Department - McGill University
  • McGill University
  • 3 :  School of Computer Science [Quebec] (SOCS)
  • McGill University
  • Domaine : Informatique/Géométrie algorithmique
 
  • inria-00336502, version 1
  • oai:hal.inria.fr:inria-00336502
  • Contributeur : 
  • Soumis le : Mardi 4 Novembre 2008, 12:18:13
  • Dernière modification le : Dimanche 20 Décembre 2009, 15:04:28