MAINTAINING VISIBILITY INFORMATION OF PLANAR POINT SETS WITH A MOVING VIEWPOINT
Olivier Devillers, Vida Dujmović, Hazel Everett, Samuel Hornus, Sue H. Whitesides, Steve Wismath · International Journal of Computational Geometry & Applications · 2007
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 .