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
4 votes
1 answer
144 views

On necessary condition for no integer points in polytope

For a convex polytope $\mathcal K$ in $\Bbb R^n$ presented by $O(n^c)$ linear inequalities is it true that for $|\mathcal K\cap \Bbb Z^n|=0$ it is necessary that at least one axis of John's ellipsoid ...
Turbo's user avatar
  • 13.7k
3 votes
1 answer
200 views

Is there a Fourier Analytic way to approximate volume?

Suppose a convex compact room in $3$-dimensions is given and source and microphones recorders are provided in the room that can locate echo timings there are works in literature which can give you the ...
Turbo's user avatar
  • 13.7k
17 votes
5 answers
858 views

Rigidity of convex polyhedrons in $\mathbb R^3$ with faces removed

Take a convex polyhedron $P$ in $\mathbb R^3$ and remove all the faces, i.e. leave only the edges. Call this graph $E$. Let us now try to continuously deform $E$ in $\mathbb R^3$ so that all the edges ...
aglearner's user avatar
  • 14k
28 votes
1 answer
1k views

Are Minkowski sums of upward closed "convex" sets in $\mathbb{N}^k$ still "convex"? (WAS: Comparing mana costs in Magic: The Gathering)

This was originally a question about comparing mana costs in Magic: The Gathering, but it's turned into a question about Minkowski sums of upward-closed convex sets in $\mathbb{N}^k$. The original ...
Harry Altman's user avatar
  • 2,535
4 votes
0 answers
218 views

Extending a Theorem of Brualdi to Matrices with Infinitely Many Rows

This question is about extending a result on transportation polytopes from Brualdi regarding $m\times n$ matrices to the case when $m=\infty$. Notation: Denote an $m\times n$ matrix by $A=[a_{i,j}]$, ...
The Substitute's user avatar
17 votes
4 answers
737 views

Volume of convex lattice polytopes with one interior lattice point

Let $P$ be a convex polytope in $\mathbb{R}^3$ whose every vertex lies in the $\mathbb{Z}^3$ lattice. Question: If $P$ contains exactly one lattice point in its interior, what is the maximum possible ...
Wlodek Kuperberg's user avatar
1 vote
0 answers
121 views

What is an umbilic point of a convex polyhedron?

An umbilic point of a smooth ($C^2$) convex surface in Euclidean 3-space is a point where the principal curvatures are equal. Is there some good way to generalize this notion to convex polyhedra? See ...
Mohammad Ghomi's user avatar
10 votes
3 answers
868 views

Approximate volume computation and lattice point enumeration - hardness

Both volume computation and lattice point enumeration of convex polyhedron are $\#P$ hard. However there is a randomized polytime algorithm for constant factor approximation for volume computation. ...
Turbo's user avatar
  • 13.7k
4 votes
1 answer
121 views

Convex caps with prescribed edges and curvature

Let $G$ be the edge graph of a convex subdivision of a convex polygon $P$ in the plane. I would like to construct a convex polyhedral cap $C$ (with zero boundary values) over $P$ whose edges project ...
Mohammad Ghomi's user avatar
6 votes
1 answer
219 views

Extend space to make polyhedra convex hulls of finite sets

