A (convex) polytope is the convex hull of some finiteset of points. Each polytope of dimensionsd has as faces finitely many polytopes of dimensions 0 (vertices), 1 (edge), 2 (2-faces), · · ·,d-1 (facets). Two-dimensional polytopes are usually calledpolygons, three-dimensional ones polyhedra. Two polytopes are said to be isomorphic, or of the same combinatorial type, provided there exists a one-to-one correspondence between their faces, such that two faces of the first polytope meet if and only if the corresponding faces of the second meet. The prism and the truncated pyramid ofFigure 9 are isomorphic, the correspondence being indicated by the letters at the vertices. To classify the convex polygons by their combinatorial types, it is sufficient to determine the number of vertices υ; for each υ ≥ 3, all polygons with υ vertices (υ-gons) are of the same combinatorial type, while a υ-gon and a υ′-gon are not isomorphic if υ ≠ υ′.Euler was the first to investigate in 1752 theanalogous question concerning polyhedra. He found that υ −e +f = 2 for every convexpolyhedron, where υ,e, andf are the numbers of vertices, edges, and faces of the polyhedron. Though this formula became one of the starting points oftopology, Euler was not successful in his attempts to find a classification scheme for convex polytopes or to determine the number of different types for each υ. Despite efforts of many famous mathematicians since Euler (Steiner, Kirkman, Cayley, Hermes, Brückner, to mention only a few from the 19th century), the problem is still open for polyhedra with more than 19vertices. The numbers of different types with four, five, six, seven, or eight vertices are 1, 2, 7, 34, and 257, respectively. It was established by American mathematician P.J. Federico in 1969 that there are 2,606 different combinatorial types of convex polyhedra with nine vertices. The number of different types for 18 vertices is more than 107 trillion.

The theory of convex polytopes has been successful in developments in other directions. The regular polytopes have been under investigation since 1880 in dimensions higher than three, together with extensions of Euler’s relation to the higher dimensions. (The Swiss geometer Ludwig Schläfli made many of these discoveries some 30 years earlier, but his work was published only posthumously in 1901.) The interest in regular polyhedra and other special polyhedra goes back to ancient Greece, as indicated by the namesPlatonic solids and Archimedean solids.

Since 1950 there has been considerable interest, in part created by practical problems related to computer techniques such aslinear programming, in questions of the following type: for polytopes of a given dimensiond and having a given number υ of vertices, how large and how small can the number of facets be? Such problems have provided greatimpetus to the development of the theory. The U.S. mathematician Victor L. Klee solved the maximum problem in 1963 in most cases (that is, for all but a finite number of υ’s for eachd), but the remaining cases were disposed of only in 1970 by P. McMullen, in theUnited States, who used a completely new method.

Incidence problems

In 1893 the British mathematician J.J.Sylvester posed the question: If a finite setS of points in a plane has the property that eachline determined by two points ofS meets at least one other point ofS, must all points ofS be on one line? Sylvester never found a satisfactory solution to the problem, and the first (affirmative) solutions were published a half century later. Since then, Sylvester’s problem has inspired many investigations and led to many other questions, both in the plane and in higher dimensions.

Helly’s theorem

In 1912 Austrian mathematician Eduard Helly proved the followingtheorem, which has since found applications in many areas ofgeometry andanalysis and has led to numerous generalizations, extensions andanalogues known as Helly-type theorems. IfK₁,K₂, · · ·,K_n are convex sets ind-dimensionalEuclidean spaceE^d, in whichn ≥d + 1, and if for every choice ofd + 1 of the setsK_i there exists a point that belongs to all the chosen sets, then there exists a point that belongs to all the setsK₁,K₂, · · ·,K_n. The theorem stated in twodimensions is easier to visualize and yet is not shorn of its strength: If every three of a set ofn convex figures in the plane have a common point (not necessarily the same point for all trios), then alln figures have a point in common. If, for example, convex setsA,B, andC have the pointp in common, and convex setsA,B, andD have the pointq in common, and setsA,C, andD have the pointr in common, and setsB,C, andD have the points in common, then some pointx is a member ofA,B,C, andD.

Although the connection is often far from obvious, manyconsequences may be derived from Helly’s theorem. Among them are the following, stated ford = 2 with some higher dimensional analogues indicated in square brackets:

A. Two finite subsetsX andY of the plane [d-space] may be strictly separated by a suitable straight line [hyperplane] if and only if, for every setZ consisting of at most 4 [d + 2] points taken fromX ∪Y, the points ofX ∩Z may be strictly separated from those ofY ∩Z. (A line [hyperplane]L strictly separatesX andY ifX is contained in one of the open half planes [half spaces] determined byL and ifY is contained in the other.)

B. Each compact convex setK in the plane [d-space] contains a pointP with the following property: each chord ofK that containsP is divided byP into a number of segments so theratio of their lengths is at most 2d.

C. IfG is an open subset of the plane [d-space] withfinite area [d-dimensional content], then there exists a pointP, such that each open half plane [half space] that containsP contains also at least 1/3 [1/(d + 1)] of the area [d-content] ofG.

D. IfI₁, · · ·,I_n are segments parallel to they-axis in a plane with acoordinate system (x,y), and if for every choice of three of the segments there exists a straight line intersecting each of the three segments, then there exists a straight line that intersects all the segmentsI₁, · · ·,I_n.

Theorem D has generalizations in whichkth degreepolynomial curvesy =a_kx^k + · · · +a₁x +a₀ take the place of the straight lines andk + 2 replaces 3 in the assumptions. These are important in the theory of best approximation of functions by polynomials.