#
Kinetic Visible Set Maintenance in the Plane

##
Olaf Hall-Holt

Submitted for publication

**Abstract**

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.

*olaf@graphics.stanford.edu*