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

learn more… | top users | synonyms

4
votes
1answer
82 views

How to prove the existence of the polytope in $\mathbb{R}^d$ with a given number of faces, minimizing the isoperimetric ratio?

This is the isoperimetric type question. We know that in $\mathbb{R}^d$, balls are the sets that minimize the isoperimetric ratio $\frac{S^{d}}{V^{d-1}}$, where $S$ is the surface area and $V$ is the ...
4
votes
0answers
57 views

Prove or disprove a claim about covering a polytope by convex polytopes in a certain way

Here is the claim: Given a polytope $K$ in a unit ball in $\mathbb{R}^d$, there exists a universal constant $C(d)>0$ depending only on $d$ and a countable collection of convex polytopes ...
5
votes
1answer
39 views

Uniform Sampling Subject to Linear Equalities and Non-Negativity Constraint

I'm trying to sample uniformly on the intersections of faces of several simplicies, with all coordinates being non-negative. That is, given constraints $$A\vec{x}=\vec{b} \ \ and \ \ \vec{x} \geq ...
17
votes
1answer
476 views

Egalitarian measures

A question I got asked I while ago: If $T$ is a triangle in $\mathbb R^2$, is there a function $f:T\to\mathbb R$ such that the integral of $f$ over each straight segment connecting two points in the ...
1
vote
0answers
55 views

About properties of polynomials with common interlacing

Say $\{a_1,a_2,..,a_n\}$ and $\{b_1,b_2,...,b_n\}$ be the real roots of two monic polynomials of degree $n$ which have a common interlacing. (say I have arranged the roots in increasing order) Can ...
20
votes
10answers
9k views

Algorithm for finding the volume of a convex polytope

It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...
1
vote
1answer
173 views

Cardinality of non-integer points in the translation of the Minkowski sum of convex hull.

Let $\operatorname{conv}(a_1,\ldots,a_m)$ denote the convex hull of $\{a_1,\ldots,a_m\}$. Let $\mathbb{Z}_+=\mathbb{N}\cup\{0\}$ and $\mathbb{Q}_+$ denotes the positive (inluding 0) rational numbers. ...
7
votes
0answers
114 views

How many facets can $\{\|D^T x\|_1\leq 1\}$ have?

$\newcommand{\RR}{\mathbb{R}}$Consider $x\in\RR^n$ and $D\in \RR^{n\times p}$ with $p\geq n$ and full rank. My question is: How many facets can the polytope $ \{x\in\RR^n\ :\ \|D^T x\|_1\leq 1\}$ ...
5
votes
1answer
129 views

Measurement of “symmetry” of a convex body

I often hear that the regular simplex is "the least" symmetric convex body, and I've heard that there are some measures of symmetry of a body, that the simplex minimizes. Could you please explain or ...
9
votes
2answers
235 views

Book on the tetrahedron

Does anybody know of a book containing "all you want to know about the tetrahedron"? What you want to know should include basic geometry of the tetrahedron, study of orthocentric tetrahedra, the Monge ...
1
vote
1answer
176 views

Regular unimodular triangulation for a certain simplex

Consider an $n$-simplex with vertices given by $(0,0,\dots,r_i,r_{i+1},\dots,r_n)$ where $r_1,\dots,r_n$ are given natural numbers, and $i=0,1,\dots,n+1$. Does this simplex admit a regular, ...
22
votes
5answers
698 views

Is the diameter of a centrally symmetric convex body realized by a pair of antipodal points?

