Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint

Olivier Devillers 1 Vida Dujmovic 2 Hazel Everett 3 Samuel Hornus 4 Sue Whitesides 5 Steve Wismath 6
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
3 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
4 ARTIS - Acquisition, representation and transformations for image synthesis
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
Abstract : Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. In linear space, and after O(n log n) preprocessing time, our solution maintains the view at a cost of O(log n) amortized time (resp. O(log^2 n) worst case time) for each change. Our algorithm can also be used to maintain the set of points sorted according to their distance to q.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2007, 17 (4), pp.297-304. 〈10.1142/S0218195907002343〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00192927
Contributeur : Olivier Devillers <>
Soumis le : jeudi 29 novembre 2007 - 17:20:27
Dernière modification le : vendredi 24 novembre 2017 - 13:28:52
Document(s) archivé(s) le : lundi 12 avril 2010 - 05:34:23

Fichier

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

Identifiants

Collections

Citation

Olivier Devillers, Vida Dujmovic, Hazel Everett, Samuel Hornus, Sue Whitesides, et al.. Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2007, 17 (4), pp.297-304. 〈10.1142/S0218195907002343〉. 〈inria-00192927〉

Partager

Métriques

Consultations de la notice

554

Téléchargements de fichiers

404