The PLS library contains the definition and the implementation of piecewise-linear systems. The library allows the programmer to build a piecewise-linear system, associate data with contained polytopes and query system with powerful library functions. PLSs are a very general way to represent

A **polytope** a finite region of
n-dimensional space enclosed by a finite number of hyperplanes. In
increasing dimensions, examples of polytopes are **points** (0d), **line
segments** (1d), **polygons** (2d), **polyhedrons** (3d).
A **convex polytope** is the convex hull of a set
of vertices in n-dimensional space.

A **PLS (piecewise-linear
system) ** is a set of polytopes S with the following properties.

- The set
*S*is closed under taking boundaries, i.e., for each*P*in*S*the boundary of*P*is a union of polytopes in*S*. -
*S*is closed under intersection. - If
dim(
*P*Intersect*Q*) = dim(*P*) then*P*is fully included in*Q*, and dim(*P*) < dim(*Q*).

Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walkington, and Han Wang, Control volume meshes using sphere packing: generation, refinement and coarsening. Proc. 5th Int. Meshing Roundtable, Sandia Nat. Lab., Oct 1996, pp. 47-61.although in that paper the polytopes were defined to be convex. We do not impose this limitation.

Here is an example of a PLS with non-convex polytopes

It is taken from the paper

Jonathan Richard Shewchuk, Tetrahedral Mesh Generation by Delaunay Refinement. Proceedings of the Fourteenth Annual ACM Symposium on Computational Geometry (Minneapolis, Minnesota), pages 86-95, June 1998.Note that in addition to the 3d object, each of the points, edges and faces is a polytope. Some of the polytopes are boundaries of higher-dimensional polytopes (such as the upper surface on the left) and some are internal constraints (such as the the lone edge embedded in the upper surface). A polytope can both be a boundary and an internal constraint (such as the other two joined edges embedded in the upper surface, which are internal constraints for the upper surface and boundary constrains for the two rectangles that penetrate the body).

Each polytope in a PLS is fully defined by a set of **boundary and internal constraints** , where each
constraint corresponds to a polytope. In fact, the representation of
a PLS is basically a DAG in which each node is a polytope and each
edge represents a constraint. There are two types of edges corresponding
to boundary and internal constraints. Edges always point from higher
to lower dimensional polytopes. The leaves of the DAG (nodes with out-degree zero),
are all zero-dimensional polytopes (i.e. points).

Using the library functions,
the programmer can build a PLS by adding and removing polytopes and
specifying the boundary and internal constraints. The library also
allows the programmer to associate data with each
polytope using the supplied `PolytopeIdTable`

.

Back to the PSciCo homepage.