3.1.2 Semi-Algebraic Models

In both the polygonal and polyhedral models, was a linear
function. In the case of a semi-algebraic model for a 2D world,
can be any polynomial with real-valued coefficients and variables
and . For a 3D world, is a polynomial with variables , ,
and . The class of semi-algebraic models includes both polygonal
and polyhedral models, which use first-degree polynomials. A point
set determined by a single polynomial primitive is called an
*algebraic set*; a point set that can be obtained by a finite
number of unions and intersections of algebraic sets is called a
*semi-algebraic set*.

Consider the case of a 2D world. A solid representation can be
defined using *algebraic primitives* of
the form

As an example, let . In this case, represents a disc of radius that is centered at the origin. This corresponds to the set of points for which , as depicted in Figure 3.4a.

(3.11) |

For , , and , the familiar circle and ellipse equations were multiplied by to yield algebraic primitives for all points outside of the circle or ellipse. The shaded region is represented as

In the case of semi-algebraic models, the intersection of primitives does not necessarily result in a convex subset of . In general, however, it might be necessary to form by taking unions and intersections of algebraic primitives.

A logical predicate, , can once again be formed, and collision checking is still performed in time that is linear in the number of primitives. Note that it is still very efficient to evaluate every primitive; is just a polynomial that is evaluated on the point .

The semi-algebraic formulation generalizes easily to the case of a 3D world. This results in algebraic primitives of the form

which can be used to define a solid representation of a 3D obstacle and a logical predicate .

Equations (3.10) and (3.13) are sufficient to express any model of interest. One may define many other primitives based on different relations, such as , , , , and ; however, most of them do not enhance the set of models that can be expressed. They might, however, be more convenient in certain contexts. To see that some primitives do not allow new models to be expressed, consider the primitive

The right part may be alternatively represented as , and may be considered as a new polynomial function of , , and . For an example that involves the relation, consider the primitive

It can instead be constructed as , in which

and

The relation does add some expressive power if it is used to construct primitives.

Steven M LaValle 2012-04-20