Skip to Main content Skip to Navigation
New interface
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, Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology
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
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, November 29, 2007 - 5:20:27 PM
Last modification on : Thursday, January 20, 2022 - 5:30:14 PM
Long-term archiving on: : 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, 2007, 17 (4), pp.297-304. ⟨10.1142/S0218195907002343⟩. ⟨inria-00192927⟩



Record views


Files downloads