## Glossary

2-neighbourly

each pair of vertices defines an edge.

References: 146

3-polytope

The convex hull of a finite set of points in R3.

References: 155, 162, 86, 167, 148, 191, 187

4-polytope

The convex hull of a finite set of points in R4

References: 102, 185

algorithms

References: 52, 41, 11

application

References: 100, 94, 87, 88, 93, 105

beneath

A point p is beneath a facet F of a polytope P if p is in the closed halfspace induced by F containing P. See also beyond

beyond

A point p is beyond a facet F of a polytope P if p is in the open halfspace induced by F not containing P. See also beneath

book

References: 147, 142, 71, 41

centered

A polytope is centered if the origin is contained in the interior of \conv V\v for all v in V

centrally symmetric

A polytope P is called centrally symmetric if x in P implies -x in P.

References: 169

combinatorial structure

References: 153, 143, 145, 152, 196, 147, 140, 144, 141, 10, 139, 11, 146

computation

References: 37

computational geometry

References: 156, 41

containment

References: 158, 154

convex hull

References: 26, 50

convexity

References: 142

cyclic

References: 83, 149, 159

data structures

References: 41

degeneracy

References: 124, 56, 150, 21, 136, 123, 137

diagonal

References: 176, 186, 146

diagonals

References: 194

diameter

Diameter is used in two different senses. In the metric sense, it means the length of the longest line segment between points in a set (see e.g. [26]). In the combinatorial sense, it is used to mean the length of the longest path in the skeleton of a polytope, or of a graph in general. See also ridge-diameter.

References: 26, 166, 165, 174, 137, 78, 173

dissection

A dissection of a d-polytope P is a set of d-polytopes { Q1, Q2, ..., Qn } such that P = \union Qi and the interiors of the Qis are pairwise disjoint.

divide-and-conquer

References: 51

doctoral thesis

References: 51

domination

References: 51

double-description

References: 35, 24, 63, 43, 42, 15, 57, 69

dwarfed

A polytope P is called dwarfed if (P) = (Q) \union h+ where f0(P) << f0(Q)

References: 3

enumeration

References: 86, 102

equidecomposable

A polytope is called equidecomposable if every triangulation has the same f-vector

References: 115

estimation

References: 6, 5

extreme-point computation

References: 8, 25, 53

f-vector

References: 153, 122, 143, 152, 130, 139

face-enumeration

References: 25, 17, 36, 34, 68

faces>>size

sum fk >> d(f0+fd-1)

facet-degenerate

(some) facets contain more than d vertices, i.e. not simplicial.

facet-enumeration

References: 22, 49, 100, 18, 8, 59, 61, 20, 60, 53, 63, 55, 2, 29, 10, 12, 13, 68, 62, 51, 11, 69, 5, 3

facets>>vertices

fd-1 >> f0.

family description

References: 98

fixed-dimension

References: 22, 18, 119, 2

Fourier-Motzkin elimination

References: 60, 43, 42, 151, 31

g-vector

References: 168, 170, 190

general-position

References: 18

References: 20, 55

halfspace

A halfspace is the set of points satisfying some linear inequality ax < b (i.e. an open halfspace) or ax < = b (i.e. a closed halfspace)

hyperplane

A hyperplane is a set of points satisfying some linear inequality ax = b.

illumination

References: 176, 186

implementation

References: 58, 59, 60, 35, 63, 64, 13, 68, 57, 69

incidence graph

References: 50, 51

incremental

Incremental algorithms for e.g. facet-enumeration proceed by adding the input points one by one, updating the list of facet-defining inequalities for the current intermediate polytope at each step. See also double-description and Fourier-Motzkin elimination

References: 22, 49, 61, 60, 35, 24, 63, 29, 10, 12, 13, 15, 62, 23, 27, 31

intersection

References: 51

k-sets

References: 26

linear inequality

References: 30

linear programming

References: 150, 50, 71

linear-algebra

References: 142

lower bound

References: 11

Lower Bound Theorem

References: 169, 171, 168, 170, 140, 172

lower bounds

References: 70, 116, 10, 12, 5, 3

lower-bounds

References: 27

metric

References: 90, 144, 142

Minkowski-Weyl Theorem

References: 30

neighbourly

each k < floor(d/2) vertices forms a face.

References: 149, 159

non-convex

References: 9

NP-Complete

References: 150, 158, 34

oriented matroid

References: 185

oriented-matroid

References: 118

output-sensitive

References: 18, 25, 50, 51

p-vector

References: 155, 111, 162, 168, 167, 170, 148, 187, 157

parallel

References: 14, 2

parallelapiped

References: 9

perturbation

References: 122, 124, 113, 21, 130, 72, 136, 123, 114

pivoting

References: 56, 58, 70, 77, 20, 14, 21, 55, 71, 6, 72, 28, 13, 62, 30, 27, 7, 31

plane-sweep

References: 51

polyhedra

References: 50

polytope

References: 37

polytope pairs

References: 171

pseudomanifold

References: 172

pulling

References: 122

pushing

References: 130

random

References: 8, 53, 6

random sampling

References: 26

realization space

References: 185

redundancy-removal

References: 181

reference

References: 196, 188, 144, 156, 141

ridge-diameter

The diameter (in the graph theoretic sense) of the dual polytope.

References: 95, 96

rigidity

References: 168, 170, 195

simple

Exactly d facets intersect at each vertex.

simplicial

Exactly d vertices on each facet.

References: 143, 86, 102

skeleton

The skeleton of a convex polytope is the graph formed by its vertices and edges. The famous theorem of Steinitz [161, 191] says that the skeletons of 3-polyhedra are exactly the 3-connected planar graphs.

stacked polytope

An n-vertex stacked d-polytope is either a d-simplex, or the convex hull of an (n-1)-vertex stacked polytope with an additional point that is beyond exactly one facet. These polytopes have the minimum number of facets for an n-vertex simplicial polytope. See also truncation.

References: 143, 140

symmetry

References: 144

triangle-free

P has no triangular 2-face.

References: 145

triangulation

A dissection of a polytope into simplices such that any pair intersect in a (possibly empty) face.

References: 131, 126, 86, 117, 119, 118, 120, 116, 115, 121

truncation

Intersection with a halfspace that cuts off exactly one vertex.

truncation polytope

An m-facet truncation d-polytope is either a simplex or the truncation of an (m-1)-facet truncation polytope. These polytopes have the minimum number of vertices possible for an m-facet simple polytope. They are dual to the stacked polytopes.

References: 140

Upper Bound Theorem

References: 182

vertex

A 0-dimensional face of a polytope. Equivalently an extreme point.

vertex-degenerate

(some) vertices are contained in more than d facets, i.e. not simple. See also facet-degenerate.

vertex-enumeration

References: 16, 56, 58, 52, 1, 14, 60, 21, 35, 181, 24, 63, 34, 64, 71, 29, 6, 10, 12, 28, 68, 15, 23, 51, 27, 7, 57, 11, 69, 5, 3

vertices>>facets

volume

References: 37

Voronoi diagram

References: 59, 92

weakly neighbourly

References: 115

zero-one

A polytope is called zero-one if every vertex coordinate has one exactly two values (e.g. 0 or 1).

References: 16, 175

zonotope

A zonotope is the minkowski sum of a set of vectors.