Questions tagged [convex-polytopes]
Convex polytopes are the convex hulls of a finite set of points in Euclidean spaces. They have rich combinatorial, arithmetic, and metrical theory, and are related to toric varieties and to linear programming
942 questions
1
vote
0
answers
46
views
Non-negative polynomials $f(p), p\in P$ from Polynomial ideal where $P$ compact polytope?
Partially related to Non-negative Polynomials from Polynomial Ideal? where focus on graph theory but now I want to understand more generally how to determine non-negativity in more general case.
A. ...
- 143
10
votes
0
answers
333
views
Bi-spherical polyhedra
Bicentric polygons have been studied: a polygon all of whose vertices lie on its
circumcirle, and whose incircle is tangent to every edge:
I have not been able to find a comparable literature ...
- 151k
1
vote
0
answers
57
views
Is the complement of a vertex figure in an (abstract) polytope connected?
I consider an (abstract) regular polytope $P$, and $H$ a vertex figure of $P$. Is the complement $P \setminus H$ connected (as a poset, in the sense that its Hasse diagram, ignoring the improper faces,...
- 31
1
vote
1
answer
164
views
number of affine pieces of linear interpolation of convex functions in high dimension
Consider a convex function $f$ defined on a $d$-dimensional hypercube $[0,1]^d$. Now for fixed $m \in \mathbb{N}$, consider the grids $\mathcal{G}_m=\{(i_1/m,\cdots,i_d/m)\}$ where $i_\alpha\in\{0,1,\...
- 599
9
votes
1
answer
1k
views
Finding the vertices of a polyhedral complex coming from a GIT wall and chamber decomposition
I am interested in a polyhedral/combinatorics problem that arises in algebraic geometry in the context of geometric invariant theory (GIT).
Algebro-geometric background: Consider the natural ...
- 1,871
4
votes
1
answer
200
views
Toric ideal of slice of a polytope?
Given a collection $A:=\{a_1, \ldots ,a_n \}$ of different integer points in $\mathbb{N}^d$, which span an affine hyperplane when viewed in $\mathbb{R}^d$, one can define a toric ideal $I_A$ from a ...
- 902
2
votes
0
answers
283
views
Distance function from the origin to the boundary of a convex polytope
Let $K\subseteq \mathbb R^n$, $n\ge 3$ be a convex bounded polytope containing the origin in its interior. Consider the unit sphere with geodesic distance $(\mathcal S^{n-1},d)$ and define the ...
- 21
3
votes
1
answer
258
views
Classification of lattice polytopes with small number of lattice points in the facets
Suppose $P$ is a convex lattice polytope in $Z^3$ without interior lattice points, and we require the interior lattice points of each facet(i.e. dimensional 2 faces) are neither too much nor too few, ...
- 3,472
0
votes
0
answers
107
views
Under which conditions is the union of conic hulls of sets in a cartesian product equal to $\mathbb{R}^N$?
Question: Under which conditions on $A, B\in\mathbb{R}^{N\times N}$ is the function $f: \mathbb{R}^N\mapsto \mathbb{R}^N$,
$$f(v) = A[v]_+ + B[-v]_+$$
surjective? Here $[.]_+$ is an elementwise ...
- 123
3
votes
1
answer
141
views
Number of lattice polytopes contained in a given lattice polytope?
Given a (convex) lattice polytope, suppose we want to list or count all (convex) lattice polytopes (of the same dimension) contained in it. Are there efficient ways to do this?
- 495
1
vote
1
answer
187
views
Straight Line Passing Through a Convex Region
Is there any test to tell me whether a straight line in a 3D euclidean space passes through a bounded closed convex region? To focus on a more specialised version of the problem, you can assume that ...
- 113
2
votes
0
answers
63
views
Number of simplices contained in a convex body
I am interested in the following question:
Given a convex body $K$ in $\mathbb{R}^d$ and an $\epsilon>0$ small enough, how many $d$-simplices $\{D_i\}_{i=1}^m\subset K$ do we need at least so that ...
- 599
12
votes
0
answers
533
views
Reciprocity (Ehrhart-style) for real polytopes?
Is there some sense in which the well-known Ehrhart reciprocity law for rational, convex, polytopes can be extended to any convex polytope with arbitrary real vertices?
In other words, given any ...
5
votes
0
answers
232
views
4D polytope analogues of the icosahedron/Rogers-Ramanujan continued fraction relationship?
The formula for the j-function which employs polynomial invariants of the icosahedron,
$$j(\tau)=-\frac{(r^{20} - 228r^{15} + 494r^{10} + 228r^5 + 1)^3}{r^5(r^{10} + 11r^5 - 1)^5}$$
where,
$$r^{-1}-...
- 12.6k
2
votes
0
answers
92
views
A convex analysis theorem improvement
John's theorem states that to any full-dimensional symmetric convex set $K\subseteq R^n$ and any Ellipsoid $E\subseteq R^n$ that is centered at origin, there exists an invertible linear map $T$ so ...
- 13.9k
1
vote
1
answer
152
views
Submodular measures on the hypercube
By the hypercube I mean the lattice formed by all n-bit strings ordered by pointwise inequality. For example, $000 \leq 110$, $010 \leq 110$, $110$ and $001$ are not comparable. Further we have the ...
- 406
2
votes
1
answer
223
views
Decide inside/outside convex hull using only distances in graph
Given a weighted, undirected graph G with K knodes k1 … kK. I have a K times K matrix containing the shortest distances between each pair of points.
Is it possible (if yes how), to decide if a point ...
- 21
4
votes
0
answers
202
views
An isoperimetric inequality for "order" polytopes
I am looking for an isoperimetric inequality for order-like polytopes.
An order polytope $K\in \mathbb{R}^n$ is defined by a set of linear inequaities:
$$ \forall i \; 0\leq x_i \leq 1 $$
and
$ ...
- 243
3
votes
1
answer
439
views
Convex n-polytope general position vectors to general position vectors of tetrahedron
I asked this question in a comment to this question, but got no response. I thought that perhaps it needed more exposure, so I made it a question in itself.
Define a set of general position vectors $...
- 4,842
3
votes
1
answer
356
views
Empty convex polytopes for random point sets
I know of the famous results on the Erdős-Szekeres empty convex polygon problem in the plane
(the Happy-Ending Problem), and I know that there are higher-dimensional extensions.
A great source (...
- 151k
3
votes
0
answers
65
views
"Spherelike" embedding for smooth Fano polytope
Let $\mathbb{R}^n$ be a vector space with Euclidean inner product and $\mathbb{Z}^n \subset \mathbb{R}^n$ be a lattice. Let $P$ be a full dimension convex lattice polytope in $\mathbb{R}^n$ containing ...
- 316
2
votes
1
answer
303
views
Max/min problems related to associahedra or their duals (ions on balls revisited)
Original motivation: This is a follow-up question to and generalization of MO Q78877 on equilibrium configurations of ions on n-Dim balls. Henry Cohn gave an excellent answer dispelling my naive ...
- 10.5k
0
votes
1
answer
584
views
The query concerning the Euler-Poincare formula’s generalizations
Euler's equation for polyhedral, Euler's polyhedral formula, V – E + F = 2, where V, E, and F, are the number of points, edges and faces, was discovered by Leonhard Euler in 1752. However, the basic ...
- 11
9
votes
1
answer
523
views
The volume of the “unit ball” in $\mathbb{R}^{m\times n}$ with respect to the cut norm
This question is inspired by the question “ε-nets with respect to the cut norm” by the user Aaron, which had been reposted to cstheory.stackexchange.com.
The cut norm ||A||C of a matrix A=(aij)∈ℝm×n ...
- 1,959
1
vote
0
answers
126
views
Convex Optimization related problem
Suppose two non-negative convex functions $f$ and $g$ be given.
We want to solve the following optimization
$$\max_{g\leq\epsilon}f.$$
Now suppose that both $f$ and $g$ can be upper-bounded by a ...
- 1,109
3
votes
1
answer
271
views
The facial structure of the convex hull of a family of characteristic functions
Let $S$ be a finite set and let $\mathcal{A} \subset\mathcal{P}(S)$ be a family of subsets of $S$. Consider the convex polytope spanned by the characteristic functions of members of $\mathcal{A}$ :
$$...
- 60.5k
1
vote
0
answers
80
views
A version of isotone projection cones
We write $a \succeq b$, where both $a, b \in \mathbb{R}^n$, as a shorthand for $a_i \ge b_i$ for all $1 \le i \le n$. Let $C$ be a closed convex cone in the first orthant of $\mathbb{R}^n$ and denote ...
- 773
1
vote
0
answers
109
views
Volume under the intersection of scaled simplices
This is rather specific but I need to compute the volume under the intersection of rescaled simplexes, that is, the volume of the space:
$\left\{x \in \mathbb{R}^n|\sum_i c_{ki} |x_i| \leq1\; k = 1 \...
5
votes
0
answers
324
views
Lattice points inside a (n-dimensional) tetrahedron
Hi, overflowers.
I was interested in a sharp lower bound for the number of lattice points (say, integral lattice points) inside the tetrahedron defined by the coordinate hyperplanes and $x_1/a_1+...+...
- 306
3
votes
0
answers
149
views
Dead Flies Problem [duplicate]
If a set of points in the plane contains one point in each convex region of
area 1, then can it have finite density?
what is the density of the points? In my understanding, it means the average ...
user39815
7
votes
2
answers
846
views
What is known about polyhedra nets that allow overlapping?
It is an open problem that the net of any convex polyhedron can be unfolded onto a flat plane with no overlapping. Is anything known if we allow x faces to overlap? For example, is it known if any ...
- 2,615
5
votes
2
answers
475
views
Making 'circles' on a lattice/ Making distinct fractions from partitions of a number
First formulation: discrete geometry
Pick your favourite 2D square lattice (I'm sure we all have one...) and try to place n points 'in a circle' (that is: in general position [no 3 should be colinear] ...
- 3,230
2
votes
0
answers
193
views
Definition of self-dual polytope
Given a d-polytope $P$ we define the c-dual polytope as $P^\ast = \{y\in R^d \mid x\cdot y\geq -c, \forall x\in P\}$. Then I say that a polytope is c-polar self-dual if $P=P^\ast$. I cannot find this ...
- 360
0
votes
0
answers
52
views
Efficient sampling from a polytope with large number of contraints [duplicate]
As far as I know, the most popular way to sample from a polytope (in H-representation)
\begin{equation}
\mathcal{P} := \{z \in \mathbb{R}^n | (Az)_j \le b_j\; \forall j=1,2,\ldots,m\}
\end{equation}
...
- 6,853
3
votes
1
answer
259
views
Is the number of vertices of a convex $d-$dimensional lattice polytop without interior lattice points bounded?
The lattice polytop $[0,n_1]\times[0,n_2]\times\dots\times[0,n_{d-1}]\times[0,1]$ contains
$(n_1+1)(n_2+1)\cdots(n_{d-1}+1)2$ integral points on the boundary and no integral points in
its interior. ...
- 17.9k
3
votes
1
answer
857
views
An intersection of a convex polytope and a simplex
How to determine whether an intersection of a convex polytope and a simplex in $R^{n}$ is not empty?
The polytope is given in a halfspace representation.
I'm aware that there are some algorithms ...
5
votes
1
answer
865
views
A Counterexample to the HIrsch Conjecture
Recently Francisco Santos has announced that he has a counterexample to the Hirsch conjecture. The last I heard it was circulating among several people and there would be a public version of it ...
- 6,523
2
votes
1
answer
134
views
Integer point in a non-empty polytope
I have a high-dimensional, non-empty polytope $Ax\geq b$ sitting inside the cube ($0\leq x_i \leq 1$). Is there any general theory or technique to show that this polytope contains an integer point, ...
- 243
0
votes
0
answers
752
views
Upper and Lower Bounds of the Total Surface Area of Convex Polytopes that Partition a Hypercube
Let $C$ be a hypercube in $\mathbb{R}^D$ with edge length of $L$. Let $\mathcal{P}_1,\ldots,\mathcal{P}_K$ be $K$ convex polytopes that partition $C$. Let $S_k$ be the surface area of the polytope $\...
- 111
8
votes
1
answer
556
views
A variation on "Hearing the shape of a drum" for polytopes.
Let $\varphi:\mathcal S^{d-1}\longrightarrow \mathbb R_{>0}$ be a strictly positive function describing the boundary $\varphi(\mathbf x)\mathbf x,\mathbf x\in\mathbb S^{d-1}$ of a $d-$dimensional ...
- 17.9k
3
votes
0
answers
133
views
Convex polyhedra jammed in $k$ disjoint holes
For a given convex polyhedron $P \subset \mathbb{R}^3$,
I was imagining finding the optimal "fixing" of $P$ in holes (or jamming them in "mud"),
which led to the following question.
First, scale $P$ ...
- 151k
0
votes
0
answers
112
views
Ref request: If an affine subspace $V$ of $\mathbb R^n$ meets an $n$-dimensional polytope $P$, then it meets $P$ in a face of dimension $\le n-\dim V$
Let $P$ and $V$ be, respectively, a bounded full-dimensional polytope and an $m$-dimensional affine subspace of $\mathbb R^n$, and assume $P \cap V$ is non-empty.
Q1. Could you provide me with a ...
- 10.5k
0
votes
2
answers
611
views
0
votes
1
answer
158
views
2-neighborhood of a simplex
Let $\Delta$ be an $n-1$-simplex in ${\mathbb R}^{n-1}$. For each vertex $v$ of $\Delta$ let $H_v$ be the hyperplane through $v$ and parallel to the opposite facet. By 2-neighborhood of a simplex I ...
- 65
8
votes
2
answers
217
views
Flipping Hilbert series of semigroup rings
I'll first give intuition, and then give a precise statement.
For $|z|<1$, we have $\sum_{i \geq 0} z^i = 1/(1-z)$. For $|z|>1$, we have $\sum_{i<0} (-1) z^i=1/(1-z)$. Thus, the two ...
- 156k
1
vote
0
answers
59
views
Conditions on probability measure that generates non-void random polytope
Let $C$ be a non-void compact convex set in $\mathbb{R}^d$, and $\nu$ a probability measure on $C$. Then under what conditions on $C$ and $\nu$, the following statement is true: If $X_1,\cdots,X_{d+1}$...
- 599
2
votes
0
answers
163
views
existence of lattice point in polytope
This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...
- 501
3
votes
0
answers
188
views
Covering points with a convex hull
Consider a set of $n$ points $x_1,\ldots,x_n \in \mathbb{R}^d$, for some $n \gg d$. Suppose $\{x_1,\ldots,x_n\} \subset C \subset \mathbb{R}^d$. Say that a set of points $y_1,\ldots,y_m \in C$ covers $...
- 794
4
votes
1
answer
626
views
Embed the intersection of an n-dimensional unit $L_1$ sphere and a hyperplane into an (n-1)-dimensional unit $L_1$ sphere.
In $\mathbb{R}^n$, given an unit $L_1$ sphere $\mathcal{B}_n: |x_1|+|x_2|+\ldots+|x_n|\leq 1$ and a hyperplane $\mathcal{P}: a_1x_1+a_2x_2+\ldots+a_nx_n=0$. Does there always exist a rotation such ...
- 59
2
votes
1
answer
229
views
How can pushing a vertex in a polytope lead to merging facets?
I'm trying to understand the Lemma 2.2 and Corollary 2.3 of Francisco Santos paper "A counterexample to the Hirsch conjecture": http://arxiv.org/abs/1006.2814
Corollary 2.3 is a proof of a result of ...
- 75