# Tag Info

## Hot answers tagged polytopes

11

A polyhedron is a special case of a polytope, or, equivalently, a polytope is a generalization of a polyhedron. A polytope has a certain dimension $n$, and when $n=3$ we say that the polytope is a polyhedron. (Similarly when $n=2$ we say that the polytope is a polygon.) This is analogous to how we can define a general $n$-dimensional sphere, and how we call ...

9

In short, what happens is the following. The $n$-dimensional analogue of a Platonic solid is called a regular polytope. In any dimension you are guaranteed three "boring" regular polytopes: the $n$-dimensional version of the tetrahedron (the $n$-simplex), the $n$-dimensional hypercube, and its dual, the $n$-dimensional version of the octahedron. In three ...

7

A self-tessellating figure can be dissected into some number of figures each similar to the original figure. I will generally assume that the smaller figures are all equal in size. I find it easier sometimes to consider the dissection of a larger figure into smaller ones rather than try to build a large figure from many copies of a small one. The regular ...

7

The generating function approach is that this is the coefficient of $x^{25}$ in: $$\frac{1}{(1-x)^3(1-x^3)}$$ Which can be rewritten as: $$\frac{(1+x+x^2)^3}{(1-x^3)^4}=(x^6 + 3 x^5 + 6 x^4 + 7 x^3 + 6 x^2 + 3 x + 1)\sum_{j=0}^{\infty}\binom{j+3}{3}x^{3j}$$ So the coefficient of $x^{25}$ is: $$3\binom{11}{3}+6\binom{10}{3}$$ More generally, the number ...

6

A vertex of the polyhedron $P = \{x \in {\mathbb R}^n: Ax \le b\}$ is defined by the solution of $n$ of the equations $(A x)_i = b_i$ corresponding to linearly independent rows of $A$. In general, not all of those will be vertices, because they may violate other constraints. But the number of vertices is at most $m \choose n$. EDIT: P. McMullen improved ...

6

Hint: Pick a point $p$ and look for a point of maximum of the function $f(k)=||p-k||, k\in K$.

6

The answer is affirmative. You want to verify $x \in P_2 \; \forall x \in P_1$. This is much like Robust Optimization, and the solution technique is the same. Let me write the constraints for $P_1$ as $Cx \leq d$ and for $P_2$ as $Ax \leq b$ for convenience. For each constraint in $P_2$, $(a^i)^T x \leq b_i$, we want to know if it is satisfied for all $x \in ... 6 Set$t\in\{0,1,2,\cdots\}$, $$3x+y+z+t=25$$ Since$x\in\{0,1,\cdots,8\}$then$y+z+t=25-3x$and we have $$\sum_{x=0}^{8}\binom{25-3x+3-1}{2}$$ 5 A point is a vertex of a closed convex polytope iff it's not expressible as a nontrivial convex combination of other points in the polytope. It's clear that the$0$-$1$matrices with$2$ones in each row and column are not expressible as nontrivial convex combinations of other points in the polytope$P$. Therefore resolving question$2$also solves ... 5 If you know both the$V$and$H$representations of your original polytope, then each of the two polytopes have vertices given by the original vertices that are all on one side of the hyperplane (i.e.$c \cdot x \leq d$or$c \cdot x \geq d$), combined with the new vertices given by the vertices of the solution to the combined equations/inequalities$c \cdot ...

5

Your question seems to me to indicate several confusions. Here are some facts you should understand. They follow from the definition of "convex hull". A set has just one convex hull, so you needn't ask about "all convex hulls". If a set is convex then it is its convex hull (as @YvesDaoust comments). The convex hull of a finite set will be a polytope. Its ...

4

It's false. To see that, introduce the new constraint $10b - 7a \leq 17$ to your example to create a new polytope $P'$. This constraint cuts off the point $N$ but keeps $M$ in $P'$. Thus $M$ minimizes $f$ over $P'$. The closest point to $x$ on $M$'s facet is now $(1.5, 2.75)$, which is the intersection of the lines $10b-7a=17$ and $2b-a=4$. However, the ...

4

(Omniscient Google taught me that) a bijection between bracketings and Schröder paths is described clearly in E. Delucchi's handouts. Description of the incidence relation definitely can be extracted from this bijection but I failed to do it so far. Update (05.2013). The incidence relation («flips between Dyck paths») is described in M. Gorsky's preprint (...

4

1) As my understanding, the orientation of g.e depends on both k-cell e and the element g. It could be defined as below: Suppose that B the chosen basis for the k-dimensional space containing k-cell e and B' the chosen basis for the k-dimensional space containing f. The orientation is defined by the sign of the determinant of the matrix which exactly is the ...

4

Perhaps I'm overloooking something, but it seems to me that the extreme points of $C_n$ are of three sorts. (1) The zero vector. (2) The standard unit vectors, with a $1$ in a single component and zeros in the other $n-1$ components. (3) Vectors with the entry $1/2$ in some set of three or more components and zeros in the remaining components. If that's ...

4

Unless I misunderstood your definition of strong equidistribution I think that your claim that 20 is the maximum cardinality is wrong. Edit: A trivial example is that $n$ equally spaced points along the equator (with their longitudes differing by $2\pi/n$) are strongly equidistributed according to this definition. You can choose $n$ to be as large as you ...

