3532 articles – 5253 Notices  [english version]

inria-00511233, version 1

A Succinct 3D Visibility Skeleton

Sylvain Lazard () 1, Christophe Weibel a, 2, Sue Whitesides () 3, Linqiao Zhang () a, 4

Discrete Mathematics, Algorithms and Applications (DMMA) 2, 4 (2010) 1-23

Résumé : The 3D visibility skeleton is a data structure that encodes the global visibility information of a set of 3D objects. While it is useful in answering global visibility queries, its large size often limits its practical use. In this paper, we address this issue by proposing a subset of the visibility skeleton, which is empirically about $25\%$ to $50\%$ of the whole set. We show that the rest of the data structure can be recovered from the subset as needed, partially or completely. The running time complexity, which we analyze in terms of output size, is efficient. We also prove that the subset is minimal in the sense that the complexity bound ceases to hold if the subset is restricted further.

  • a –  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 :  Department of Computer Science (UVic)
  • University of Victoria
  • 4 :  School of Computer Science [Quebec] (SOCS)
  • McGill University
  • Domaine : Informatique/Géométrie algorithmique
 
  • inria-00511233, version 1
  • http://hal.inria.fr/inria-00511233
  • oai:hal.inria.fr:inria-00511233
  • Contributeur : Sylvain Lazard <>
  • Soumis le : Mardi 24 Août 2010, 11:30:09
  • Dernière modification le : Mercredi 19 Janvier 2011, 15:21:27