1082:
665:
1077:{\displaystyle {\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;\leq \;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;\leq \;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\;\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;\leq \;&&&b_{m}\\\end{alignedat}}}
2290:
2343:, where the partial ordering is by set containment of faces. The definition of a face given above allows both the polytope itself and the empty set to be considered as faces, ensuring that every pair of faces has a join and a meet in the face lattice. The whole polytope is the unique maximum element of the lattice, and the empty set, considered to be a (−1)-dimensional face (a
31:
2096:
The two representations together provide an efficient way to decide whether a given vector is included in a given convex polytope: to show that it is in the polytope, it is sufficient to present it as a convex combination of the polytope vertices (the V-description is used); to show that it is not in
1530:
and the polytope can be studied as an object in this subspace. In this case, there exist linear equations which are satisfied by all points of the polytope. Adding one of these equations to any of the defining inequalities does not change the polytope. Therefore, in general there is no unique minimal
103:
convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others (including this article) allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts
1542:
By requiring that the intersection of half-spaces results in a bounded set, the definition becomes equivalent to the vertex-representation. An outline of the proof, that the bounded intersection of half-spaces results in a polytope in vertex-representation, follows:
2527:, and the intersection of any two simplices is either empty or a lower-dimensional simplex. This simplicial decomposition is the basis of many methods for computing the volume of a convex polytope, since the volume of a simplex is easily given by a formula.
122:, convex polytopes are often simply called "polytopes". GrĂĽnbaum points out that this is solely to avoid the endless repetition of the word "convex", and that the discussion should throughout be understood as applying only to the convex variety (p. 51).
2282:, and vice versa. Each point on a given facet will satisfy the linear equality of the corresponding row in the matrix. (It may or may not also satisfy equality in other rows). Similarly, each point on a ridge will satisfy equality in two of the rows of
2397:. Because these polytopes' face lattices are determined by their graphs, the problem of deciding whether two three-dimensional or simple convex polytopes are combinatorially isomorphic can be formulated equivalently as a special case of the
2560:
Different representations of a convex polytope have different utility, therefore the construction of one representation given another one is an important problem. The problem of the construction of a V-representation is known as the
250:
A convex polytope may be defined in a number of ways, depending on what is more suitable for the problem at hand. GrĂĽnbaum's definition is in terms of a convex set of points in space. Other important definitions are: as the
670:
2569:. While the vertex set of a bounded convex polytope uniquely defines it, in various applications it is important to know more about the combinatorial structure of the polytope, i.e., about its face lattice. Various
626:
2100:
A subtle point in the representation by vectors is that the number of vectors may be exponential in the dimension, so the proof that a vector is in the polytope might be exponentially long. Fortunately,
2580:, both facet and vertex enumeration problems amount to the ordering vertices (resp. edges) around the convex hull. It is a trivial task when the convex polygon is specified in a traditional way for
1534:
In general the intersection of arbitrary half-spaces need not be bounded. However if one wishes to have a definition equivalent to that as a convex hull, then bounding must be explicitly required.
515:). There exist infinitely many H-descriptions of a convex polytope. However, for a full-dimensional convex polytope, the minimal H-description is in fact unique and is given by the set of the
2199:
such that none of the interior points of the polytope lie on the boundary of the halfspace. Equivalently, a face is the set of points giving equality in some valid inequality of the polytope.
1681:
1836:
1627:
2628:
1966:
1581:
1528:
341:
176:
97:
1908:
1336:
1236:
1190:
2264:
1495:
1141:
1708:
1390:
1363:
1290:
1263:
2930:
2175:, every finite-dimensional vector space being not only an image of, but in fact isomorphic to, Euclidean space of some dimension (or analog over other fields).
2086:
2066:
2046:
2026:
2006:
1986:
1932:
1876:
1856:
1792:
1768:
1748:
1728:
1440:
1420:
1310:
1210:
1164:
1105:
649:
465:
445:
425:
405:
385:
365:
312:
147:
68:
2401:. However, it is also possible to translate these problems in the opposite direction, showing that polytope isomorphism testing is graph-isomorphism complete.
1587:
form the set of vertices. It remains to show that the set of extreme points (of the bounded intersection of a finite set of half-spaces) is also finite:
2102:
1446:
of the polytope, a hyperplane bounding a half-space that contains the polytope. If a supporting hyperplane also intersects the polytope, it is called a
1457:
minimal set of defining inequalities (up to multiplication by a positive number). Inequalities belonging to this unique minimal system are called
1442:
correspond with the coefficients of the linear inequality defining the respective half-space. Hence, each row in the matrix corresponds with a
3186:
2857:
2784:
2121:
For an unbounded polytope (sometimes called: polyhedron), the H-description is still valid, but the V-description should be extended.
475:
of a finite set of points, where the finite set must contain the set of extreme points of the polytope. Such a definition is called a
3228:
3148:
2892:
2832:
2776:
2325:
of the face. Geometrically speaking, this means that the face is the set of points on the polytope that lie in the intersection of
536:
2167:
of the (finitely many) vertices. However, polytopes are not in general isomorphic to simplices. This is in contrast to the case of
3045:
1710:. We consider the intersection of all the corresponding hyperplanes (which divide the space into the half-spaces) that contain
1583:
is clearly compact and convex. A compact and convex set with a finite number of extreme points must be a polytope, where those
3083:
656:
2675:
3218:
2562:
2544:
503:
A convex polytope may be defined as an intersection of a finite number of half-spaces. Such definition is called a
2398:
252:
2523:. It is possible to form a collection of subsets such that the union of the corresponding simplices is equal to
1632:
3426:
3088:
2997:
1797:
2377:) is the set of vertices and edges of the polytope only, ignoring higher-dimensional faces. For instance, a
2088:. Every extreme point lies in one of these sets, which means that the amount of extreme points is finite.
1593:
2671:
2651:
2394:
2667:
2570:
2438:
1399:
is defined in the same way, with strict inequalities used in the formulas instead of the non-strict ones.
2876:
487:). For a compact convex polytope, the minimal V-description is unique and it is given by the set of the
2587:
2196:
1937:
256:
222:
2717:
118:
In the influential textbooks of GrĂĽnbaum and
Ziegler on the subject, as well as in many other texts in
1557:
1504:
1450:(since it is a supporting hyperplane, it can only intersect the polytope at the polytope's boundary).
317:
152:
73:
3324:
3206:
2800:
2768:
2513:
2442:
2271:
1108:
2760:
2207:
226:
3312:
2385:
the face lattice of a three-dimensional polytope is determined by its graph. The same is true for
1461:. The set of points of a polytope which satisfy an essential inequality with equality is called a
3421:
3276:
3249:
3115:
3097:
3022:
2974:
2924:
2880:
2536:
2490:
2418:
2172:
2164:
1453:
The foregoing definition assumes that the polytope is full-dimensional. In this case, there is a
112:
2750:
1881:
1315:
1215:
1169:
3384:
3365:
3342:
3224:
3182:
3144:
2888:
2853:
2828:
2780:
2772:
2691:
2446:
2240:
2215:
2184:
1551:
1471:
1117:
527:
523:
492:
488:
119:
3405:
2836:
3332:
3291:
3258:
3202:
3174:
3107:
3054:
3006:
2964:
2956:
2755:
2707:
2478:
2378:
2223:
2144:
2122:
516:
273:
230:
3272:
3068:
3018:
2902:
1686:
1368:
1341:
1268:
1241:
3268:
3064:
3014:
2944:
2898:
2808:
2687:
2683:
2635:
2631:
2386:
2382:
2336:
2219:
2190:
1498:
234:
218:
203:
2097:
the polytope, it is sufficient to present a single defining inequality that it violates.
1107:
is the number of half-spaces defining the polytope. This can be concisely written as the
3328:
3214:
2992:
2712:
2679:
2577:
2540:
2474:
2333:
2294:
2071:
2051:
2031:
2011:
1991:
1971:
1917:
1861:
1841:
1777:
1753:
1733:
1713:
1425:
1405:
1295:
1195:
1149:
1090:
634:
450:
430:
410:
390:
370:
350:
297:
286:
211:
207:
132:
53:
3387:
3337:
202:
shape (the intersection of two non-parallel half-planes), a shape defined by a convex
3415:
3059:
3026:
2414:
2298:
2168:
1584:
279:
3280:
2289:
651:
is the dimension of the space containing the polytope under consideration. Hence, a
3401:
3368:
3288:
Proceedings of the
Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83)
3162:
2466:
2390:
3123:
3119:
2686:, one obstacle is that, when given a representation of the convex polytope as an
3178:
3136:
2764:
2647:
2425:
denote the dimension of the polytope. If the polytope is full-dimensional, then
2389:
of arbitrary dimension (Blind & Mani-Levitska 1987, proving a conjecture of
2355:
2140:
2130:
472:
260:
108:
100:
3244:
3210:
3111:
2969:
2852:. Graduate texts in mathematics. Cham, Switzerland: Springer. pp. 30–35.
2695:
2136:
282:
195:
188:
47:
3346:
3392:
3373:
3040:
2125:(1936) proved that any unbounded polytope can be represented as a sum of a
2105:
guarantees that every vector in the polytope can be represented by at most
3296:
3263:
2565:
and the problem of the construction of a H-representation is known as the
2450:
1911:
43:
17:
3286:
Ben-Or, Michael (1983), "Lower Bounds for
Algebraic Computation Trees",
3010:
2978:
2581:
2517:
2494:
2160:
187:
Many examples of bounded convex polytopes can be found in the article "
2449:
is trivial. The boundary of the convex polytope is homeomorphic to an
2381:
is the polytope graph of a three-dimensional polytope. By a result of
241:) defined by three or more half-spaces passing through a common point.
221:
between two parallel hyperplanes, a wedge defined by two non-parallel
3102:
2663:
3166:
2995:; Mani-Levitska, Peter (1987), "Puzzles and polytope isomorphisms",
2960:
2917:
Beitrage zur
Theorie der linearen Ungleichungen (Ph.D. dissertation)
2573:
deal both with the facet enumeration and face lattice construction.
107:
Convex polytopes play an important role both in various branches of
2347:) of every polytope, is the unique minimum element of the lattice.
2807:, Graduate Texts in Mathematics, vol. 152, Berlin, New York:
199:
30:
29:
3043:(1988), "A simple way to tell a simple polytope from its graph",
2008:
would be the inner point of (at least) a line, which contradicts
2195:
of a convex polytope is any intersection of the polytope with a
2147:
of its infinite edges (its "defining rays"). This is called the
2068:
closed half-spaces, there are only finitely many different sets
471:
This is equivalent to defining a bounded convex polytope as the
238:
2887:, Annals of Discrete Mathematics, vol. 29, North-Holland,
2630:. When the input list of vertices (or edges) is unordered, the
1468:
If the polytope is not full-dimensional, then the solutions of
194:
In the 2-dimensional case the full-dimensional examples are a
621:{\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}\leq b}
3223:(2nd ed.). MIT Press and McGraw-Hill. pp. 947–957.
2543:) can be dissected into some even number of instances of its
2135:. In other words, every vector in an unbounded polytope is a
1750:. For each half-space where the hyperplane does not contain
3167:"Exact Volume Computation for Polytopes: A Practical Study"
2947:(1932). "Congruent graphs and the connectivity of graphs".
2048:
chooses either the interior or the boundary of one of the
27:
Convex hull of a finite set of points in a
Euclidean space
1338:
column vector whose coordinates are the right-hand sides
2301:; each face in the lattice is labeled by its vertex set.
2666:
of a convex polytope has been studied in the field of
2590:
2409:
A convex polytope, like any compact convex subset of
2243:
2074:
2054:
2034:
2014:
1994:
1974:
1940:
1920:
1884:
1864:
1844:
1800:
1780:
1756:
1736:
1716:
1689:
1635:
1596:
1560:
1507:
1474:
1428:
1408:
1371:
1344:
1318:
1298:
1271:
1244:
1218:
1198:
1172:
1152:
1120:
1093:
668:
637:
539:
453:
433:
413:
393:
373:
353:
320:
300:
155:
135:
76:
56:
3084:"On the Complexity of Polytope Isomorphism Problems"
2539:
to an orthoscheme. Every regular convex polyhedron (
2457:. The boundary's Euler characteristic is 0 for even
2028:
being an extreme point. Since every construction of
217:
Special cases of an unbounded convex polytope are a
46:, having the additional property that it is also a
2622:
2258:
2159:Every (bounded) convex polytope is the image of a
2080:
2060:
2040:
2020:
2000:
1980:
1960:
1926:
1902:
1870:
1850:
1830:
1786:
1762:
1742:
1722:
1702:
1675:
1621:
1575:
1522:
1489:
1434:
1414:
1384:
1357:
1330:
1304:
1284:
1257:
1238:column vector whose coordinates are the variables
1230:
1204:
1184:
1158:
1135:
1099:
1076:
643:
620:
459:
439:
419:
399:
379:
359:
335:
306:
170:
141:
91:
62:
3247:(1981), "A lower bound to finding convex hulls",
1683:, the bounded intersection of closed half-spaces
495:if all of its vertices have integer coordinates.
2698:which is not polynomial in this representation.
2584:, i.e., by the ordered sequence of its vertices
2139:of its vertices (its "defining points"), plus a
491:of the polytope. A convex polytope is called an
2393:). Kalai (1988) gives a simple proof based on
655:may be regarded as the set of solutions to the
2678:technique, when having access to a membership
2270:corresponds with a bounding hyperplane and is
1774:of those half-spaces. This yields an open set
104:identify a convex polytope with its boundary.
2214: − 1)-dimensional faces, its
8:
3082:Kaibel, Volker; Schwartz, Alexander (2003).
2332:The faces of a convex polytope thus form an
263:of a set of points (vertex representation).
2489:A convex polytope can be decomposed into a
1531:set of inequalities defining the polytope.
99:. Most texts use the term "polytope" for a
2929:: CS1 maint: location missing publisher (
2551:Algorithmic problems for a convex polytope
1676:{\displaystyle P:=\bigcap _{i=1}^{k}H_{i}}
1055:
1051:
1021:
1011:
981:
977:
943:
934:
933:
932:
923:
922:
921:
912:
911:
910:
888:
884:
854:
844:
817:
813:
771:
767:
737:
727:
700:
696:
277:, GrĂĽnbaum defines a convex polytope as a
3336:
3295:
3262:
3217:(2001) . "33.3 Finding the convex hull".
3171:Polytopes — Combinatorics and Computation
3101:
3058:
2968:
2614:
2595:
2589:
2465:. The boundary may also be regarded as a
2313:)-dimensional face satisfies equality in
2242:
2230: − 2)-dimensional faces.
2073:
2053:
2033:
2013:
1993:
1973:
1939:
1919:
1883:
1863:
1843:
1831:{\displaystyle x\in (U\cap O)\subseteq P}
1799:
1779:
1755:
1735:
1715:
1694:
1688:
1667:
1657:
1646:
1634:
1604:
1603:
1595:
1567:
1563:
1562:
1559:
1514:
1510:
1509:
1506:
1473:
1427:
1407:
1376:
1370:
1349:
1343:
1317:
1297:
1276:
1270:
1249:
1243:
1217:
1197:
1171:
1151:
1119:
1092:
1064:
1042:
1029:
1002:
989:
968:
955:
897:
875:
862:
835:
825:
804:
794:
780:
758:
745:
718:
708:
687:
677:
669:
667:
636:
606:
596:
577:
567:
554:
544:
538:
452:
432:
412:
392:
372:
352:
327:
323:
322:
319:
299:
198:, a strip between two parallel lines, an
162:
158:
157:
154:
134:
83:
79:
78:
75:
55:
2694:, the volume of the polytope may have a
2508:, a subset of its vertices containing (
2329:of the polytope's bounding hyperplanes.
2288:
1538:Equivalence to the vertex representation
2820:
2818:
2730:
1622:{\displaystyle x\in {\textrm {ext}}(P)}
259:(half-space representation) and as the
2922:
2795:
2793:
2746:
2744:
2742:
2740:
2738:
2736:
2734:
2433:. The convex polytope therefore is an
2274:of the other rows, then each facet of
1770:, we consider the intersection of the
111:and in applied areas, most notably in
2222:are its 1-dimensional faces, and its
2117:Representation of unbounded polytopes
347:if, for each pair of distinct points
7:
2871:
2869:
2848:Hug, Daniel; Weil, Wolfgang (2020).
2278:corresponds with exactly one row of
407:, the closed segment with endpoints
2092:Using the different representations
267:Vertex representation (convex hull)
2623:{\displaystyle v_{1},\dots ,v_{m}}
2473: − 1)-dimensional
1961:{\displaystyle D=\left\{x\right\}}
25:
3338:10.1090/S0025-5718-1991-1079024-2
2497:, satisfying certain properties.
2237:defined by the matrix inequality
2218:are its 0-dimensional faces, its
1730:. This yields an affine subspace
2576:In the planar case, i.e., for a
1576:{\displaystyle \mathbb {R} ^{n}}
1523:{\displaystyle \mathbb {R} ^{n}}
1402:The coefficients of each row of
336:{\displaystyle \mathbb {R} ^{n}}
171:{\displaystyle \mathbb {R} ^{n}}
92:{\displaystyle \mathbb {R} ^{n}}
3046:Journal of Combinatorial Theory
2556:Construction of representations
2113:is the dimension of the space.
34:A 3-dimensional convex polytope
1819:
1807:
1616:
1610:
1:
3313:"Polytope volume computation"
2670:. The volume can be computed
657:system of linear inequalities
210:attached to its ends, and a
70:-dimensional Euclidean space
3060:10.1016/0097-3165(88)90064-7
2827:, by Melvyn W. Jeter (1986)
2455: − 1)-sphere
1392:of the scalar inequalities.
3179:10.1007/978-3-0348-8438-9_6
2850:Lectures on convex geometry
2759:, 2nd edition, prepared by
2676:convex volume approximation
2535:Every convex polyhedron is
2354:if their face lattices are
2109:+1 defining vectors, where
499:Intersection of half-spaces
3443:
3406:Polyhedral computation FAQ
3317:Mathematics of Computation
3220:Introduction to Algorithms
2915:Motzkin, Theodore (1936).
2674:, for instance, using the
2662:The task of computing the
2563:vertex enumeration problem
2545:characteristic orthoscheme
2352:combinatorially isomorphic
2182:
1934:must be 0-dimensional and
1903:{\displaystyle D:=U\cap O}
3112:10.1007/s00373-002-0503-y
2567:facet enumeration problem
2399:graph isomorphism problem
2350:Two polytopes are called
1331:{\displaystyle m\times 1}
1231:{\displaystyle n\times 1}
1185:{\displaystyle m\times n}
505:half-space representation
3089:Graphs and Combinatorics
2998:Aequationes Mathematicae
2825:Mathematical Programming
2634:of the problems becomes
2485:Simplicial decomposition
2395:unique sink orientations
2259:{\displaystyle Ax\leq b}
2233:Given a convex polytope
1490:{\displaystyle Ax\leq b}
1136:{\displaystyle Ax\leq b}
285:with a finite number of
2652:algebraic decision tree
1988:was not 0-dimensional,
1858:is an extreme point of
1629:be an extreme point of
149:-dimensional object in
42:is a special case of a
3311:Lawrence, Jim (1991).
3161:BĂĽeler, B.; Enge, A.;
2668:computational geometry
2654:model of computation.
2624:
2571:convex hull algorithms
2504:-dimensional polytope
2405:Topological properties
2302:
2293:The face lattice of a
2260:
2163:, as every point is a
2132:convex polyhedral cone
2103:Carathéodory's theorem
2082:
2062:
2042:
2022:
2002:
1982:
1962:
1928:
1904:
1872:
1852:
1832:
1788:
1764:
1744:
1724:
1704:
1677:
1662:
1623:
1577:
1524:
1491:
1436:
1416:
1386:
1359:
1332:
1306:
1286:
1259:
1232:
1206:
1186:
1160:
1137:
1101:
1078:
653:closed convex polytope
645:
622:
519:-defining halfspaces.
461:
441:
421:
401:
381:
361:
337:
308:
172:
143:
93:
64:
35:
3297:10.1145/800061.808735
3264:10.1145/322276.322289
3207:Leiserson, Charles E.
3141:Topology and Geometry
2805:Lectures on Polytopes
2625:
2371:graph of the polytope
2292:
2261:
2083:
2063:
2043:
2023:
2003:
1983:
1963:
1929:
1905:
1873:
1853:
1833:
1789:
1765:
1745:
1725:
1705:
1703:{\displaystyle H_{i}}
1678:
1642:
1624:
1578:
1525:
1492:
1444:supporting hyperplane
1437:
1417:
1387:
1385:{\displaystyle b_{m}}
1360:
1358:{\displaystyle b_{1}}
1333:
1307:
1287:
1285:{\displaystyle x_{n}}
1260:
1258:{\displaystyle x_{1}}
1233:
1207:
1187:
1161:
1138:
1102:
1079:
646:
623:
477:vertex representation
462:
442:
422:
402:
382:
362:
338:
309:
173:
144:
125:A polytope is called
94:
65:
33:
3245:Yao, Andrew Chi Chih
3173:. pp. 131–154.
2720:for convex polyhedra
2588:
2514:affinely independent
2443:Euler characteristic
2321:. These rows form a
2272:linearly independent
2241:
2149:finite basis theorem
2072:
2052:
2032:
2012:
1992:
1972:
1938:
1918:
1882:
1862:
1842:
1798:
1778:
1754:
1734:
1714:
1687:
1633:
1594:
1558:
1505:
1472:
1426:
1406:
1397:open convex polytope
1369:
1342:
1316:
1296:
1269:
1242:
1216:
1196:
1170:
1150:
1118:
1091:
666:
635:
537:
526:can be written as a
451:
447:is contained within
431:
411:
391:
371:
351:
318:
298:
153:
133:
74:
54:
3388:"Convex polyhedron"
3329:1991MaCom..57..259L
2692:linear inequalities
2531:Scissors-congruency
2441:with boundary, its
2309: −
2173:linear combinations
1448:bounding hyperplane
227:polyhedral cylinder
3385:Weisstein, Eric W.
3366:Weisstein, Eric W.
3290:, pp. 80–86,
3250:Journal of the ACM
3011:10.1007/BF01830678
2970:10338.dmlcz/101067
2801:Ziegler, GĂĽnter M.
2718:Steinitz's theorem
2658:Volume computation
2620:
2537:scissors-congruent
2516:points defines an
2491:simplicial complex
2477:— i.e. as a
2303:
2256:
2206:-dimensional, its
2165:convex combination
2078:
2058:
2038:
2018:
1998:
1978:
1958:
1924:
1914:, it follows that
1900:
1868:
1848:
1828:
1784:
1760:
1740:
1720:
1700:
1673:
1619:
1573:
1552:closed half-spaces
1520:
1487:
1432:
1412:
1382:
1355:
1328:
1302:
1282:
1255:
1228:
1202:
1182:
1156:
1133:
1097:
1074:
1072:
641:
618:
457:
437:
417:
397:
377:
357:
333:
304:
168:
139:
113:linear programming
89:
60:
36:
3211:Rivest, Ronald L.
3203:Cormen, Thomas H.
3188:978-3-7643-6351-2
2859:978-3-030-50180-8
2785:978-0-387-40409-7
2769:GĂĽnter M. Ziegler
2684:exact computation
2447:fundamental group
2317:specific rows of
2266:, if each row in
2202:If a polytope is
2185:abstract polytope
2145:Euclidean vectors
2081:{\displaystyle D}
2061:{\displaystyle k}
2041:{\displaystyle D}
2021:{\displaystyle x}
2001:{\displaystyle x}
1981:{\displaystyle D}
1927:{\displaystyle D}
1871:{\displaystyle P}
1851:{\displaystyle x}
1787:{\displaystyle O}
1763:{\displaystyle x}
1743:{\displaystyle U}
1723:{\displaystyle x}
1607:
1435:{\displaystyle b}
1415:{\displaystyle A}
1305:{\displaystyle b}
1205:{\displaystyle x}
1159:{\displaystyle A}
1100:{\displaystyle m}
644:{\displaystyle n}
528:linear inequality
524:closed half-space
493:integral polytope
460:{\displaystyle K}
440:{\displaystyle b}
420:{\displaystyle a}
400:{\displaystyle K}
380:{\displaystyle b}
360:{\displaystyle a}
307:{\displaystyle K}
142:{\displaystyle n}
120:discrete geometry
63:{\displaystyle n}
50:contained in the
16:(Redirected from
3434:
3398:
3397:
3379:
3378:
3369:"Convex polygon"
3351:
3350:
3340:
3323:(195): 259–271.
3308:
3302:
3300:
3299:
3283:
3266:
3241:
3235:
3234:
3199:
3193:
3192:
3158:
3152:
3134:
3128:
3127:
3122:. Archived from
3105:
3079:
3073:
3071:
3062:
3037:
3031:
3029:
3005:(2–3): 287–297,
2989:
2983:
2982:
2972:
2945:Whitney, Hassler
2941:
2935:
2934:
2928:
2920:
2912:
2906:
2905:
2873:
2864:
2863:
2845:
2839:
2822:
2813:
2811:
2797:
2788:
2756:Convex Polytopes
2748:
2708:Oriented matroid
2650:is known in the
2629:
2627:
2626:
2621:
2619:
2618:
2600:
2599:
2479:spherical tiling
2387:simple polytopes
2379:polyhedral graph
2305:In general, an (
2265:
2263:
2262:
2257:
2179:The face lattice
2127:bounded polytope
2123:Theodore Motzkin
2087:
2085:
2084:
2079:
2067:
2065:
2064:
2059:
2047:
2045:
2044:
2039:
2027:
2025:
2024:
2019:
2007:
2005:
2004:
1999:
1987:
1985:
1984:
1979:
1967:
1965:
1964:
1959:
1957:
1933:
1931:
1930:
1925:
1909:
1907:
1906:
1901:
1877:
1875:
1874:
1869:
1857:
1855:
1854:
1849:
1837:
1835:
1834:
1829:
1793:
1791:
1790:
1785:
1769:
1767:
1766:
1761:
1749:
1747:
1746:
1741:
1729:
1727:
1726:
1721:
1709:
1707:
1706:
1701:
1699:
1698:
1682:
1680:
1679:
1674:
1672:
1671:
1661:
1656:
1628:
1626:
1625:
1620:
1609:
1608:
1605:
1582:
1580:
1579:
1574:
1572:
1571:
1566:
1550:intersection of
1529:
1527:
1526:
1521:
1519:
1518:
1513:
1497:lie in a proper
1496:
1494:
1493:
1488:
1441:
1439:
1438:
1433:
1421:
1419:
1418:
1413:
1391:
1389:
1388:
1383:
1381:
1380:
1364:
1362:
1361:
1356:
1354:
1353:
1337:
1335:
1334:
1329:
1311:
1309:
1308:
1303:
1291:
1289:
1288:
1283:
1281:
1280:
1264:
1262:
1261:
1256:
1254:
1253:
1237:
1235:
1234:
1229:
1211:
1209:
1208:
1203:
1191:
1189:
1188:
1183:
1165:
1163:
1162:
1157:
1142:
1140:
1139:
1134:
1106:
1104:
1103:
1098:
1083:
1081:
1080:
1075:
1073:
1069:
1068:
1058:
1057:
1049:
1047:
1046:
1037:
1036:
1023:
1009:
1007:
1006:
997:
996:
983:
975:
973:
972:
963:
962:
939:
938:
937:
936:
927:
926:
925:
916:
915:
914:
902:
901:
891:
890:
882:
880:
879:
870:
869:
856:
842:
840:
839:
830:
829:
819:
811:
809:
808:
799:
798:
785:
784:
774:
773:
765:
763:
762:
753:
752:
739:
725:
723:
722:
713:
712:
702:
694:
692:
691:
682:
681:
650:
648:
647:
642:
627:
625:
624:
619:
611:
610:
601:
600:
582:
581:
572:
571:
559:
558:
549:
548:
509:H-representation
481:V-representation
466:
464:
463:
458:
446:
444:
443:
438:
426:
424:
423:
418:
406:
404:
403:
398:
386:
384:
383:
378:
366:
364:
363:
358:
342:
340:
339:
334:
332:
331:
326:
313:
311:
310:
305:
274:Convex Polytopes
177:
175:
174:
169:
167:
166:
161:
148:
146:
145:
140:
127:full-dimensional
98:
96:
95:
90:
88:
87:
82:
69:
67:
66:
61:
21:
3442:
3441:
3437:
3436:
3435:
3433:
3432:
3431:
3427:Convex geometry
3412:
3411:
3383:
3382:
3364:
3363:
3360:
3355:
3354:
3310:
3309:
3305:
3285:
3243:
3242:
3238:
3231:
3215:Stein, Clifford
3201:
3200:
3196:
3189:
3160:
3159:
3155:
3135:
3131:
3081:
3080:
3076:
3039:
3038:
3034:
2993:Blind, Roswitha
2991:
2990:
2986:
2961:10.2307/2371086
2943:
2942:
2938:
2921:
2914:
2913:
2909:
2895:
2885:Matching Theory
2875:
2874:
2867:
2860:
2847:
2846:
2842:
2823:
2816:
2809:Springer-Verlag
2799:
2798:
2791:
2751:Branko GrĂĽnbaum
2749:
2732:
2727:
2704:
2688:equation system
2660:
2642: log
2632:time complexity
2610:
2591:
2586:
2585:
2558:
2553:
2533:
2500:Given a convex
2487:
2475:spherical space
2407:
2367:polytopal graph
2239:
2238:
2187:
2181:
2157:
2119:
2094:
2070:
2069:
2050:
2049:
2030:
2029:
2010:
2009:
1990:
1989:
1970:
1969:
1947:
1936:
1935:
1916:
1915:
1912:relatively open
1880:
1879:
1860:
1859:
1840:
1839:
1796:
1795:
1776:
1775:
1752:
1751:
1732:
1731:
1712:
1711:
1690:
1685:
1684:
1663:
1631:
1630:
1592:
1591:
1561:
1556:
1555:
1540:
1508:
1503:
1502:
1499:affine subspace
1470:
1469:
1424:
1423:
1404:
1403:
1372:
1367:
1366:
1345:
1340:
1339:
1314:
1313:
1294:
1293:
1272:
1267:
1266:
1245:
1240:
1239:
1214:
1213:
1194:
1193:
1168:
1167:
1148:
1147:
1116:
1115:
1089:
1088:
1071:
1070:
1060:
1056:
1048:
1038:
1025:
1022:
1008:
998:
985:
982:
974:
964:
951:
948:
947:
935:
924:
913:
904:
903:
893:
889:
881:
871:
858:
855:
841:
831:
821:
818:
810:
800:
790:
787:
786:
776:
772:
764:
754:
741:
738:
724:
714:
704:
701:
693:
683:
673:
664:
663:
633:
632:
602:
592:
573:
563:
550:
540:
535:
534:
501:
449:
448:
429:
428:
409:
408:
389:
388:
369:
368:
349:
348:
321:
316:
315:
296:
295:
269:
248:
235:polyhedral cone
204:polygonal chain
184:
156:
151:
150:
131:
130:
77:
72:
71:
52:
51:
40:convex polytope
28:
23:
22:
15:
12:
11:
5:
3440:
3438:
3430:
3429:
3424:
3414:
3413:
3410:
3409:
3399:
3380:
3359:
3358:External links
3356:
3353:
3352:
3303:
3257:(4): 780–787,
3236:
3229:
3194:
3187:
3153:
3137:Glen E. Bredon
3129:
3126:on 2015-07-21.
3096:(2): 215–230.
3074:
3053:(2): 381–383,
3032:
2984:
2955:(1): 150–168.
2936:
2907:
2893:
2881:Plummer, M. D.
2877:Lovász, László
2865:
2858:
2840:
2814:
2789:
2729:
2728:
2726:
2723:
2722:
2721:
2715:
2713:Nef polyhedron
2710:
2703:
2700:
2659:
2656:
2646:). A matching
2617:
2613:
2609:
2606:
2603:
2598:
2594:
2578:convex polygon
2557:
2554:
2552:
2549:
2541:Platonic solid
2532:
2529:
2493:, or union of
2486:
2483:
2461:and 2 for odd
2445:is 1, and its
2406:
2403:
2363:polytope graph
2295:square pyramid
2255:
2252:
2249:
2246:
2183:Main article:
2180:
2177:
2156:
2153:
2118:
2115:
2093:
2090:
2077:
2057:
2037:
2017:
1997:
1977:
1956:
1953:
1950:
1946:
1943:
1923:
1899:
1896:
1893:
1890:
1887:
1867:
1847:
1827:
1824:
1821:
1818:
1815:
1812:
1809:
1806:
1803:
1783:
1759:
1739:
1719:
1697:
1693:
1670:
1666:
1660:
1655:
1652:
1649:
1645:
1641:
1638:
1618:
1615:
1612:
1602:
1599:
1585:extreme points
1570:
1565:
1539:
1536:
1517:
1512:
1486:
1483:
1480:
1477:
1431:
1411:
1379:
1375:
1352:
1348:
1327:
1324:
1321:
1301:
1279:
1275:
1252:
1248:
1227:
1224:
1221:
1201:
1181:
1178:
1175:
1155:
1144:
1143:
1132:
1129:
1126:
1123:
1096:
1085:
1084:
1067:
1063:
1059:
1054:
1050:
1045:
1041:
1035:
1032:
1028:
1024:
1020:
1017:
1014:
1010:
1005:
1001:
995:
992:
988:
984:
980:
976:
971:
967:
961:
958:
954:
950:
949:
946:
942:
940:
931:
928:
920:
917:
909:
906:
905:
900:
896:
892:
887:
883:
878:
874:
868:
865:
861:
857:
853:
850:
847:
843:
838:
834:
828:
824:
820:
816:
812:
807:
803:
797:
793:
789:
788:
783:
779:
775:
770:
766:
761:
757:
751:
748:
744:
740:
736:
733:
730:
726:
721:
717:
711:
707:
703:
699:
695:
690:
686:
680:
676:
672:
671:
640:
629:
628:
617:
614:
609:
605:
599:
595:
591:
588:
585:
580:
576:
570:
566:
562:
557:
553:
547:
543:
500:
497:
469:
468:
456:
436:
416:
396:
376:
356:
330:
325:
303:
287:extreme points
268:
265:
247:
244:
243:
242:
215:
212:convex polygon
192:
183:
180:
165:
160:
138:
86:
81:
59:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3439:
3428:
3425:
3423:
3420:
3419:
3417:
3407:
3403:
3400:
3395:
3394:
3389:
3386:
3381:
3376:
3375:
3370:
3367:
3362:
3361:
3357:
3348:
3344:
3339:
3334:
3330:
3326:
3322:
3318:
3314:
3307:
3304:
3298:
3293:
3289:
3282:
3278:
3274:
3270:
3265:
3260:
3256:
3252:
3251:
3246:
3240:
3237:
3232:
3230:0-262-03293-7
3226:
3222:
3221:
3216:
3212:
3208:
3204:
3198:
3195:
3190:
3184:
3180:
3176:
3172:
3168:
3164:
3157:
3154:
3150:
3149:0-387-97926-3
3146:
3142:
3138:
3133:
3130:
3125:
3121:
3117:
3113:
3109:
3104:
3099:
3095:
3091:
3090:
3085:
3078:
3075:
3070:
3066:
3061:
3056:
3052:
3048:
3047:
3042:
3036:
3033:
3028:
3024:
3020:
3016:
3012:
3008:
3004:
3000:
2999:
2994:
2988:
2985:
2980:
2976:
2971:
2966:
2962:
2958:
2954:
2950:
2949:Amer. J. Math
2946:
2940:
2937:
2932:
2926:
2918:
2911:
2908:
2904:
2900:
2896:
2894:0-444-87916-1
2890:
2886:
2882:
2878:
2872:
2870:
2866:
2861:
2855:
2851:
2844:
2841:
2838:
2834:
2833:0-8247-7478-7
2830:
2826:
2821:
2819:
2815:
2810:
2806:
2802:
2796:
2794:
2790:
2786:
2782:
2778:
2777:0-387-40409-0
2774:
2770:
2766:
2762:
2761:Volker Kaibel
2758:
2757:
2752:
2747:
2745:
2743:
2741:
2739:
2737:
2735:
2731:
2724:
2719:
2716:
2714:
2711:
2709:
2706:
2705:
2701:
2699:
2697:
2693:
2689:
2685:
2681:
2677:
2673:
2672:approximately
2669:
2665:
2657:
2655:
2653:
2649:
2645:
2641:
2637:
2633:
2615:
2611:
2607:
2604:
2601:
2596:
2592:
2583:
2579:
2574:
2572:
2568:
2564:
2555:
2550:
2548:
2546:
2542:
2538:
2530:
2528:
2526:
2522:
2520:
2515:
2511:
2507:
2503:
2498:
2496:
2492:
2484:
2482:
2480:
2476:
2472:
2468:
2464:
2460:
2456:
2454:
2448:
2444:
2440:
2437:-dimensional
2436:
2432:
2428:
2424:
2420:
2416:
2412:
2404:
2402:
2400:
2396:
2392:
2388:
2384:
2380:
2376:
2372:
2368:
2364:
2359:
2357:
2353:
2348:
2346:
2345:null polytope
2342:
2338:
2335:
2330:
2328:
2324:
2320:
2316:
2312:
2308:
2300:
2299:Hasse diagram
2297:, drawn as a
2296:
2291:
2287:
2285:
2281:
2277:
2273:
2269:
2253:
2250:
2247:
2244:
2236:
2231:
2229:
2225:
2221:
2217:
2213:
2209:
2205:
2200:
2198:
2194:
2193:
2186:
2178:
2176:
2174:
2170:
2169:vector spaces
2166:
2162:
2154:
2152:
2150:
2146:
2142:
2138:
2134:
2133:
2128:
2124:
2116:
2114:
2112:
2108:
2104:
2098:
2091:
2089:
2075:
2055:
2035:
2015:
1995:
1975:
1954:
1951:
1948:
1944:
1941:
1921:
1913:
1897:
1894:
1891:
1888:
1885:
1865:
1845:
1825:
1822:
1816:
1813:
1810:
1804:
1801:
1781:
1773:
1757:
1737:
1717:
1695:
1691:
1668:
1664:
1658:
1653:
1650:
1647:
1643:
1639:
1636:
1613:
1600:
1597:
1588:
1586:
1568:
1553:
1549:
1544:
1537:
1535:
1532:
1515:
1500:
1484:
1481:
1478:
1475:
1466:
1464:
1460:
1456:
1451:
1449:
1445:
1429:
1409:
1400:
1398:
1393:
1377:
1373:
1350:
1346:
1325:
1322:
1319:
1299:
1277:
1273:
1250:
1246:
1225:
1222:
1219:
1199:
1179:
1176:
1173:
1153:
1130:
1127:
1124:
1121:
1114:
1113:
1112:
1110:
1094:
1065:
1061:
1052:
1043:
1039:
1033:
1030:
1026:
1018:
1015:
1012:
1003:
999:
993:
990:
986:
978:
969:
965:
959:
956:
952:
944:
941:
929:
918:
907:
898:
894:
885:
876:
872:
866:
863:
859:
851:
848:
845:
836:
832:
826:
822:
814:
805:
801:
795:
791:
781:
777:
768:
759:
755:
749:
746:
742:
734:
731:
728:
719:
715:
709:
705:
697:
688:
684:
678:
674:
662:
661:
660:
658:
654:
638:
615:
612:
607:
603:
597:
593:
589:
586:
583:
578:
574:
568:
564:
560:
555:
551:
545:
541:
533:
532:
531:
529:
525:
520:
518:
514:
513:H-description
510:
506:
498:
496:
494:
490:
486:
485:V-description
482:
478:
474:
454:
434:
414:
394:
374:
354:
346:
328:
301:
293:
292:
291:
289:
288:
284:
281:
276:
275:
266:
264:
262:
258:
254:
245:
240:
236:
232:
228:
224:
220:
216:
213:
209:
205:
201:
197:
193:
190:
186:
185:
181:
179:
163:
136:
128:
123:
121:
116:
114:
110:
105:
102:
84:
57:
49:
45:
41:
32:
19:
3402:Komei Fukuda
3391:
3372:
3320:
3316:
3306:
3287:
3254:
3248:
3239:
3219:
3197:
3170:
3156:
3140:
3132:
3124:the original
3103:math/0106093
3093:
3087:
3077:
3050:
3044:
3035:
3002:
2996:
2987:
2952:
2948:
2939:
2919:. Jerusalem.
2916:
2910:
2884:
2849:
2843:
2824:
2804:
2754:
2661:
2643:
2639:
2575:
2566:
2559:
2534:
2524:
2518:
2509:
2505:
2501:
2499:
2488:
2470:
2467:tessellation
2462:
2458:
2452:
2434:
2430:
2426:
2422:
2417:to a closed
2415:homeomorphic
2410:
2408:
2391:Micha Perles
2374:
2370:
2366:
2362:
2360:
2351:
2349:
2344:
2341:face lattice
2340:
2331:
2326:
2322:
2318:
2314:
2310:
2306:
2304:
2283:
2279:
2275:
2267:
2234:
2232:
2227:
2211:
2203:
2201:
2191:
2188:
2158:
2148:
2131:
2126:
2120:
2110:
2106:
2099:
2095:
1771:
1589:
1547:
1545:
1541:
1533:
1467:
1462:
1458:
1454:
1452:
1447:
1443:
1401:
1396:
1394:
1145:
1111:inequality:
1086:
652:
630:
521:
512:
508:
504:
502:
484:
480:
476:
470:
344:
278:
272:
271:In his book
270:
253:intersection
249:
129:if it is an
126:
124:
117:
106:
39:
37:
2765:Victor Klee
2648:lower bound
2339:called its
2141:conical sum
1794:. Clearly,
473:convex hull
261:convex hull
257:half-spaces
246:Definitions
223:half-spaces
109:mathematics
3416:Categories
3163:Fukuda, K.
3049:, Ser. A,
3041:Kalai, Gil
2725:References
2696:bit-length
2375:1-skeleton
2356:isomorphic
2155:Properties
2137:convex sum
283:convex set
237:(infinite
229:(infinite
196:half-plane
189:polyhedron
48:convex set
3422:Polytopes
3393:MathWorld
3374:MathWorld
3347:0025-5718
3027:120222616
2925:cite book
2682:. As for
2605:…
2495:simplices
2251:≤
2226:are its (
2210:are its (
2197:halfspace
1895:∩
1823:⊆
1814:∩
1805:∈
1644:⋂
1601:∈
1482:≤
1459:essential
1323:×
1223:×
1177:×
1128:≤
1053:≤
1016:⋯
945:⋮
930:⋮
919:⋮
908:⋮
886:≤
849:⋯
769:≤
732:⋯
613:≤
587:⋯
233:), and a
206:with two
18:Nonconvex
3281:13846330
3165:(2000).
3151:, p. 56.
3143:, 1993,
2883:(1986),
2803:(1995),
2787:, 466pp.
2771:, 2003,
2702:See also
2582:polygons
2521:-simplex
2439:manifold
2334:Eulerian
2216:vertices
1838:. Since
1772:interior
1192:matrix,
489:vertices
182:Examples
44:polytope
3325:Bibcode
3273:0677089
3069:0964396
3019:0921106
2979:2371086
2903:0859549
2383:Whitney
2337:lattice
2161:simplex
2143:of the
1548:bounded
280:compact
101:bounded
3345:
3279:
3271:
3227:
3185:
3147:
3120:179936
3118:
3067:
3025:
3017:
2977:
2901:
2891:
2856:
2831:
2783:
2775:
2767:, and
2680:oracle
2664:volume
2421:. Let
2224:ridges
2208:facets
2129:and a
1455:unique
1312:is an
1292:, and
1212:is an
1166:is an
1146:where
1109:matrix
1087:where
631:where
345:convex
294:A set
3277:S2CID
3116:S2CID
3098:arXiv
3023:S2CID
2975:JSTOR
2837:p. 68
2413:, is
2323:basis
2220:edges
1968:. If
1463:facet
517:facet
231:prism
200:angle
3343:ISSN
3225:ISBN
3183:ISBN
3145:ISBN
2931:link
2889:ISBN
2854:ISBN
2829:ISBN
2781:ISBN
2773:ISBN
2512:+1)
2469:of (
2419:ball
2361:The
2192:face
2171:and
1878:and
1590:Let
1546:The
1422:and
427:and
239:cone
225:, a
219:slab
208:rays
3333:doi
3292:doi
3259:doi
3175:doi
3108:doi
3055:doi
3007:doi
2965:hdl
2957:doi
2690:of
1910:is
1606:ext
1554:of
1501:of
1395:An
1365:to
1265:to
511:or
483:or
387:in
343:is
314:of
255:of
3418::
3404:,
3390:.
3371:.
3341:.
3331:.
3321:57
3319:.
3315:.
3284:;
3275:,
3269:MR
3267:,
3255:28
3253:,
3213:;
3209:;
3205:;
3181:.
3169:.
3139:,
3114:.
3106:.
3094:19
3092:.
3086:.
3065:MR
3063:,
3051:49
3021:,
3015:MR
3013:,
3003:34
3001:,
2973:.
2963:.
2953:54
2951:.
2927:}}
2923:{{
2899:MR
2897:,
2879:;
2868:^
2835:,
2817:^
2792:^
2779:,
2763:,
2753:,
2733:^
2547:.
2481:.
2429:=
2373:,
2369:,
2358:.
2286:.
2189:A
2151:.
1889::=
1640::=
1465:.
827:22
796:21
710:12
679:11
659::
530::
522:A
367:,
290::
191:".
178:.
115:.
38:A
3408:.
3396:.
3377:.
3349:.
3335::
3327::
3301:.
3294::
3261::
3233:.
3191:.
3177::
3110::
3100::
3072:.
3057::
3030:.
3009::
2981:.
2967::
2959::
2933:)
2862:.
2812:.
2644:m
2640:m
2638:(
2636:O
2616:m
2612:v
2608:,
2602:,
2597:1
2593:v
2525:P
2519:r
2510:r
2506:P
2502:r
2471:m
2463:m
2459:m
2453:m
2451:(
2435:m
2431:n
2427:m
2423:m
2411:R
2365:(
2327:j
2319:A
2315:j
2311:j
2307:n
2284:A
2280:A
2276:P
2268:A
2254:b
2248:x
2245:A
2235:P
2228:d
2212:d
2204:d
2111:d
2107:d
2076:D
2056:k
2036:D
2016:x
1996:x
1976:D
1955:}
1952:x
1949:{
1945:=
1942:D
1922:D
1898:O
1892:U
1886:D
1866:P
1846:x
1826:P
1820:)
1817:O
1811:U
1808:(
1802:x
1782:O
1758:x
1738:U
1718:x
1696:i
1692:H
1669:i
1665:H
1659:k
1654:1
1651:=
1648:i
1637:P
1617:)
1614:P
1611:(
1598:x
1569:n
1564:R
1516:n
1511:R
1485:b
1479:x
1476:A
1430:b
1410:A
1378:m
1374:b
1351:1
1347:b
1326:1
1320:m
1300:b
1278:n
1274:x
1251:1
1247:x
1226:1
1220:n
1200:x
1180:n
1174:m
1154:A
1131:b
1125:x
1122:A
1095:m
1066:m
1062:b
1044:n
1040:x
1034:n
1031:m
1027:a
1019:+
1013:+
1004:2
1000:x
994:2
991:m
987:a
979:+
970:1
966:x
960:1
957:m
953:a
899:2
895:b
877:n
873:x
867:n
864:2
860:a
852:+
846:+
837:2
833:x
823:a
815:+
806:1
802:x
792:a
782:1
778:b
760:n
756:x
750:n
747:1
743:a
735:+
729:+
720:2
716:x
706:a
698:+
689:1
685:x
675:a
639:n
616:b
608:n
604:x
598:n
594:a
590:+
584:+
579:2
575:x
569:2
565:a
561:+
556:1
552:x
546:1
542:a
507:(
479:(
467:.
455:K
435:b
415:a
395:K
375:b
355:a
329:n
324:R
302:K
214:.
164:n
159:R
137:n
85:n
80:R
58:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
