TABLE OF CONTENTS In this section we discuss our models of motion, define pseudo-triangulations, and discuss how we maintain them as objects move continuously.
There are two reasons for defining motion models. First, we need to be able to compute the certificate failure times. Second, we wish to be able to give bounds on the maximum number of events that can happen. We describe the model for which we bound the number of events first.
A rigid polygon P is described at rest by a reference point o, by an orthonormal basis ( x, y), and by the coordinates ( p x, p y) of each vertex p of P in this orthonormal frame centered at o. An algebraic motion of P is given by a trajectory o( t) of the reference point and by an orthonormal basis ( x( t), y( t)), such that the coordinates of o, x, y are algebraic functions of time of bounded degree. The position of v at time t, denoted by v( t), is o( t) + p xx( t) + p yy( t). If P is a point, then o is the same as P and the vectors x, y are not needed. We will use P(
