List of routines List of routinesGEOMETRIC BOUNDING TOOLBOX, Version 5.1
ADD adds two polytopes or ellipsoids
BOUNDED tests whether a polyhedron is polytope
CENTRE computes the centre (mass, lp-Chebishev centres,
p>1) of a polytope or ellipsoid
CONVHULL computes the convex-hull polytope of a set of
points or its approximation by different methods
DEFBOX defines an axis aligned box in GBT format
DEFELL defines an ellipsoid in GBT format
DEFPIPE defines a parallelepiped in polytope format in GBT
DEFSIMP defines a regular simplex in GBT format
DIAMETER computes the diameter of a polytope or ellipsoid
DIREXT computes the extreme of an ellipsoid or polytope in
a given direction
DIRGEN generates roughly uniformly distributed directions
ELLIBND performs various types of recursive ellipsoidal
updating
ELLICOV extracts the covariance of an ellipsoid from its
GBT format
FACES extracts the hyperplane faces of a polyhedron
FACET computes the ith facet of a polytope
INEL computes the volume-optimal inner bounding
ellipsoid of a polytope
INTERSCT intersects two polyhedra or ellipsoids
MAXFACE computes the maximum possible number of faces of a
polytope
MAXVERT computes the maximum possible number of vertices of
a polytope
MOVE translates or rotates an ellipsoid or a polyhedron
PDUAL computes the dual of a polytope
PERSPECT displays the shaded 3D view of a polytope
POLYBND performs recursive polytope updating
POLYHEDR performs recursive polyhedron updating
POLYHLIM performs hyperplane limited recursive polytope
updating
POLYREG performs recursive updating of regular polyhedra
POLYSLIM performs support limited recursive polytope
updating
PROJECT projects an ellipsoid or a polytope onto a linear
subspace
PR2DL solves dual LP problems
RANGES computes the smallest axis aligned box around an
ellipsoid or polytope
RELAX recovers a polyhedron from a polytope by removing
one of its faces
SEL computes the volume-minimal outer bounding
ellipsoid to a given polytope
SIMSTDES an efficient simplex method for LP problems
SLICEGBT computes the intersection of an ellipsoid or
polytope and a hyperplane
STEL computes the volume-optimal minimal invariant
outer-ellipsoid to a polytope
SUBTRACT internal difference of two polytopes or ellipsoids
TRANSF performs linear transformation on a polyhedron or
ellipsoid
VERTICES extracts the vertices of a polyhedron from its GBT
format
VIEWGBT displays several ellipsoids or polytopes on the
screen (2D or 3D projections) using their
edge-graphs
VOLUME computes the volume of an ellipsoid or polytope
Format-converting routines:
CAN transforms general LP problems into standard
form
CONVP_PH converts type 2 format to type 4 format of
polyhedra
CONVPH_P converts type 4 format to type 2 format of
polyhedra
DECAN transforms the LP solution back into original
variables
For most routines *.m there is a demo file d_*.m supplied on
the distribution disk. gbtdemo.m activates a menu of demos.
General description of the aims of the package
The Geometric Bounding Toolbox (GBT) has sprung from the recognition
of demand among engineers and researchers for a simple to use
software to perform operations on multidimensional geometric objects.
GBT is a set of routines in MATLABTM to perform operations on
polytopes, polyhedra and ellipsoids.
User friendliness was one of the major aims. The geometric objects
have a single name and no details of specifications have to be
remembered.
Another aim was to include the best available algorithms in the
area. The numerical procedures have been selected either for their
best numerical properties or for the sake of elegance and simplicity.
Sometimes compromise had to be made between speed and accuracy
or memory requirement and accuracy. The usefulness of the package
is not difficult to appreciate: there is an increasing number
of areas of control and digital signal processing where operations
with polytopes, ellipsoids and other geometric bodies play an
increasing role. Design of robust and adaptive filters and non-linear
controllers might need the calculation of parameter or state regions
in the forms of polytopes, ellipsoids and rectangular boxes. Also
linear optimisation, numerically robust and stable computations,
computational complexity are potential areas of applications.
The algorithmic contents of the routines can be roughly grouped
into those which
(i) perform operations on polytopes and polyhedra
(ii) perform operations with ellipsoids
(iii) compute approximate ellipsoids or polytopes to solve various
problems
(iv) compute characteristics of a high dimensional (>6) geometric
objects by solving linear programming (LP) problems.
The operations can be grouped into
(a) updating, i.e. intersecting with half-spaces,
(b) unitary operations on geometric objects,
(c) binary operations on geometric objects.
An efficient set of LP routines has been added to the existing
core of routines in Version 1.0 of GBT. The reason for this is
that in higher dimensions (>6), the number of vertices and
faces of a polyhedron can increase to such an extent, that speed
and memory limits of today's computers make the operations impracticable.
In many higher dimensional problems, however, there is no need
to compute all the faces or vertices of a polytope: instead, it
might be sufficient to compute some characteristics only (for
instance the extreme vertex in a certain direction or the smallest
box around the polytope etc.). It was felt therefore that to make
the package really powerful, a set of efficient LP routines should
be added. These are described in Chapter 4.
On the 240 page manual
Chapter 1 of describes the internal structure of a matrix representing
polyhedra of different types. This description is important to
now from the very beginning of using GBT in order to understand
how the routines work. There are basically three types of the
matrix representations of polyhedra. The first two types handle
only simple polyhedra, i.e. which have exactly d
edges at each vertex (if d is the dimension of the space):
type 2 - is used for simple bounded polyhedra and it lists
the planes of the facets, the vertices and a vertex-facet adjacency
list.
type 4 - allows also for the representation of simple unbounded
polyhedra and it adds a vertex-vertex adjacency list to the content
of the type 2 representation.
type 6 - is used for the representation of polyhedra
which might have more than d edges joining at a vertex.
Chapter 2 explains how the updating of a polyhedron with a half-space
works in different algorithms. Beside the three main routines
(POLYBND, POLYHEDR, POLYREG) several other routines are also explained
which allow for the limited complexity and approximate computations
of polytopes (POLYSLIM, POLYHLIM) and the inverse operation of
updating (RELAX).
Updating of ellipsoids by a slice according to different optimality
criteria (POLYBND) is explained in Chapter 3. The algorithms of
different types of updating are summarised in a systematic manner
. A second major topic within Chapter 3 in Section 3.4 is the
computation of optimal inner and outer bounding ellipsoids to
a polytope (INEL, SEL, STEL).
Chapter 4 is devoted to treatment of LP problems. The use of the
simplex algorithm (SIMSTDES) and related utilities (CAN, PR2DL,
DECAN) are explained and their use illustrated on examples
Chapter 5 contains descriptions of operations of various kind.
Since computation of a convex hull and the resulting polytope
itself can sometimes be too complex, therefore the option of computing
approximate solutions (CONVHULL) has been introduced with respect
to Version 4.0 of GBT. Quick definitions of simple boxes, parallelepipeds,
ellipsoids and simplexes makes initialisation simpler in many
applied problems (DEFBOX, DEFELL, DEFPIPE, DEFSIMP). Measures
of size include computations of the diameter, volume and the width
and extreme points of an object in a given direction (DIAMETER,
VOLUME, DIREXT). Extracting components of a geometric object can
be useful in various situations (VERTICES, FACES, FACET, ELLICOV).
Feature extraction includes computing various types of the centre
of an object, the ranges of the vector components in the object,
the projections onto a subspace and the cross section with a hyperplane.
(CENTRE, RANGES, PROJECT, SLICEGBT). Presentation of a polytope
or ellipsoid on the screen is possible by VIEWGBT, the use of
which is demonstrated on many examples throughout this manual.
Unitary operations include the computations of the result of moving
an rotating the object, performing a one-to-one affine transformation
on the object and computing the dual of a polytope (MOVE, TRANSF,
PDUAL).
Binary operations include the addition, intersection and subtraction
of two objects (ADD, TRANSF, SUBTRACT). For ellipsoids the latter
results in approximate computations.
Numerical problems: precision and efficiency
The intention of the authors was to write a set of routines which
work fast and accurately and are easy to use. It turned out that
various compromises had to be made and the dream of the authors
was in many cases impossible to realise because of objective limits.
The main compromise is made between speed and accuracy of computation.
Indeed, that is why the different types of polytope formats are
introduced:
As the type of matrix format of the object description increases,
the complexity of the description increases too, and the associated
memory efficiency & speed decreases.
Type formats 2 and 4 are different in their
use from type 6:
POLYBND and POLYHEDR use type 2 and 4, respectively.
These were designed to handle irregular simple polytopes which
have exactly d edge at each vertex.
POLYREG updates regular polytopes as well. The simple way of polytope
representation, which exist in POLYBND and POLYHEDR is lost in
POLYREG.
The origin of this distinction is that it is only in the idealised
world of mathematics that one can decide whether a new hyperplane
crosses a vertex. In practice, one has regular polytopes only
with a given accuracy and the decision is up to this accuracy.
The accuracy of computation will not practically improve by using
type 6. When using type 2 and 4 it is assumed
that a new hyperplane never crosses a vertex. Small random errors
of magnitude 10-10 are introduced to make sure that crossing never
happens. The magnitude of the random errors introduced can be
set by the "inerr" input variable of POLYBND and POLYHEDR.
CONVHULL is the most computationally demanding and sensitive routine
from all and it is best used by defining the order of approximation
to compute approximate polytope solutions, the accuracy of which
can be made arbitrary high.