MAINTAINING VISIBILITY OF A POLYGON WITH A MOVING POINT-OF-VIEW

The following problem is studied in this paper: Given a scene with an n-vertex simple polygon and a trajectory path in the plane, construct a data structure for reporting the perspective view from a moving poin t along the trajectory. We present conceptually simple algorithms for the cases of this problem in which the trajectory path consists of sev eral line segments or of a conic curve that contains the polygon. Our algorithms take O(n log n) time and O(n) space. We also prove that the problem of reporting perspective views from successive points along a trajectory path takes Omega(n log n) time in the worst case in the al gebraic computation tree model. Our data structure reports the view fr om any query point on the trajectory in O(k + log n) time for a view o f size k. (C) 1998 Elsevier Science B.V.