A (convex) polytope is the convex hull of a finite number of points in Euclidean space (this is the so-called "vertex description"). Alternatively, it can defined to be a bounded polyhedron (this is ...
Sam Hopkins's user avatar
  • 22.7k
3 votes
1 answer
81 views

Polytopes that are just defined by ordering the variables

I am working with a polytope with a very specific structure, namely that it is characterized entirely by placing the variables, or the variables plus constants, or just constants, in a particular ...
Tom Solberg's user avatar
  • 3,929
5 votes
2 answers
290 views

Convex caps with prescribed edges

Let $P$ be a convex polygon in the plane $R^2=R^2\times \{0\}$, and $E$ be the edge graph of some subdivision of $P$ into convex polygons, which is $3$-connected. Does there exist a convex polyhedral ...
Mohammad Ghomi's user avatar
5 votes
2 answers
547 views

When are the closed convex subsets countable intersections of halfspaces

For what kind of topological vector spaces (separable maybe?) are the closed convex subsets countable intersections of halfspaces. I've seen somewhere that it's true for separable Hilbert spaces, ...
LCO's user avatar
  • 496
9 votes
1 answer
222 views

Cyclic polygons generalized to higher dimensions

Many theorems hold for cyclic polygons—convex polygons inscribed in a circle. Perhaps the most basic is this, from the reference cited below: Theorem. There exists a cyclic polygon of $n \ge ...
Joseph O'Rourke's user avatar
14 votes
0 answers
201 views

Have there been further developments on this scheme for polytope approximations to the unit ball of $\ell_p^n$?

A long time ago I happened to look at, and save (on a floppy disk!) for future reading, a copy of the following article: W. T. Gowers, Polytope approximations of the unit ball of $l^n_p$. In Convex ...
Yemon Choi's user avatar
  • 25.5k
2 votes
0 answers
536 views

On Kalai's $3^{d}$ conjecture

I just learned the existence of Gil Kalai's $3^{d}$ conjecture, which according to Wikipedia, is proven for $d$ at most $4$. It states that every $d$ dimensional polytope with central symmetry has at ...
Sylvain JULIEN's user avatar
6 votes
2 answers
350 views

Parallelotope fundamental domains of the n-torus

The group $\mathbb Z^n$ acts on the topological space $\mathbb R^n$ by translation: if $z = (z_1, \cdots, z_n) \in \mathbb Z^n$ and $x = (x_1, \cdots, x_n) \in \mathbb R^n$, then $z\cdot x := z+x$. ...
Daniel Smolkin's user avatar
4 votes
2 answers
616 views

How to know if convex-hull of a set contains zero?

Let $(\lambda_1 , \cdots , \lambda_d) \vdash k$ be a partition of $k$ of length $d$. Is there any way to decide if $0 \in \text{Conv}\{(\underbrace{\alpha_1, \cdots, \alpha_1}_{\lambda_1}, \cdots , \...
SMD's user avatar
  • 480
9 votes
1 answer
407 views

The $32$-deg polynomial for the tetrahedron inscribed in the icosahedron?

This MO answer discusses this table involving the maximal side lengths of the five Platonic solids $T,C,O,D,I$ inscribed in the other solids, This table is also found in Moritz Firsching's paper. I ...
Tito Piezas III's user avatar
7 votes
1 answer
285 views

Section of an $n$-dimensional convex polytope by $2$-dimensional plane

Consider an $n$-dimensional convex polytope with $k$ vertices. In the worst case the number of faces is exponential in $n$ and $k$. Consider a $2$-dimensional plane which intersects this polytope, i....
makkostya's user avatar
  • 415
3 votes
2 answers
291 views

Narayana polynomials as numerators of Ehrhart series rational functions?

The Narayana polynomials (OEIS A001263) are the h-polynomials of the associahedra (the Stasheff polytopes) and their dual simplicial polytopes (cf. the Fomin and Reading ref in the OEIS entry). Are ...
Tom Copeland's user avatar
  • 9,937
2 votes
0 answers
67 views

Estimate for the diameter of a facet of best-approximating polytope

Let $P$ be a convex polytope in $\Bbb R^n$ with $N$ vertices that is best-approximating for the Euclidean unit ball $B$ under the symmetric difference metric. I am trying to prove the following ...
user3816's user avatar
  • 216
8 votes
1 answer
440 views

Loday's characterization and enumeration of faces of associahedra (Stasheff polytopes)

From "The multiple facets of the associahedra" by Loday: Let us consider the formal power series $$f(x) = x+a_1 x^2 +a_2 x^3 + \cdots+ a_n x^{n+1} + \cdots$$ and let $$ g(x) = x+b_1 x^2 + ...
Tom Copeland's user avatar
  • 9,937
4 votes
0 answers
181 views

Keep doing it: generalized Catalan

One more time, let us see how else the Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$ can be generalized. First recall the generating function $$C(x):=\frac{1-\sqrt{1-4x}}x=\sum_{n\geq0}C_n\,x^n.$$ ...
T. Amdeberhan's user avatar
2 votes
1 answer
144 views

Intersection of segments in $\mathbf{R}^{k}$

Let $A$ be a set composed by an even number $n$ of distinct points in $\mathbf{R}^{k}$, such that any 3 points in $A$ are non-collinear in $\mathbf{R}^{k}$. Let us consider the set $P_{2}(A)$ of ...
Francesco Ciardiello's user avatar
1 vote
0 answers
212 views

volume of the region above a simplex in a spherical cap

Consider the $n$-dimensional unit ball $B$ centered at the origin and a hyperplane $H$ that intersects $B$. Suppose that there is a simplex $S$ inscribed in $B\cap H$, so that the vertices of $S$ lie ...
user3816's user avatar
  • 216
1 vote
1 answer
73 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.7k
4 votes
0 answers
121 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
3 votes
1 answer
285 views

Approximating John's ellipsoid from uniform sampling of a centrally symmetric convex polyhedron

A centrally symmetric convex polyhedron in $\Bbb R^n$ shifted from the origin with possibly $e^{\alpha n}$ number of vertices at some $\alpha>0$ has an unique ellipsoid of maximum volume called ...
Turbo's user avatar
  • 13.7k
4 votes
1 answer
169 views

The number of simplicial and general $d$-polytopes with $d+3$ labelled vertices

Micha Perles used Gale diagrams to compute the number of simplicial $d$-polytopes with $d+3$ vertices and of general $d$-polytopes with $d+3$ vertices. The computation can be found in Chapter 6.3 of ...
Gil Kalai's user avatar
  • 24.2k
5 votes
2 answers
311 views

Convex hull with genus information

Are there convexity generalizations that admit genus information? For example in genus $1$ is there a way to think of this polyhedron as convex while this polyhedron as non-convex? Any two points can ...
Turbo's user avatar
  • 13.7k
1 vote
1 answer
222 views

When is the second largest Gaussian r.v. the largest in the stochastic sense?

Let $X_1, \ldots, X_n$ be jointly Gaussian, each of which is marginally distributed as a standard Gaussian $N(0,1)$. It is well known that $\max |X_i|$ achieves the maximum in the stochastic sense if $...
John Wong's user avatar
  • 753
2 votes
0 answers
62 views

on vectors for which the intersection of their convex hull and the nonegative orthant is the unit simplex

Consider the vectors $r^1 = (0,2,-1)$, $r^2 = (-1,0,2)$, and $r^3 = (2,-1,0)$. Two properties of these vectors that interest us here are: 1) The $i$'th coordinate of $r^i$ is 0, and 2) The ...
Eilon's user avatar
  • 745
1 vote
0 answers
92 views

quick hull algorithm detail

When using quick hull algorithm to find the polytope for half space intersection, we are required to provide an interior point to the solver qhalf. In other words, providing $$Ax \le b$$ is not ...
user40780's user avatar
  • 867
3 votes
1 answer
155 views

Cyclic polytopes whose boundary is a flag complex

A cyclic polytope $C(n, d)$ is defined as the convex hull of $n$ distinct points on the moment curve in $\mathbb{R}^d$ (here $n>d$). This is a simplicial polytope so its boundary $\partial C(n, d)$ ...
Priyavrat Deshpande's user avatar
0 votes
1 answer
76 views

algorithms and tools available for a particular polytope computation

Let me define each half space i as: $${H_i}:{c_i}{\bf{x}} \le {b_i}$$ The intersection of all such ${H_i}$ gives a polyhedron (bounded or not). Suppose I am interested in if ${H_i}$ is active (...
user40780's user avatar
  • 867
2 votes
0 answers
76 views

An inequality about the volume of convex body

For a subset $S$ of $\mathbb{R}^n$, we denote by $\lambda S$ the dilation for any $\lambda \in \mathbb{R}$: $$\lambda S=\{\lambda x| x\in S\}.$$ Let $\Omega$ be a convex body in $\mathbb{R}^n$ with $...
Feng Wang's user avatar
  • 179
0 votes
1 answer
28 views

Finding a point at which only certain linear functionals are integral

Let $C$ be a full-dimensional rational polyhedral cone in $\Bbb R^d$ with facets $G_1,\ldots,G_n$ . For each $i$, let $h_i$ be an integer-valued linear functional on $\Bbb R^d$ whose kernel is the ...
Avi Steiner's user avatar
  • 3,031
6 votes
0 answers
188 views

Cut locus on a hypercube

Inspired by the question, "Shortest path connecting two opposite points on a cube": Q. What does the cut locus with respect to one corner of a hypercube in $\mathbb{R}^d$ look like? "The cut ...
Joseph O'Rourke's user avatar
4 votes
1 answer
567 views

The geometric explanation of **isotropic position**

A convex body $K$ in $\mathbb{R}^n$ is in isotropic position if, for all vectors $x \in \mathbb{R}^n$, we have $$\frac{1}{\mathrm{vol}(K)}\int_K \langle x, y \rangle^2 dy = \|x\|^2.$$ My question: ...
Epsilon's user avatar
  • 49
4 votes
0 answers
80 views

Polynomial approximations on the Boolean hypercube

Given $\vec{a} \in \mathbb{R}^n$ and $b \in \mathbb{R}$ consider the function $f(x) = Th[\vec{a}.\vec{x}+b]$ on $x \in \{-1,1\}^n$ such that the ``threshold function (Th)" gives $1$ when the argument ...
gradstudent's user avatar
  • 2,136
1 vote
0 answers
353 views

About hyperplanes cutting the discrete hypercube

Given $\{-1,1\}^n$ we randomly choose a hyperplane in $\mathbb{R}^n$. Now given an integer $p \in [1,n]$ and a number $\epsilon \in [0,1]$, I want to ask, "How likely is it that at least one of the $p-...
gradstudent's user avatar
  • 2,136
5 votes
0 answers
219 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
0 votes
1 answer
79 views

Can convex combinations of indicator functions for pairwise non-disjoint sets unordered by inclusion dominate one another?

Let $N$ be a finite subset of the naturals. Let $P$ be a set of subsets of $N$ such that: 1) $P\neq \varnothing$, 2) $\forall x\in P, |x| >1$, 3) $\forall x,y\in P,$ if $x\neq y$, then $x\not\...
VMfoobar's user avatar
0 votes
2 answers
304 views