4

The answer to both questions is no. For the first, consider the following arrangement of 5 lines in $\mathbb{R}^2$. None of the bounded cells has $5$ facets. For the second, consider the following situation with $7$ planes in $\mathbb{R}^3$. We cut a cube by an hyperplane passing by the middle point of $6$ edges as in the picture. It separates the cube in ...

4

Density vs sparsity for polynomials is an informal distinction: a (multivariate) polynomial is sparse if "most" of the coefficients of its monomials are zero, and dense otherwise. If you have not found this reference yet, Sturmfels' book on solving polynomial equations has a chapter on Bernstein's theorem, and is in general very instructive.

4

Here is a simple explanation if you know some linear algebra and polyhedral geometry: Given $d$ vectors in $R^d$, that form a $d \times d$ matrix $A$, the volume of the parallelopiped $\{ \sum_i c_i v_i \, | \, 0 \leq c_i \leq 1\}$ spanned by the vectors is the absolute value of the determinant of $A$. The volume of the simplex $\{ \sum_i c_i v_i \, | \, c_i ... 4 Well, here's one way to do it. Let$A_{i2}$and$b_{i2}$denote the$i$th row of$A_2$and$i$th element of$b_2$, respectively. Then solve$m$linear programs: $$\begin{array}{ll} \text{minimize} & A_{i2}^T x - b_{i2} \\ \text{subject to} & A_1 x \geq b_1 \end{array} \qquad i=1,2,\dots, m$$ If any of these have a negative objective, including ... 4 The two sources are using different notation. Ziegler's vertex$(312)$is a permutation that maps$x_3$to$1$,$x_1$to$2$, and$x_2$to$3$, corresponding to the point$(2,3,1)$in space. It is adjacent to$(132)$and$(321)$(Ziegler notation) which are points$(1,3,2)$and$(3,2,1)$, all of which is consistent with the Wikipedia picture. 4 We can work with standard embeddings of the$n$-cube (as$[-1,1]^n$) and cross-polytope (vertices$(\pm1,0,0,\ldots) $,$(0,\pm1,0,\ldots) $, etc.) and the embedding of the$n$-simplex in$\mathbb{R}^{n+1}$given by$0\leq x_i\leq 1$and$\sum_{i=0}^{n+1}x_i=1$. In these coordinates, the distance from the cube's vertices to its center is$\sqrt{n} $while ... 4 Cartesian products of polytopes$P,Q$are indeed polytopes again. The vertices are pairs of vertices$(p,q)$where$p$is a vertex of$P$, and$q$is a vertex of$Q$. In fact, if you have two polytopes, say$P \subset \mathbb{R}^n$and$Q \subset \mathbb{R}^m$, then all faces of$P \times Q$are just the Cartesian products of faces of$P$and$Q$. You can ... 4 (1) A minor addition to your list: Ellipsoids are just linear transformations of spheres. If$M$is a linear transformation applied to sphere$S$, then the volume of the ellipsoid is vol$(S) \cdot$det$(M)$. Here is an explicit reference: Wilson, A. John. "Volume of n-dimensional ellipsoid." Sciencia Acta Xaveriana. 2009. That must be$a_1 a_2 a_3 \cdots$. ... 4 As we see in Height of$n$-simplex, the altitude (height) of a regular$n$-simplex of edge length$a$is $$h_n = a\sqrt{\frac{n+1}{2n}}.$$ The inradius$r_n$is the distance from the centroid of the regular$n$-simplex to the center of a hyperface, so$r_n = \frac 1{n+1} h_n.$Therefore $$r_n = \frac a{n+1} \sqrt{\frac{n+1}{2n}} = \frac{a}{\sqrt{2n(n+1)}}... 4 Here's a non-convex example in three dimensions. Consider the union of two tetrahedra, each with base with vertices (1,0,0), (4/5,3/5,0) and (4/5,-3/5,0). One of the tetrahedra has fourth vertex (0,0,1) the other (0,0,-1). There's no example in the plane. 4 Lets define f_i as the fraction of the total money bet on horse i:$$f_i \equiv \frac{x_i}{\sum x_i}$$Then the conditions are$$a_if_i>1\ \ \forall i$$And$$\sum f_i = 1$$Assume for a moment that we want to get the same amount no matter which horse wins. Call the ratio of the winnings to the amount invested M. Then$$a_if_i -1 \equiv M \ \ \forall i$$... 4 Yes, this indeed the case. The proof has several ingredients. Burnside's theorem: Suppose that G< GL(n, {\mathbb C}) is an irreducible subgroup, i.e. a subgroup which does not preserve any proper linear subspace in {\mathbb C}^n. Then the linear span of G is the entire group M_n({\mathbb C}) of complex n\times n matrices. (Take a look for ... 3 The polytope can be written as Ax \geq b (where rows of A contain your v vectors). For each row v = [v_1 v_2 \ldots v_n] of A, solve the LP$$ \begin{array}{c} \min v^T x \\ Ax \geq b \end{array}$$The half-space defined by this$v$is not redundant if and only if the optimum value obtained above is equal to the corresponding$b\$ value.

Only top voted, non community-wiki answers of a minimum length are eligible