Skip to main content

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

Filter by
Sorted by
Tagged with
5 votes
1 answer
384 views

Examples of Polyhedra with Large Shadows

Let $P \subseteq \mathbb{R}^n$ be a polyhedron described by $\mathcal{O}(n^{c_1})$ inequalities, where $c_1$ is a constant. Moreover, let $M\colon P \to \mathbb{R}^2$ be a linear mapping. I'm looking ...
Christopher's user avatar
9 votes
2 answers
153 views

Generate polyhedra by collapsing vertices of a polyhedron

I am looking for basic information about the following idea: (I) Consider a square. By collapsing two adjacent vertices, we obtain a triangle. (II) Consider a three-dimensional cube. By collapsing a ...
shuhalo's user avatar
  • 5,327
5 votes
0 answers
233 views

Is there a well-established terminology for polyhedra/polytopes?

I got confused lately. It seems like in the metric context a polyhedron tends to mean an intersection of a finite number of half-spaces, while a polytope is a convex hull of a finite set of points. At ...
მამუკა ჯიბლაძე's user avatar
8 votes
0 answers
6k views

Convex hulls of compact sets

Let $A$ be a compact set in a separable Hilbert space $H$, and let $\bar A$ denote its convex hull. Is $\bar A$ compact?
Tom LaGatta's user avatar
  • 8,512
3 votes
1 answer
153 views

Taking powers of polytopes

I am not sure this is a well framed question but I would like to know if anything like "taking the power" of a polytope is known. Imagine this situation where I want to think of such a thing : say ...
gradstudent's user avatar
  • 2,246
15 votes
1 answer
640 views

Smallest regular simplex containing the unit cube in $R^n$

