N-dimensional polyhedron

<h2 id="examples">Examples</h2>
Many traditional polyhedral forms are n-dimensional polyhedra. Other examples include:

<ul><li>A <a href="/facts/Half-space_(geometry)/AGknBgnw">half-space</a> is a polyhedron defined by a single linear inequality, a1Tx ≤ b1.</li>
<li>A <a href="/facts/Hyperplane/2s2ycYYd">hyperplane</a> is a polyhedron defined by two inequalities, a1Tx ≤ b1 and a1Tx ≥ b1 (which is equivalent to -a1Tx ≤ -b1).</li>
<li>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: { ( x, y ) : x ≥ 0, y ≥ 0 }. Its sides are the two positive axes, and it is otherwise unbounded.</li>
<li>An octant in Euclidean 3-space, { ( x, y, z ) : x ≥ 0, y ≥ 0, z ≥ 0 }.</li>
<li>A prism of infinite extent. For instance a doubly infinite square prism in 3-space, consisting of a square in the xy-plane swept along the z-axis: { ( x, y, z ) : 0 ≤ x ≤ 1, 0 ≤ y ≤ 1 }.</li>
<li>Each <a href="/facts/Cell_(geometry)/T2E6BTU4">cell</a> in a <a href="/facts/Voronoi_diagram/AhQY5LD8">Voronoi tessellation</a> is a polyhedron. In the Voronoi tessellation of a set S, the cell A corresponding to a point c ∈ S is bounded (hence a traditional polyhedron) when c lies in the <a href="/facts/Interior_(topology)/5sxGnQfY">interior</a> of the <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> of S, and otherwise (when c lies on the <a href="/facts/Boundary_(topology)/WgdH18kp">boundary</a> of the convex hull of S) A is unbounded.</li></ul>
<h2 id="faces-and-vertices">Faces and vertices</h2>
A subset F of a polyhedron P is called a face of P if there is a halfspace H (defined by some inequality a1Tx ≤ b1) such that H contains P and F is the intersection of H and P.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>: 9  

<ul><li>If a face contains a single point {v}, then v is called a vertex of P.</li>
<li>If a face F is nonempty and n-1 dimensional, then F is called a facet of P.</li></ul>
Suppose P is a polyhedron defined by Ax ≤ b, where A has full column rank. Then, v is a vertex of P if and only if v is a <a href="/facts/Basic_feasible_solution/e18dV7Xh">basic feasible solution</a> of the linear system Ax ≤ b.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>: 10 

<h2 id="standard-representation">Standard representation</h2>
The representation of a polyhedron by a set of linear inequalities is not unique. It is common to define a standard representation for each polyhedron P:<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>: 9  

<ul><li>If P is full-dimensional, then its standard representation is a set of inequalities such that each inequality aiTx ≤ bi defines exactly one facet of P, and moreover, the inequalities are normalized such that 
 
 
 
 ‖
 
 a
 
 i
 
 
 
 ‖
 
 ∞
 
 
 =
 1
 
 
 {\displaystyle \|a_{i}\|_{\infty }=1}
 
 for all i.</li>