Lattice question

Consider a lattice $\mathcal{L} = \mathbb{Z}v_1 \oplus \ldots \oplus \mathbb{Z}v_l$ in $\mathbb{R}^n$ and let $S_0$ be the set of edges of the fundamental unit of $\mathcal{L}$. We call a region $X$ ...
Alex's user avatar
  • 491
1 vote
0 answers
61 views

Sampling in a polyhedral complex

Assume one is given a polyhedral complex $P$ in $\mathbb{R}^n$. Now consider picking uniformly at random a $D \subseteq \{0,1\}^n$. Is there way to upper bound the probability that $D$ (a subset of ...
gradstudent's user avatar
  • 2,136
2 votes
0 answers
162 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
  • 9,937
15 votes
3 answers
988 views

Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?

Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets. Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$. Can $\text{Proj}(P)$ have more than $f$ facets? ...
Pedro Ruiz's user avatar
54 votes
5 answers
2k views

Unusual symmetries of the Cayley-Menger determinant for the volume of tetrahedra

Suppose you have a tetrahedron $T$ in Euclidean space with edge lengths $\ell_{01}$, $\ell_{02}$, $\ell_{03}$, $\ell_{12}$, $\ell_{13}$, and $\ell_{23}$. Now consider the tetrahedron $T'$ with edge ...
Dylan Thurston's user avatar
5 votes
0 answers
128 views

Lattice paths in polytopes

Let $P$ be a polytope in $\mathbb{R}^n$. Let $A_ix = b_i$ be the defining equations of its codimension $1$ faces. Is there an algorithm or some kind of criterion to decide if the lattice points inside ...
Alex's user avatar
  • 491

1
7 8
9
10 11
19