List of routines List of routinesGEOMETRIC BOUNDING TOOLBOX, Version 5.1
ADD adding two polytopes or ellipsoids algebraically
BOUNDED tests whether a polyhedron is polytope
CENTRE calculating the centre of a polytope or ellipsoid
(mass, Chebishev)
CONVHULL calculating the polytope convex-hull of a set of points
by different methods
DEFBOX defining an axis aligned box in GBT polyhedron format
DEFELL defining an ellipsoid in GBT format
DEFPIPE defining a parallelepiped in polytope format in GBT
DEFSIMP defining a regular simplex in GBT format
DIAMETER calculating the diameter of a polytope or ellipsoid
DIREXT calculating the extremum of an ellipsoid or polytope in a
given direction
DIRGEN generating roughly uniformly distributed directions
ELLIBND to perform various types of recursive ellipsoidal
updating
ELLICOV extracting the covariance of an ellipsoid from its GBT format
FACES extracting the hyperplane faces of a polyhedron
FACET calculating the i-th facet of a polytope
INEL calculating the optimal inner bounding ellipsoid of a
polytope
INTERSCT intersecting two polyhedra or ellipsoids
MAXFACE maximum possible number of faces of a polytope
MAXVERT maximum possible number of vertices of a polytope
MOVE translating or rotating an ellipsoid or a polyhedron
PDUAL calculating the dual of a polytope
POLYBND to perform recursive polytope updating
POLYHEDR to perform recursive polyhedron updating
POLYHLIM to perform hyperplane limited recursive polytope
updating
POLYREG to perform recursive updating of regular polyhedra
POLYSLIM to perform support limited recursive polytope updating
PROJECT projecting of an ellipsoid or a polytope onto a linear
subspace
PR2DL solving dual LP problems
RANGES calculating the smallest axis aligned box around
an ellipsoid or polytope
RELAX recovering a polyhedron from a polytope by removing one
of its faces
SEL calculating the minimal volume outer bounding ellipsoid of
a given polytope
SIMSTDES solving LP problems
SLICEGBT calculating the intersection of an ellipsoid or polytope
and a hyperplane
STEL calculating the optimal minimal volume invariant covering
ellipsoid to polytope
SUBTRACT internal difference of two polytopes or ellipsoids
TRANSF performing linear transformation on a polyhedron or
ellipsoid
VERTICES extracting the vertices of a polyhedron from its GBT
format
VIEWGBT viewing several ellipsoids or polytopes on the screen
(2D or 3D projections)
VOLUME calculating the volume of an ellipsoid or polytope
Format-converting routines:
CAN transforming general LP problems into standard form
CONVP_PH converting type 2 format to type 4 format of polyhedra
CONVPH_P converting type 4 format to type 2 format of polyhedra
DECAN transforming 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.
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.
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.
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.