<li>If P is not full-dimensional, then it is contained in its <a href="/facts/Affine_hull/4fhyHKoa">affine hull</a>, which is defined by a set of linear equations Cx=d. It is possible to choose C such that C = (I, C'), where I is an <a href="/facts/Identity_matrix/Glbcf6ol">identity matrix</a>. The standard representation of P contains this set Cx=d and a set of inequalities such that each inequality aiTx ≤ bi defines exactly one facet of P, the inequalities are normalized such that 
 
 
 
 ‖
 
 a
 
 i
 
 
 
 ‖
 
 ∞
 
 
 =
 1
 
 
 {\displaystyle \|a_{i}\|_{\infty }=1}
 
 for all i, and each ai is orthogonal to each row of C. This representation is unique up to the choice of columns of the identity matrix.</li></ul>
<h2 id="representation-by-cones-and-convex-hulls">Representation by cones and convex hulls</h2>
If P is a polytope (a bounded polyhedron), then it can be represented by its set of vertices V, as P is simply the <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> of V: P = conv(V).
If P is a general (possibly unbounded) polyhedron, then it can be represented as: P = conv(V) + cone(E), where V is (as before) the set of vertices of P, and E is another finite set, and cone denotes the <a href="/facts/Conic_hull/41KGtqdd">conic hull</a>. The set cone(E) is also called the <a href="/facts/Recession_cone/tuKBGACh">recession cone</a> of P.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>: 10 
<a href="/facts/Carath%25C3%25A9odory%2527s_theorem_(convex_hull)/QGyEIEPv">Carathéodory's theorem</a> states that, if P is a d-dimensional polytope, then every point in P can be written as a convex combination of at most d+1 affinely-independent vertices of P. The theorem can be generalized: if P is any d-dimensional polyhedron, then every point in P can be written as a convex combination of points v1,...,vs, v1+e1,...,v1+et with s+t ≤ d+1, such that v1,...,vs are elements of minimal nonempty faces of P and e1,...,et are elements of the minimal nonzero faces of the recession cone of P.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>: 10 

<h2 id="complexity-of-representation">Complexity of representation</h2>
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 P:<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>: 163  

<ul><li>P has facet complexity at most f, if P 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 f. Note that f ≥ n+1, since there are n+1 coefficients in each inequality.</li>
<li>P has vertex complexity at most v, if P can be represented as conv(V)+cone(E), where V and E are finite sets, such that each point in V or E has encoding length at most v. Note that v ≥ n, since there are n coefficients in each vector.</li></ul>
These two kinds of complexity are closely related:<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>: Lem.6.2.4 

<ul><li>If P has facet complexity at most f, then P has vertex complexity at most 4 n2 f.</li>
<li>If P has vertex complexity at most v, then P has facet complexity at most 3 n2 v.</li></ul>
A polyhedron P is called well-described if we know n (the number of dimensions) and f (an upper bound on the facet complexity). This is equivalent to requiring that we know n and v (an upper bound on the vertex complexity).
In some cases, we know an upper bound on the facet complexity of a polyhedron P, 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 P is at most 35 n2 f.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>: Lem.6.2.3 
The complexity of representation of P implies upper and lower bounds on the volume of P:<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>: 165 

<ul><li>If P has vertex complexity at most v, then trivially, all vertices of P are contained in the ball of radius 2v around the origin. This means that, if P is a polytope, then P itself is circumscribed in that ball.</li>
<li>If P is a full-dimensional polyhedron with facet complexity at most f, then P contains a ball with radius 
 
 
 
 
 2
 
 −
 7
 
 n
 
 3
 
 
 f
 
 
 
 
 {\displaystyle 2^{-7n^{3}f}}
 
. Moreover, this ball is contained in the ball of radius 
 
 
 
 
 2
 
 5
 
 n
 
 2
 
 
 f
 
 
 
 
 {\displaystyle 2^{5n^{2}f}}
 
 around the origin.</li></ul>
Small representation complexity is useful for "rounding" approximate solutions to exact solutions. Specifically:<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>: 166 

<ul><li>If P is a polyhedron with facet complexity at most f, and y is a rational vector whose entries have common denominator at most q, and the distance from y to P is at most 2-2f/q, then y is in fact in P.</li>
<li>If P is a polyhedron with vertex complexity at most v, and P satisfies the inequality aTx ≤ b + 2-v-1, then P also satisfies the inequality aTx ≤ b.</li>
<li>If P is a polyhedron with facet complexity at most f, and v is a rational vector with distance from P of at most 2-6nf, and q and w are integer vectors satisfying 
 
 
 
 ‖
 q
 v
 −
 w
 ‖
 <
 
 2
 
 −
 3
 f
 
 
 ,
 0
 <
 q
 <
 
 2
 
 4
 n
 f
 
 
 
 
 {\displaystyle \|qv-w\|<2^{-3f},0<q<2^{4nf}}
 
, then the point w/q is contained in P. The number q and the vector w can be found in polytime using <a href="/facts/Simultaneous_diophantine_approximation/WGVMuWF4">simultaneous diophantine approximation</a>.</li>
<li>If P is a polyhedron with vertex complexity at most v, and P satisfies the inequality aTx ≤ b + 2-6nv, and q,c,d are integer vectors satisfying 
 
 
 
 ‖
 q
 a
 −
 c
 ‖
 +
 
 |
 
 q
 b
 −
 d
 
 |
 
 <
 
 2
 
 −
 3
 v
 
 
 ,
 0
 <
 q
 <
 
 2
 
 4
 n
 v
 
 
 
 
 {\displaystyle \|qa-c\|+|qb-d|<2^{-3v},0<q<2^{4nv}}
 
, then P satisfies the inequality cTx ≤ d. The numbers q,d and the vector c can be found in polytime using <a href="/facts/Simultaneous_diophantine_approximation/WGVMuWF4">simultaneous diophantine approximation</a>.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Algorithmic_problems_on_convex_sets/wVtJDwNQ">Algorithmic problems on convex sets</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Grünbaum, Branko (2003), Convex Polytopes, Graduate Texts in Mathematics, vol. 221 (2nd ed.), New York: Springer-Verlag, p. 26, doi:10.1007/978-1-4613-0019-9, ISBN 978-0-387-00424-2, MR 1976856. <a href="978-0-387-00424-2" target="_blank">978-0-387-00424-2</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Bruns, Winfried; Gubeladze, Joseph (2009), "Definition 1.1", Polytopes, Rings, and K-theory, Springer Monographs in Mathematics, Dordrecht: Springer, p. 5, CiteSeerX 10.1.1.693.2630, doi:10.1007/b105283, ISBN 978-0-387-76355-2, MR 2508056. <a href="978-0-387-76355-2" target="_blank">978-0-387-76355-2</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419 <a href="978-3-642-78242-8" target="_blank">978-3-642-78242-8</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
</ol>

N-dimensional polyhedron open-in-new

N-dimensional polyhedron