What is the length $e_n$ of the edge of the smallest $n$-dimensional regular simplex $S_n$ containing the $n$-dimensional unit cube $Q_n$? In particular, is there $n$ such that $e_n<\sqrt{2}(n+1-\...
Jan Kyncl's user avatar
  • 6,101
2 votes
1 answer
433 views

intersection of the unit cube and a hyperplane containing the main diagonal

Let $A$ be a linear $m$-dimensional subspace of $\mathbf{R}^n$ $m < n$, containing the point $(1,1,\ldots,1) \in \mathbf{R}^n$, and consider the intersection of $A$ and the unit cube $\Delta_n$ (...
Lior Eldar's user avatar
9 votes
1 answer
665 views

Question about tetrahedron decomposition

Are there tetrahedra which can be subdivided into three non-overlapping parts similar to the original? I believe this would require splitting one face into three parts. I know some types of tetrahedra ...
Dennis Farr's user avatar
5 votes
2 answers
563 views

Covering convex polygons with inscribed disks

The following problem came up when discussing mapping software (e.g., Google maps) with computer scientists. By $B(c,r)$ I mean the planar disk (open or closed, it doesn't matter) of radius $r$ around ...
Vidit Nanda's user avatar
  • 15.5k
0 votes
1 answer
201 views

Recursive linear programming on a linear subset of a simplex

The problem I am working on is: Given an $n$ dimensional vector $r \in \mathcal{R}^n$, and a convex set $G=\{\mu \in \mathcal{R}^n | \mu_i \ge 0, ~ \mu^T \mathbf{1}=1, ~ A\mu =0 \}$ where $\mathbf{1}...
Sungjoon Choi Samuel's user avatar
16 votes
2 answers
536 views

What is $A+A^T$ when $A$ is row-stochastic ?

This is motivated by this MO question. If $A\in{\bf M}_n({\mathbb R})$ is row-stochastic (entrywise non-negative, and $\sum_j a_{ij}=1$ for all $i$), then $M:=A+A^T$ is symmetric, entrywise non-...
Denis Serre's user avatar
  • 52.3k
7 votes
1 answer
248 views

Sample integer points of cross-polytope uniformly

For $r,d\in\mathbb{N}$, let $$C_{r,d}=\{x\in\mathbb{Z}^d: \|x\|_1\le r\}\subset\mathbb{Z}^d$$ be the set of integer points of the $d$-dimensional cross-polytope with radius $r$. What is (...
Tobias Windisch's user avatar
4 votes
0 answers
124 views

Reference for this fact about perturbed polytopes?

Let $K \subset \mathbb{R}^n$ be a polytope (i.e., an intersection of finitely many halfspaces that has finite volume) and consider $F(K) := \int_K \|x\|^2\, {\rm d}x$, where $\|\cdot\|$ is the ...
Noah Stephens-Davidowitz's user avatar
4 votes
1 answer
969 views

Simplex in convex polytope, pulling triangulation

Let $P$ be a convex $d$-dimensional polytope. I have two questions, related to triangulations of $P$. Question 1: Let $p$ be in the interior of $P$. Can I always find a triangulation of $P$, such ...
Per Alexandersson's user avatar
6 votes
2 answers
3k views

Finding the convex combination of vertices which yields an inner point of a polytope

Given a convex polytope $P\in \mathbb{R}^n$, and a point $x\in P$, Caratheodory's theorem gives us that there exists a set of at most $n+1$ vertices of $P$, such that $x$ is a convex combination of ...
Guy Adini's user avatar
  • 243
2 votes
1 answer
265 views

Is mean width a Dehn invariant?

Let $P \subset \mathbf{R}^3$ be a convex polyhedron. Let $rP$ be the dilation of $P$ by the positive real number $r$. The Dehn invariant of $P$ is an element of the weird real vector space $\mathbf{...
David Treumann's user avatar
1 vote
0 answers
196 views

Facet Enumeration Problem nondegeneracy case

Hello in case of a nondegeneracy case of the Facet Enumeration Problem, there is a polynomial algorithm for the convex hull problem as written here https://www.inf.ethz.ch/personal/fukudak/polyfaq/...
test100's user avatar
  • 11
1 vote
0 answers
368 views

Convex hull of the intersection of nonconvex sets

I have a set $D$ in $\mathbb{R}^{d+1}$ which is the intersection of $d$ domains $D_i$ given by $f(x_{i}) \leq x_{i+1} \leq g(x_{i})$ for two functions $f$ and $g$. I want to find the convex hull of $...
mono's user avatar
  • 31
1 vote
0 answers
47 views

What separates a cyclic polytope from a projective polytope?

I am having trouble understanding the difference between a cyclic polytope and a convex projective polytope as positive geometries. The link https://arxiv.org/pdf/1703.04541.pdf is the source of ...
Alexander's user avatar
  • 151
2 votes
0 answers
165 views

Link of a power series by the Bernoullis for a Riccati equation to zonotopes?

On pg. 85 of The Rise and Development of Theory of Series up to the Early 1820s by Ferraro is a series soln. of $$ d^2z/z = -x^2dx^2 $$ related to the reputed first appearance of a Riccati-type eqn.,...
Tom Copeland's user avatar
  • 10.5k
3 votes
1 answer
151 views

The center of a minimal convex superbody

Is the following true? CONJECTURE: $\,$ Let $\ B\ C\subseteq\mathbb R^n\ $ be convex bodies in $\mathbb R^n$ such that $\ C\ $ is centrally symmetric, $\ B\subseteq C,\ $ and $\ t\!\cdot\! B\ $ cannot ...
Włodzimierz Holsztyński's user avatar
2 votes
1 answer
113 views

Internal edges in Convex Polytopes

Suppose $S\subset{\mathbb R}^n$ is an infinite subset that is in general position which means that the intersection of $S$ with every affine subspace of dimension $d<n$ always contains at most $(d+...
Daryl Cooper's user avatar
1 vote
0 answers
53 views

Projecting two convex polyhedra onto their intersection

Suppose we are given two convex polyhedra $\mathcal{C}_1, \mathcal{C}_2 \subset \mathbb{R}^n$ with non-empty intersection $\mathcal{C}_1 \cap \mathcal{C}_2 \neq \emptyset$. For the orthogonal ...
madison54's user avatar
  • 337
14 votes
0 answers
479 views

Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?

After reading these very interesting questions, I came up with another one: Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
Piotr Shatalin's user avatar
20 votes
1 answer
591 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 ...
Joseph O'Rourke's user avatar
1 vote
1 answer
391 views

Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces

Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by $$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$ $$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$ I wish to find their convex hull, that is a ...
Sidharth Ghoshal's user avatar
7 votes
1 answer
824 views

Ehrhart polynomial

What is the Ehrhart polynomial of the regular cross-polytope of dimension d? Are there published upper and lower estimates?
user avatar
2 votes
1 answer
248 views

Choosing the weights of a Voronoi diagram -- is this function always the gradient of another function?

This question is related to the earlier question Weighted area of a Voronoi cell . As in that question, let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,...
Tom Solberg's user avatar
  • 4,049
3 votes
0 answers
387 views

regular triangulations of the product of two simplices

Is description of all regular triangluations of $\Delta^n\times \Delta^k$ known? (Regular triangulations are those which correspond to vertices of Gelfand--Kapranov--Zelevinsky secondary polytope, or, ...
Fedor Petrov's user avatar
6 votes
1 answer
587 views

Study of convex polytopes via commutative algebra

Let $P \subset \mathbb{R}^d$ be any convex polytope with integral vertices, and let $M$ be the additive submonoid of $\mathbb{R}^{d+1}$ which is generated by $\{ (v,1) : v \in P \cap \mathbb{Z}^d \}$. ...
Erik Friese's user avatar
6 votes
1 answer
237 views

Some polytopes in $\mathbb R^n$ whose vertices have coordinates 1, -1 or 0

Let $n$ and $k$ be positive integers with $k\leq n$. Let $P(n,k)$ be the convex hull in $\mathbb R^n$ of the $2^k {n \choose k}$ vectors whose exactly $k$ coordinates belong to $\{\pm 1\}$ all the ...
Lucien's user avatar
  • 838
3 votes
1 answer
445 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 ...
Priyavrat Deshpande's user avatar
14 votes
0 answers
254 views

Is combinatorial automorphism of symmetric convex polytope always antipodal?

The question is formulated in the title. More precisely, if $P$ is an origin-symmetric convex polytope in $\mathbb{R}^d$, and $f$ is a bijective transform of the set of the vertices of $P$, which ...
Fedor Petrov's user avatar
2 votes
0 answers
41 views

Efficient $H$ representation of matrices with distinct cyclic shift permuted entries

Given points $v_1,\dots,v_n\in\mathbb Z^n$ in codimesion $1$ hyperplane $x_1+\dots+x_n=t$ with $0\leq x_{i}$ and a cyclic shift permutation $\sigma$ where $v_1,\dots,v_n$ when written as columns of ...
Turbo's user avatar
  • 13.9k
6 votes
0 answers
491 views

Minimum solid angle and aspect ratio of an $n$-simplex

In computational geometry and other fields, it is of interest to have degeneracy measures for shapes of simplices, which quantitatively seperate the regular simplex from degenerate simplices. In two ...
shuhalo's user avatar
  • 5,327
13 votes
1 answer
1k views

When is a matrix similar to a non-negative matrix?

Consider a real square matrix $A$ of size $n\times n$. Under which conditions on $A$ does there exist a row-stochastic matrix $U$ (non-negative, rowsums = 1), such that $A'=U^{-1}AU$ is a non-negative ...
J Reichardt's user avatar
4 votes
2 answers
191 views

Affine hull of a set of non-negative matrices with fixed row-sums

Fix any non-negative matrix $M \in \mathbb{R}_{\geq 0}^{m \times n}$ that contains no zero-row and no zero-column. Further, fix any positive vector $r \in \mathbb{R}_{> 0}^m$. With $nz(M) := \{(i,j)...
cubic lettuce's user avatar
1 vote
0 answers
57 views

geometry of intersection of 2 polytope in higher dimension [closed]

Suppose $P_{1}$ is a $\frac{n}{2}$-dimension polytope in $ R^{n}$ with barycenter $c$, and $P_{2}$ is a $(n-1)$-simplex in $R^{n}$ with the same barycenter as $P_{1}$, i.e $c$ . And also suppose they ...
shere's user avatar
  • 111
4 votes
2 answers
250 views

Build a topological polytope with a specified CW-structure

I am a topologist and not quite familiar with the tools for building a polytope. I would like to build some topological polytope which is an somewhere in between permutohedron and associahedron which ...
Prasit's user avatar
  • 2,023
3 votes
1 answer
396 views

Lattice points in cross-polytopes

Let $E\subset \mathbb{R}^n$ be a cross-polytope: $$E= \left\lbrace x : \frac{|x_1|}{q_1}+\cdots+\frac{|x_n|}{q_n}\leq 1 \right\rbrace, $$ where $q_1,\dots,q_n$ are positive integers. I am interested ...
Oleg Eroshkin's user avatar
4 votes
2 answers
567 views

Realization spaces for regular convex polytopes

Q1. Are there convex polytopes combinatorially equivalent to each of the regular polytopes that are realized with integer vertex coordinates?         &...
Joseph O'Rourke's user avatar
2 votes
2 answers
330 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. ...
Cusp's user avatar
  • 1,713
4 votes
0 answers
2k views

Regular cross-sections of a dodecahedron; analogous sections of 4-polytopes

One can intersect a dodecahedron with a plane and obtain an equilateral triangle, a square, a regular pentagon, a regular hexagon, and a regular decagon:             &...
Joseph O'Rourke's user avatar
2 votes
1 answer
194 views

Approximating Ehrhart Polynomial of Rational n-Tetrahedron

A set of positive integers $d_1, \dots, d_n$ describe a n-dimensional tetrahedron $T$ with the vertices $$ (0,\dots,0), (1/d_1,0,\dots,0), (0, 1/d_2,\dots,0), \dots, (0,\dots,1/d_n).$$ Let $L_T(t)$ be ...
Jiro's user avatar
  • 909
6 votes
1 answer
393 views

Recovering a polyhedron from its tumble-density profile

Imagine a white convex polyhedron $P$ tumbling randomly about its fixed center of gravity (c.g.) $c$ against a blue background. A long-exposure photo would show pure white in a neighborhood of $c$ (...
Joseph O'Rourke's user avatar
1 vote
1 answer
77 views

Uniqueness of polytope embedding from symmetry group

Do the symmetry group generators of a regular convex polytope and a marked $\{0,1\}^n$ vertex point suffice to embed the polytope uniquely with $\{0,1\}^n$ vertex set? If so can we find the John's ...
Turbo's user avatar
  • 13.9k
1 vote
0 answers
243 views

16-cell honeycomb (4D tiling by cross-polytopes)

A 4-dimensional cross-polytope (also called 16-cell) is a regular polytope whose vertices are all permutations of $(\pm1,0,0,0)$. It is known that this body tiles the space $\mathbb{R}^4$ by ...
aleph's user avatar
  • 503
6 votes
0 answers
434 views

Algorithm to express a point from a H-polyhedron as convex combination of extreme points

Let $P\subset\mathbb{R}^n$ be a convex polyhedron described as an intersection of hyperspaces, that is, $$P:=\{\boldsymbol{x}: A\boldsymbol{x} \leq \boldsymbol{b}\}$$ Let $\boldsymbol{x} \in P$. We ...
guigux's user avatar
  • 617
4 votes
1 answer
694 views

$\mathcal{H}$-polyhedron under a linear map

Let $P = \{ x \in \mathbb{R}^n \mid Ax \leq b \}$ be a (bounded) polyhedron for $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$, $n,m > 0$. Moreover, let $M \colon \mathbb{R}^n \to \...
Christopher's user avatar
3 votes
0 answers
219 views

First to note/document the relation between permutohedra and multiplicative inversion

The relation between the refined face numbers of the permutohedra and the formal series expansion of the reciprocal of a function (exponential generating function, formal Taylor series) is given in ...
Tom Copeland's user avatar
  • 10.5k

1
12 13
14
15 16
19