Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue International Journal of Computational Geometry and Applications Année : 2007

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint

Résumé

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.
Fichier principal
Vignette du fichier
hal.pdf (129.42 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00192927 , version 1 (29-11-2007)

Identifiants

Citer

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, 2007, 17 (4), pp.297-304. ⟨10.1142/S0218195907002343⟩. ⟨inria-00192927⟩
417 Consultations
421 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More