Let $S \subset \mathbb{R}^n$ be the boundary of a centrally symmetric convex body and provide $S$ with the geodesic metric given by its embedding in Euclidean space (i.e., the distance between two ...
5
votes
2answers
120 views

Differentiability of polytope shadow areas

Let $P$ be an opaque convex polyhedron containing the origin in $\mathbb{R}^3$, and let $S$ be an origin-centered sphere strictly containing $P$: $S \supset P$. For a point $x$ on $S$, let $\sigma(x)$ ...
0
votes
1answer
104 views

polynomial expression for counting number of integral points of a set

Let $v_i=a_ie_i\in\mathbb R^d$ and $w_i=b_ie_i\in\mathbb R^d$ for $i=1,\dots,d$ where $e_i$'s are unit vetcors and $a_i,b_i$ are positive integers. Let $$S=conv\{0,rv_i+sw_i:i=1,\dots,d\}.$$ Can we ...
2
votes
1answer
36 views

Efficient algorithm for finding normals of a high dimensional convex hull with few facets

I am looking for the most efficient algorithm to use to, given a set of points in $d$ dimensional space, find the normals of the convex hull of these points, given that I know that the number of ...
4
votes
2answers
62 views

Expressing a convex Polytope as a sublevel set of a function

Given an n-dimensional polytope $P$ in $\mathbb R^n$, Given as a convex hull of a finite set of points, $S$ I would like to construct an expliict formula for a function $f\colon \mathbb R^n \to ...
2
votes
0answers
126 views

Find the intersection between two convex hulls, in this specific case

We work over $\mathbb{R}^K$. Let $V$ be the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$. Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
2
votes
0answers
61 views

Newton polyhedron and product of ideals

Let $I$ be an ideal generated by monomials $\underline{x}^{\underline{a}_1},\ldots ,\underline{x}^{\underline{a}_s}$ and $J$ be the ideal generated by $\underline{x}^{\underline{b}_1},\ldots ...
46
votes
5answers
2k views

Do unit quaternions at vertices of a regular 4-simplex, one being 1, generate a free group?

Choose unit quaternions $q_0, q_1, q_2, q_3, q_4$ that form the vertices of a regular 4-simplex in the quaternions. Assume $q_0 = 1$. Let the other four generate a group via quaternion ...
5
votes
1answer
138 views

Integer decomposition of dilated integral polytopes

For $n > 0$, let $P$ be an integral polytope, that is, the convex hull in $\mathbb{R}^n$ of points in $\mathbb{Z}^n$. Suppose that $\dim(P) = n$. Question: Given $d > n + 2$ is it true that $$ ...
1
vote
1answer
90 views

Extreme points of convex hull of Minkowski sum [closed]

Let $\operatorname{conv}(a_1,\ldots,a_m)$ denote the convex hull of $\{a_1,\ldots,a_n\}$. Let $P = \operatorname{conv}(a_1,\ldots,a_p)$ and $Q = \operatorname{conv}(b_1,\ldots,b_q)$ be two convex sets ...
3
votes
1answer
195 views

Dehn-Sommerville relations for $\Delta$-complexes

Let $M$ be a closed, triangulated manifold of dimension $m$ and $K(M)$ be its triangulation. Let $f_i$ denote the number of $i$-simplices of $K(M)$. As proved by Klee the face numbers satisfy the ...
8
votes
2answers
467 views

When does every point in a polytope lie along a chord between its edges?

Consider the 3-simplex, or tetrahedron, in 3-space. Regardless of the positions of the vertices, every point in the simplex lies on a chord between two non-adjacent edges of the simplex. Or, ...
3
votes
1answer
230 views

Polar interpretation of convexity

Let $C$ be a convex polygon in the plane containing the origin, and let $r(\theta)$ for $\theta\in[0,2\pi)$ be a parametrization of its boundary. Is there a condition on $r$ that is equivalent to (or ...
1
vote
0answers
40 views

Projection of a ray onto a random polytope

Suppose $P$ is a polytope formed by $p$ (general) random planes in $\mathbb{R}^n$. We assume $p \asymp n$ and $P$ has a diameter $O(\sqrt{n})$. For any $x \in \mathbb{R}^n$, denote by ...
19
votes
1answer
440 views

Update to Shephard's “Twenty Problems on Convex Polyhedra”

Forty-three years ago, Geoffrey Shephard published an influential list of open problems on convex polyhedra. Progress has been made on several of his problems, and perhaps some have been completely ...
5
votes
1answer
119 views

Approximation of convex body by polytopes

In a recent survey paper, Approximation of convex sets by polytopes, Bronstein claims that under Hausdorff distance $\rho_H$, for every convex body $U$, $$\rho_H(U,\mathcal{P}_n)\leq c(U) ...
2
votes
2answers
168 views

4-polytope with vertices at the binary octahedral group

Does anybody know if there is a convex polytope in $R^4$ with vertices at the binary octahedral group (identitfying $H$ with $R^4$). The binary tetrahedral group lies at the vertices of the ...
1
vote
1answer
85 views

What is the functional form of the projections of a subdimensional polytope?

Let $\mathbf{S}$ be a $m\times n$ matrix, with $m < n$. We define a subdimensional polytope as the space of $n$-dimensional vectors $\mathbf{x}$ that satisfy the following equation: ...
3
votes
1answer
123 views

Computionally efficient vertex enumeration for (convex) polytopes

Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be ...
17
votes
5answers
409 views

How many unit simplices are needed to cover a unit $n$-cube?

The volume of an $n$-dimensional simplex of unit edge length is $$V(n) = \frac{\sqrt{n+1}}{n! 2^{n/2}} \;,$$ so at least $\lceil 1/V(n) \rceil$ such simplices are needed to cover the unit $n$-cube. ...
4
votes
1answer
58 views

Largest regular $k$-simplex inscribed in a $d$-cube, $k < d$

The largest (by edge length) regular simplex inscribed in a unit cube is well known in $\mathbb{R}^2$ and $\mathbb{R}^3$:     Image sources: left: NMSU, right: Mathworld. A recent ...
7
votes
2answers
183 views

Decomposition of a cross-polytope into simplices

Consider the standard embedded $n$-cross polytope $P_n$ with vertices $\pm e_i \in \mathbb R^n$. Let us consider decompositions of this polytope into $2^{n-1}$ simplices, such that these simplices ...
1
vote
1answer
92 views

Computation of extreme rays of rational polyhedral cones - Hemmecke's project and lift algorithm

I am working on an implementation of Raymond Hemmecke's algorithm for finding generating sets of cones: http://arxiv.org/abs/math/0203105 Unfortunately I am struggling to make the algorithm work on ...
26
votes
14answers
6k views

Open problems in Euclidean geometry?

Which are some (research level) open problems in Euclidean geometry ? (Edit: I ask just out of curiosity, to understand how -and if- nowadays this is not a "dead" field yet) I should clarify a ...
16
votes
4answers
777 views

Is there a midsphere theorem for 4-polytopes?

The (remarkable) midsphere theorem says that each combinatorial type of convex polyhedron may be realized by one all of whose edges are tangent to a sphere (and the realization is unique if the center ...
1
vote
1answer
68 views

4D Duoprisms based on nonconvex polygons

A duoprism is a polytope that can be expressed as the Cartesian product of two polytopes (each of dimension $\ge 2$). Four-dimensional duoprisms in particular have been studied: $$P \times Q = \{ ...
38
votes
0answers
1k views

Intersecting Family of Triangulations

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let ...
13
votes
2answers
261 views

Can any simplex shadow-project to a regular simplex?

Every triangle $A$ can be oriented in $\mathbb{R}^3$ so that its orthogonal projection (shadow) onto the $xy$-plane is an equilateral triangle $Q$:               ...
3
votes
0answers
79 views

Intersection numbers on blow ups of toric varieties

Suppose we have a smooth, complete toric varietiy $X_{\Sigma}$ of dimension $n$. Let $\sigma_k \in \Sigma(k)$ a smooth $k$-dimensional cone in $\Sigma$ and suppose we make the toric blow up at the ...
3
votes
1answer
126 views

convex decompositions of the sphere

Consider a decomposition of the sphere $S^n$ into convex pieces (that is, every cell of the cell decomposition is convex, in particular, is contained in a hemisphere). Consider the $k$-skeleta of ...
3
votes
0answers
82 views

Polytopes whose intersections have few vertices

This is related to one that I asked earlier: The intersection of two $l_1$ balls My question: are there any general classes of polytopes $P_1,P_2\subset\mathbb{R}^n$ such that $P_1$ has few ...
2
votes
0answers
85 views

The intersection of two $l_1$ balls

Let $B_1$ and $B_2$ be two balls in $\mathbb{R}^n$ with respect to the $l_1$ norm that have different radii and different centers. Is there an upper bound for the number of vertices that $B_1\cap ...
1
vote
0answers
30 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
2answers
160 views

name for a polytope constructed from a system of linear equations?

To a system of inhomogeneous linear equations, one can associate a polytope, as follows. Let $A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^m$ and $V=\{x\mid Ax=b, \text{support of $x$ ...
3
votes
2answers
131 views

How to (efficiently) find intersection of two polyhedral cones?

I have two polyhedral cones represented by their rays. I am looking to find their intersection, which would also be a polyhedral cone, hopefully efficiently. Does anybody know a way to do that? ...
3
votes
2answers
85 views

algorithm of polytope

Basically, we have an incremental sets of vertices $${V_1} \subset {V_2} \subset ...$$ for each of them, we could build a polytope $${P_i} = Conv({V_i})$$ Consequently, we can compute $${F_i} = ...
1
vote
0answers
71 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 ...
2
votes
0answers
53 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 ...
8
votes
3answers
356 views

Positivity of Ehrhart polynomial coefficients

Are there any results stating that a given family of convex polytopes have Ehrhart polynomials with non-negative coefficients? What methods are available for proving such a property for some family ...