956:
can be represented by a system of linear inequalities with rational coefficients, such that the encoding length of each inequality (i.e., the binary encoding length of all rational numbers appearing as coefficients in the inequality) is at most
930:
When solving algorithmic problems on polyhedra, it is important to know whether a certain polyhedron can be represented by an encoding with a small number of bits. There are several measures to the representation complexity of a polyhedron
1577:
1417:
707:
581:
1181:
1221:
192:
A quadrant in the plane. For instance, the region of the cartesian plane consisting of all points above the horizontal axis and to the right of the vertical axis:
1083:, but we do not know the specific inequalities that attain this upper bound. However, it can be proved that the encoding length in any standard representation of
797:
1472:
1600:
1440:
1789:
1714:
1655:
1337:
94:
are scalars. This definition of polyhedra is particularly important as it provides a geometric perspective for problems in
50:. Unlike a 3-dimensional polyhedron, it may be bounded or unbounded. In this terminology, a bounded polyhedron is called a
1613:
246:
A prism of infinite extent. For instance a doubly infinite square prism in 3-space, consisting of a square in the
1227:
Small representation complexity is useful for "rounding" approximate solutions to exact solutions. Specifically:
666:
540:
500:
The representation of a polyhedron by a set of linear inequalities is not unique. It is common to define a
768:
is a general (possibly unbounded) polyhedron, then it can be represented as: P = conv(V) + cone(E), where
1823:
516:
is full-dimensional, then its standard representation is a set of inequalities such that each inequality
59:
Analytically, a convex polyhedron is expressed as the solution set for a system of linear inequalities,
1642:, Graduate Texts in Mathematics, vol. 221 (2nd ed.), New York: Springer-Verlag, p. 26,
1697:
1143:
1186:
481:
1692:
1771:
111:
47:
1763:
1680:
46:, that has flat sides. It may alternatively be defined as the intersection of finitely many
1799:
1724:
1665:
8:
1767:
328:
312:
1759:
737:
is a polytope (a bounded polyhedron), then it can be represented by its set of vertices
1818:
1068:(an upper bound on the facet complexity). This is equivalent to requiring that we know
106:
Many traditional polyhedral forms are n-dimensional polyhedra. Other examples include:
95:
1633:
1785:
1776:, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin,
1710:
1651:
1777:
1702:
1643:
1637:
724:. This representation is unique up to the choice of columns of the identity matrix.
1795:
1720:
1661:
627:
286:
282:
39:
786:
1781:
1647:
1079:
In some cases, we know an upper bound on the facet complexity of a polyhedron
1812:
1121:
are contained in the ball of radius 2 around the origin. This means that, if
995:
are finite sets, such that each point in V or E has encoding length at most
35:
746:
595:
316:
32:
781:
212:}. Its sides are the two positive axes, and it is otherwise unbounded.
135:
24:
1691:, Springer Monographs in Mathematics, Dordrecht: Springer, p. 5,
1706:
1243:
is a rational vector whose entries have common denominator at most
918:
are elements of the minimal nonzero faces of the recession cone of
52:
1132:
is a full-dimensional polyhedron with facet complexity at most
1572:{\displaystyle \|qa-c\|+|qb-d|<2^{-3v},0<q<2^{4nv}}
1125:
is a polytope, then P itself is circumscribed in that ball.
728:
537:, and moreover, the inequalities are normalized such that
1183:. Moreover, this ball is contained in the ball of radius
23:
is a geometric object that generalizes the 3-dimensional
1758:
965:+1, since there are n+1 coefficients in each inequality.
31:-dimensional space. It is defined as a set of points in
289:
is a polyhedron. In the
Voronoi tessellation of a set
114:
is a polyhedron defined by a single linear inequality,
1475:
1412:{\displaystyle \|qv-w\|<2^{-3f},0<q<2^{4nf}}
1340:
1189:
1146:
669:
594:
is not full-dimensional, then it is contained in its
543:
642:
and a set of inequalities such that each inequality
1773:
Geometric algorithms and combinatorial optimization
1011:These two kinds of complexity are closely related:
1672:
1626:
1571:
1411:
1215:
1175:
812:can be written as a convex combination of at most
701:
575:
832:can be written as a convex combination of points
307:is bounded (hence a traditional polyhedron) when
1810:
1101:implies upper and lower bounds on the volume of
598:, which is defined by a set of linear equations
1450:is a polyhedron with vertex complexity at most
1274:is a polyhedron with vertex complexity at most
925:
1678:
1632:
1314:is a polyhedron with facet complexity at most
1235:is a polyhedron with facet complexity at most
828:-dimensional polyhedron, then every point in
138:is a polyhedron defined by two inequalities,
1491:
1476:
1356:
1341:
780:is another finite set, and cone denotes the
684:
670:
663:, the inequalities are normalized such that
558:
544:
1679:Bruns, Winfried; Gubeladze, Joseph (2009),
1076:(an upper bound on the vertex complexity).
808:-dimensional polytope, then every point in
900:are elements of minimal nonempty faces of
495:
1696:
1469:and q,c,d are integer vectors satisfying
1023:, then P has vertex complexity at most 4
1322:is a rational vector with distance from
1041:, then P has facet complexity at most 3
729:Representation by cones and convex hulls
1811:
1754:
1601:simultaneous diophantine approximation
1441:simultaneous diophantine approximation
772:is (as before) the set of vertices of
1752:
1750:
1748:
1746:
1744:
1742:
1740:
1738:
1736:
1734:
820:. The theorem can be generalized: if
784:. The set cone(E) is also called the
702:{\displaystyle \|a_{i}\|_{\infty }=1}
576:{\displaystyle \|a_{i}\|_{\infty }=1}
343:
1097:The complexity of representation of
816:+1 affinely-independent vertices of
1614:Algorithmic problems on convex sets
409:If a face contains a single point {
13:
1731:
1117:, then trivially, all vertices of
688:
562:
14:
1835:
630:. The standard representation of
215:An octant in Euclidean 3-space,
1599:can be found in polytime using
1439:can be found in polytime using
1334:are integer vectors satisfying
1064:(the number of dimensions) and
1515:
1498:
1297:also satisfies the inequality
1113:has vertex complexity at most
1037:has vertex complexity at most
1:
1619:
1019:has facet complexity at most
720:is orthogonal to each row of
659:defines exactly one facet of
533:defines exactly one facet of
1176:{\displaystyle 2^{-7n^{3}f}}
1140:contains a ball with radius
1007:coefficients in each vector.
926:Complexity of representation
468:has full column rank. Then,
368:(defined by some inequality
7:
1607:
1216:{\displaystyle 2^{5n^{2}f}}
979:can be represented as conv(
606:. It is possible to choose
456:is a polyhedron defined by
101:
10:
1840:
1583:satisfies the inequality c
970:vertex complexity at most
1782:10.1007/978-3-642-78240-4
1648:10.1007/978-1-4613-0019-9
1458:satisfies the inequality
1282:satisfies the inequality
297:corresponding to a point
42:) space of any dimension
1247:, and the distance from
364:if there is a halfspace
172:(which is equivalent to
502:standard representation
496:Standard representation
482:basic feasible solution
397:is the intersection of
250:-plane swept along the
21:-dimensional polyhedron
1685:Polytopes, Rings, and
1573:
1413:
1217:
1177:
798:Carathéodory's theorem
703:
577:
331:of the convex hull of
323:, and otherwise (when
1574:
1414:
1218:
1178:
704:
578:
484:of the linear system
436:-1 dimensional, then
1768:Schrijver, Alexander
1473:
1338:
1187:
1144:
667:
541:
504:for each polyhedron
287:Voronoi tessellation
1824:Linear programming
1569:
1409:
1326:of at most 2, and
1223:around the origin.
1213:
1173:
1003:, since there are
699:
634:contains this set
573:
344:Faces and vertices
96:linear programming
1791:978-3-642-78242-8
1760:Grötschel, Martin
1716:978-0-387-76355-2
1657:978-0-387-00424-2
1419:, then the point
1831:
1803:
1802:
1756:
1729:
1727:
1700:
1681:"Definition 1.1"
1676:
1670:
1668:
1639:Convex Polytopes
1634:Grünbaum, Branko
1630:
1578:
1576:
1575:
1570:
1568:
1567:
1537:
1536:
1518:
1501:
1427:is contained in
1418:
1416:
1415:
1410:
1408:
1407:
1377:
1376:
1222:
1220:
1219:
1214:
1212:
1211:
1207:
1206:
1182:
1180:
1179:
1174:
1172:
1171:
1167:
1166:
944:facet complexity
800:states that, if
708:
706:
705:
700:
692:
691:
682:
681:
582:
580:
579:
574:
566:
565:
556:
555:
432:is nonempty and
352:of a polyhedron
306:
277:
242:
211:
1839:
1838:
1834:
1833:
1832:
1830:
1829:
1828:
1809:
1808:
1807:
1806:
1792:
1757:
1732:
1717:
1707:10.1007/b105283
1698:10.1.1.693.2630
1677:
1673:
1658:
1631:
1627:
1622:
1610:
1595:and the vector
1557:
1553:
1526:
1522:
1514:
1497:
1474:
1471:
1470:
1435:and the vector
1397:
1393:
1366:
1362:
1339:
1336:
1335:
1202:
1198:
1194:
1190:
1188:
1185:
1184:
1162:
1158:
1151:
1147:
1145:
1142:
1141:
928:
916:
910:
898:
892:
872:
866:
859:
852:
844:
838:
731:
718:
687:
683:
677:
673:
668:
665:
664:
657:
647:
628:identity matrix
561:
557:
551:
547:
542:
539:
538:
531:
521:
498:
476:if and only if
472:is a vertex of
383:
373:
346:
298:
255:
216:
193:
187:
177:
170:
160:
153:
143:
129:
119:
104:
92:
83:are vectors in
81:
74:
64:
12:
11:
5:
1837:
1827:
1826:
1821:
1805:
1804:
1790:
1764:Lovász, László
1730:
1715:
1671:
1656:
1624:
1623:
1621:
1618:
1617:
1616:
1609:
1606:
1605:
1604:
1591:. The numbers
1566:
1563:
1560:
1556:
1552:
1549:
1546:
1543:
1540:
1535:
1532:
1529:
1525:
1521:
1517:
1513:
1510:
1507:
1504:
1500:
1496:
1493:
1490:
1487:
1484:
1481:
1478:
1444:
1406:
1403:
1400:
1396:
1392:
1389:
1386:
1383:
1380:
1375:
1372:
1369:
1365:
1361:
1358:
1355:
1352:
1349:
1346:
1343:
1308:
1268:
1263:is in fact in
1225:
1224:
1210:
1205:
1201:
1197:
1193:
1170:
1165:
1161:
1157:
1154:
1150:
1126:
1087:is at most 35
1058:well-described
1050:
1049:
1031:
1009:
1008:
966:
927:
924:
914:
908:
896:
890:
886:+1, such that
870:
864:
857:
850:
842:
836:
787:recession cone
745:is simply the
730:
727:
726:
725:
716:
698:
695:
690:
686:
680:
676:
672:
655:
645:
588:
572:
569:
564:
560:
554:
550:
546:
529:
519:
497:
494:
450:
449:
426:
381:
371:
345:
342:
341:
340:
279:
244:
213:
190:
185:
175:
168:
158:
151:
141:
132:
127:
117:
103:
100:
90:
79:
72:
62:
9:
6:
4:
3:
2:
1836:
1825:
1822:
1820:
1817:
1816:
1814:
1801:
1797:
1793:
1787:
1783:
1779:
1775:
1774:
1769:
1765:
1761:
1755:
1753:
1751:
1749:
1747:
1745:
1743:
1741:
1739:
1737:
1735:
1726:
1722:
1718:
1712:
1708:
1704:
1699:
1694:
1690:
1686:
1682:
1675:
1667:
1663:
1659:
1653:
1649:
1645:
1641:
1640:
1635:
1629:
1625:
1615:
1612:
1611:
1602:
1598:
1594:
1590:
1586:
1582:
1564:
1561:
1558:
1554:
1550:
1547:
1544:
1541:
1538:
1533:
1530:
1527:
1523:
1519:
1511:
1508:
1505:
1502:
1494:
1488:
1485:
1482:
1479:
1468:
1464:
1461:
1457:
1453:
1449:
1445:
1442:
1438:
1434:
1431:. The number
1430:
1426:
1422:
1404:
1401:
1398:
1394:
1390:
1387:
1384:
1381:
1378:
1373:
1370:
1367:
1363:
1359:
1353:
1350:
1347:
1344:
1333:
1329:
1325:
1321:
1317:
1313:
1309:
1307:
1303:
1300:
1296:
1292:
1288:
1285:
1281:
1277:
1273:
1269:
1266:
1262:
1258:
1255:is at most 2/
1254:
1250:
1246:
1242:
1238:
1234:
1230:
1229:
1228:
1208:
1203:
1199:
1195:
1191:
1168:
1163:
1159:
1155:
1152:
1148:
1139:
1135:
1131:
1127:
1124:
1120:
1116:
1112:
1108:
1107:
1106:
1104:
1100:
1095:
1093:
1090:
1086:
1082:
1077:
1075:
1071:
1067:
1063:
1059:
1055:
1052:A polyhedron
1047:
1044:
1040:
1036:
1032:
1029:
1026:
1022:
1018:
1014:
1013:
1012:
1006:
1002:
998:
994:
990:
986:
982:
978:
974:
973:
967:
964:
960:
955:
951:
950:
945:
941:
938:
937:
936:
934:
923:
921:
917:
907:
903:
899:
889:
885:
881:
877:
873:
863:
856:
849:
845:
835:
831:
827:
823:
819:
815:
811:
807:
803:
799:
795:
793:
789:
788:
783:
779:
775:
771:
767:
762:
760:
756:
752:
748:
744:
740:
736:
723:
719:
712:
696:
693:
678:
674:
662:
658:
651:
648:
641:
637:
633:
629:
625:
621:
617:
613:
609:
605:
601:
597:
593:
589:
586:
570:
567:
552:
548:
536:
532:
525:
522:
515:
511:
510:
509:
507:
503:
493:
491:
487:
483:
479:
475:
471:
467:
463:
459:
455:
447:
443:
439:
435:
431:
427:
424:
420:
416:
412:
408:
407:
406:
404:
400:
396:
392:
388:
384:
377:
374:
367:
363:
359:
355:
351:
339:is unbounded.
338:
334:
330:
326:
322:
318:
314:
310:
305:
301:
296:
292:
288:
284:
280:
275:
271:
268:) : 0 ≤
267:
263:
259:
253:
249:
245:
240:
236:
232:
228:
224:
220:
214:
209:
205:
201:
197:
191:
188:
181:
178:
171:
164:
161:
154:
147:
144:
137:
133:
130:
123:
120:
113:
109:
108:
107:
99:
97:
93:
86:
82:
75:
68:
65:
57:
55:
54:
49:
45:
41:
37:
34:
30:
26:
22:
20:
1772:
1688:
1684:
1674:
1638:
1628:
1596:
1592:
1588:
1584:
1580:
1466:
1462:
1459:
1455:
1451:
1447:
1436:
1432:
1428:
1424:
1420:
1331:
1327:
1323:
1319:
1315:
1311:
1305:
1301:
1298:
1294:
1290:
1286:
1283:
1279:
1275:
1271:
1264:
1260:
1256:
1252:
1248:
1244:
1240:
1236:
1232:
1226:
1137:
1133:
1129:
1122:
1118:
1114:
1110:
1102:
1098:
1096:
1091:
1088:
1084:
1080:
1078:
1073:
1069:
1065:
1061:
1057:
1053:
1051:
1045:
1042:
1038:
1034:
1027:
1024:
1020:
1016:
1010:
1004:
1000:
999:. Note that
996:
992:
988:
984:
980:
976:
971:
969:
962:
961:. Note that
958:
953:
948:
946:
943:
939:
932:
929:
919:
912:
905:
901:
894:
887:
883:
879:
875:
868:
861:
854:
847:
840:
833:
829:
825:
821:
817:
813:
809:
805:
801:
796:
791:
785:
777:
773:
769:
765:
763:
758:
754:
750:
742:
738:
734:
732:
721:
714:
710:
660:
653:
649:
643:
639:
635:
631:
623:
619:
615:
611:
607:
603:
599:
591:
584:
534:
527:
523:
517:
513:
505:
501:
499:
489:
485:
477:
473:
469:
465:
461:
457:
453:
451:
445:
441:
440:is called a
437:
433:
429:
422:
418:
417:is called a
414:
410:
402:
398:
394:
390:
386:
385:) such that
379:
375:
369:
365:
361:
357:
356:is called a
353:
349:
347:
336:
332:
327:lies on the
324:
320:
311:lies in the
308:
303:
299:
294:
290:
273:
269:
265:
261:
257:
251:
247:
238:
234:
230:
226:
222:
218:
207:
203:
199:
195:
183:
179:
173:
166:
162:
156:
149:
145:
139:
125:
121:
115:
105:
88:
84:
77:
70:
66:
60:
58:
51:
43:
28:
18:
17:
15:
1060:if we know
747:convex hull
713:, and each
596:affine hull
317:convex hull
293:, the cell
48:half-spaces
1813:Categories
1620:References
1056:is called
782:conic hull
622:'), where
610:such that
428:If a face
272:≤ 1, 0 ≤
136:hyperplane
112:half-space
25:polyhedron
1819:Polyhedra
1693:CiteSeerX
1528:−
1509:−
1492:‖
1486:−
1477:‖
1368:−
1357:‖
1351:−
1342:‖
1153:−
987:), where
689:∞
685:‖
671:‖
563:∞
559:‖
545:‖
389:contains
348:A subset
229:) :
202:) :
40:Euclidean
1770:(1993),
1636:(2003),
1608:See also
947:at most
709:for all
583:for all
464:, where
452:Suppose
413:}, then
329:boundary
313:interior
254:-axis:
102:Examples
76:, where
53:polytope
1800:1261419
1725:2508056
1689:-theory
1666:1976856
1579:, then
1259:, then
1136:, then
983:)+cone(
824:is any
757:= conv(
315:of the
1798:
1788:
1723:
1713:
1695:
1664:
1654:
1467:b + 2,
1454:, and
1318:, and
1291:b + 2,
1278:, and
1239:, and
968:P has
776:, and
626:is an
419:vertex
36:affine
27:to an
1293:then
1001:v ≥ n
975:, if
963:f ≥ n
952:, if
911:,...,
893:,...,
874:with
860:,...,
839:,...,
804:is a
741:, as
480:is a
442:facet
285:in a
281:Each
237:≥ 0,
233:≥ 0,
206:≥ 0,
1786:ISBN
1711:ISBN
1652:ISBN
1551:<
1545:<
1520:<
1391:<
1385:<
1360:<
1330:and
1072:and
991:and
942:has
904:and
401:and
393:and
358:face
283:cell
276:≤ 1
256:{ (
241:≥ 0
217:{ (
210:≥ 0
194:{ (
182:≤ -
155:and
87:and
38:(or
33:real
1778:doi
1703:doi
1644:doi
1593:q,d
1446:If
1310:If
1270:If
1251:to
1231:If
1128:If
1109:If
1033:If
1015:If
935::
790:of
764:If
761:).
749:of
733:If
614:= (
590:If
512:If
508::
444:of
421:of
405:.
360:of
319:of
98:.
16:An
1815::
1796:MR
1794:,
1784:,
1766:;
1762:;
1733:^
1721:MR
1719:,
1709:,
1701:,
1683:,
1662:MR
1660:,
1650:,
1587:≤
1465:≤
1306:b.
1304:≤
1289:≤
1105::
1094:.
922:.
882:≤
846:,
794:.
753::
652:≤
638:x=
618:,
602:x=
526:≤
492:.
488:≤
486:Ax
460:≤
458:Ax
378:≤
335:)
302:∈
278:}.
264:,
260:,
248:xy
243:}.
225:,
221:,
198:,
189:).
174:-a
165:≥
148:≤
134:A
124:≤
110:A
69:≤
56:.
1780::
1728:.
1705::
1687:K
1669:.
1646::
1603:.
1597:c
1589:d
1585:x
1581:P
1565:v
1562:n
1559:4
1555:2
1548:q
1542:0
1539:,
1534:v
1531:3
1524:2
1516:|
1512:d
1506:b
1503:q
1499:|
1495:+
1489:c
1483:a
1480:q
1463:x
1460:a
1456:P
1452:v
1448:P
1443:.
1437:w
1433:q
1429:P
1425:q
1423:/
1421:w
1405:f
1402:n
1399:4
1395:2
1388:q
1382:0
1379:,
1374:f
1371:3
1364:2
1354:w
1348:v
1345:q
1332:w
1328:q
1324:P
1320:v
1316:f
1312:P
1302:x
1299:a
1295:P
1287:x
1284:a
1280:P
1276:v
1272:P
1267:.
1265:P
1261:y
1257:q
1253:P
1249:y
1245:q
1241:y
1237:f
1233:P
1209:f
1204:2
1200:n
1196:5
1192:2
1169:f
1164:3
1160:n
1156:7
1149:2
1138:P
1134:f
1130:P
1123:P
1119:P
1115:v
1111:P
1103:P
1099:P
1092:f
1089:n
1085:P
1081:P
1074:v
1070:n
1066:f
1062:n
1054:P
1048:.
1046:v
1043:n
1039:v
1035:P
1030:.
1028:f
1025:n
1021:f
1017:P
1005:n
997:v
993:E
989:V
985:E
981:V
977:P
972:v
959:f
954:P
949:f
940:P
933:P
920:P
915:t
913:e
909:1
906:e
902:P
897:s
895:v
891:1
888:v
884:d
880:t
878:+
876:s
871:t
869:e
867:+
865:1
862:v
858:1
855:e
853:+
851:1
848:v
843:s
841:v
837:1
834:v
830:P
826:d
822:P
818:P
814:d
810:P
806:d
802:P
792:P
778:E
774:P
770:V
766:P
759:V
755:P
751:V
743:P
739:V
735:P
722:C
717:i
715:a
711:i
697:1
694:=
679:i
675:a
661:P
656:i
654:b
650:x
646:i
644:a
640:d
636:C
632:P
624:I
620:C
616:I
612:C
608:C
604:d
600:C
592:P
587:.
585:i
571:1
568:=
553:i
549:a
535:P
530:i
528:b
524:x
520:i
518:a
514:P
506:P
490:b
478:v
474:P
470:v
466:A
462:b
454:P
448:.
446:P
438:F
434:n
430:F
425:.
423:P
415:v
411:v
403:P
399:H
395:F
391:P
387:H
382:1
380:b
376:x
372:1
370:a
366:H
362:P
354:P
350:F
337:A
333:S
325:c
321:S
309:c
304:S
300:c
295:A
291:S
274:y
270:x
266:z
262:y
258:x
252:z
239:z
235:y
231:x
227:z
223:y
219:x
208:y
204:x
200:y
196:x
186:1
184:b
180:x
176:1
169:1
167:b
163:x
159:1
157:a
152:1
150:b
146:x
142:1
140:a
131:.
128:1
126:b
122:x
118:1
116:a
91:i
89:b
85:R
80:i
78:a
73:i
71:b
67:x
63:i
61:a
44:n
29:n
19:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.