Kinetic Visible Set Maintenance in the Plane

Olaf Hall-Holt

Submitted for publication


This paper examines the problem of maintaining the visible set of a moving observer among n non-overlapping convex objects in the plane, where the motion is specified on-line using constant degree pseudo-algebraic trajectories. The visible zone is a linear size visibility structure analogous to a topological line through the visibility complex. Initializing a visible zone requires O(n log n) time, and querying a visible zone for the visible set requires time proportional to the size of the visible set. For static scenes where the angle between two bitangents connected to a single object can be bounded from below by a constant, the cost of maintaining a visible zone is proportional to the number of changes in the visible set. The visible zone can also be maintained for moving objects, without increasing the cost associated with changes in the observer motion.

Full paper as compressed Postscript, 564145 bytes compressed, 5445732 bytes uncompressed.