Published in

World Scientific Publishing, International Journal of Computational Geometry and Applications, 04(17), p. 297-304

DOI: 10.1142/s0218195907002343

Links

Tools

Export citation

Search in Google Scholar

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint

Journal article published in 2005 by Olivier Devillers ORCID, Vida Dujmovic, Hazel Everett, Samuel Hornus, Sue Whitesides, Steve Wismath
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

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 .