Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download
Contributor : Olivier Devillers <>
Submitted on : Thursday, November 29, 2007 - 5:20:27 PM
Last modification on : Thursday, March 26, 2020 - 8:49: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