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 Steve Wismath 5
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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [7 references]  Display  Hide  Download
Contributor : Olivier Devillers <>
Submitted on : Thursday, November 29, 2007 - 5:20:27 PM
Last modification on : Wednesday, February 13, 2019 - 2:58:21 PM
Document(s) archivé(s) le : Monday, April 12, 2010 - 5:34:23 AM


Files produced by the author(s)




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⟩



Record views


Files downloads