Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint

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.