## 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 (3.10)

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. Example 3..1 (Gingerbread Face)   Consider constructing a model of the shaded region shown in Figure 3.4b. Let the center of the outer circle have radius and be centered at the origin. Suppose that the eyes'' have radius and and are centered at and , respectively. Let the mouth'' be an ellipse with major axis and minor axis and is centered at . The functions are defined as (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 (3.12) 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 (3.13)

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 (3.14)

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 (3.15)

It can instead be constructed as , in which (3.16)

and (3.17)

The relation does add some expressive power if it is used to construct primitives.3.2 It is needed to construct models that do not include the outer boundary (for example, the set of all points inside of a sphere, which does not include points on the sphere). These are generally called open sets and are defined Chapter 4.

Steven M LaValle 2012-04-20