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

5
votes
1answer
334 views

Isometric embedding a convex cap to render its boundary planar

I would like to know if there is a polyhedral analog to this beautiful theorem of Hong: Theorem 11.0.1. Any smooth positive disk $(\bar{D},g)$ with a positive geodesic curvature along ...
0
votes
0answers
344 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 ...
5
votes
3answers
2k views

Random Sampling a linearly constrained region in n-dimensions…

Hi, So here is my problem: Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$ $x_n \le c_n$ and $\sum_{n=1}^N x_n = 1$ find an ...
2
votes
0answers
211 views

Sampling from a partition of a hypercube by convex polytopes.

I have a binary space partitioning (BSP) tree which recursively partitions a hypercube using linear hyperplanes. That is, a hyperplane splits the hybercube in half, creating two convex polytopes. Each ...
1
vote
2answers
437 views

Extreme points of transportation polytope

I'm interested in $n \times m$ joint probability tables with prescribed row and column marginals. Such tables form a convex set known as the transportation polytope. What are the extreme points of ...
2
votes
2answers
490 views

Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center

Does this already exist in literature? The closest Ive been able to find is circumscribe intersection of two ellipsoids with a common center by W. Kahan ...
2
votes
1answer
290 views

Angle btween Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample

Definitions Let $\mathcal{C}$ be a convex polytope in $\mathbb{R}^{D}$ with $K$-facets $F_{1},\ldots,F_{K}$. I denote the normal vector of the $k^\mathrm{th}$ facet as ...
7
votes
3answers
634 views

Not quite regular polyhedra

Take a naive interpretation of regular polyhedra: All vertices (including epsilon ball) congruent All edges congruent All faces congruent We can now find interesting families by removing one ...
9
votes
3answers
738 views

Polytopes with few vertices.

Suppose I have a convex polytope in $\mathbb{R}^d$ which I know has few vertices (in the case which prompted this question, I seem to have a polytope in $\mathbb{R}^9$ which has sixteen vertices). Is ...
5
votes
1answer
312 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$ ...
12
votes
1answer
636 views

Optimal 8-vertex isoperimetric polyhedron?

I know from Marcel Berger's Geometry Revealed: A Jacob's Ladder to Modern Higher Geometry (p.531) that it is not yet established which polyhedron in $\mathbb{R}^3$ on 8 vertices achieves the optimal ...
13
votes
2answers
698 views

Sampling from the Birkhoff polytope

The set of $n\times n$ real, nonnegative matrices whose rows and columns sum to one forms the well-known Birkhoff polytope Recently someone asked me if I knew How to sample (in polynomial time) ...
8
votes
2answers
682 views

Regular polygon shadows of convex polyhedra

Fix a finite subset $S$ of the natural numbers $\mathbb{N}$, each element $\ge 3$. Is there a convex polyhedron $P$ that has among its shadows regular $n$-gons for each $n \in S$? Does such a ...
1
vote
1answer
208 views

Representing integer points inside a polytope using a unit hypercube

Let $D\subset\mathbb{Z}\times\mathbb{Z}$ such that $D$ is formed by the points bounded by a convex polytope. Let $f:D\to\mathbb{R}$ defined by $f(x,y)=ax+by+c$, where $a,b,c\in\mathbb{R}$ and ...
14
votes
1answer
576 views

Totally rational polytopes

Define a convex polytope in $\mathbb{R}^d$ as totally rational (my terminology) if its vertex coordinates are rational, its edge lengths are rational, its two-dimensional face areas are rational, ...
3
votes
2answers
203 views

time-shifted ODEs/volume of polytopes

Hello, I'm looking for help with the following ODE: f'(t) = x f(1 - at) for 0 < a < 1, x in any interval (though 0 < x < 1 would be best), and f(0) = 1. There should be a solution for ...
3
votes
1answer
343 views

Number of simplicial polytopes with a given f-vector

Plenty of very nice literature is available on the characterization of f-vectors of simplicial complexes of diverse sorts (results by Billera, Bjoerner, Kalai, Stanley, among others). I mention, as an ...
5
votes
0answers
182 views

A polytope associated with the Hadamard Transform

In an investigation of whether or not a subset $V$ of "Hamming Space" $M_n = \mathbb{F}_2^n$ is a tile (i.e. whether $M_n$ can be written as a disjoint partition of translates of $V$) in ...
6
votes
0answers
260 views

A question about a blue fan and a red fan and their common refinement

Is the following conjecture true? Conjecture: Let $M_1$ be a red map and let $M_2$ be a blue map drawn in general position on $S^n$, and let $M$ be their common refinement. There is a vertex $w$ of ...
5
votes
0answers
393 views

Reference for this polyhedral lemma

Recall the definition of a fan: Let $U$ be a finite dimensional real vector space. Then a fan is a collection $\mathcal{F}$ of cones in $U$ such that (1) If $\sigma \in \mathcal{F}$ and $\tau$ is a ...
1
vote
0answers
156 views

Marginals and Convex Sets

I am looking for a weak convergence of marginals result, in the following type of situation. References to 'related' situations are also very much appreciated. I have a collection of affine ...
4
votes
4answers
534 views

Parametrizing the realization space of a polyhedron by its edges

I alluded to this here, but at that point I hadn't really done enough work to know what I wanted to ask. Call a polyhedron "trihedral" if three faces meet at each vertex. Each of the F faces can be ...
5
votes
2answers
418 views

A convex polyhedral analog of the pentagram map

I am wondering if there is a three-dimensional analog of the pentagram map, which maps a convex polygon to another convex polygon. Here's the Wikipedia image:           ...
4
votes
1answer
1k views

intersection of convex and non-convex polyhedra

Hi everyone, I am trying to find the best appropriate way to intersect polyhedra which may be non-convex. The number of vertices that build the polyhedron is hence always small (up to 20 or so). ...
13
votes
3answers
656 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
318 views

When is a complete fan a normal fan?

Is there a characterization for when a complete fan in $\mathbf{R}^n$ is the normal fan of a polytope? Thanks!
8
votes
1answer
737 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 ...
3
votes
0answers
188 views

Bell polytopes with nontrivial symmetries

Take $N$ parties, each of which receives an input $s_i \in {1, \dots, m_i}$ and produces an output $r_i \in {1, \dots, r_i}$, possibly in a nondeterministic manner. We are interested in joint ...
4
votes
1answer
395 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 ...
3
votes
0answers
214 views

Maximum of a function on $d-$dimensional convex compact sets

Let $\mathcal C_d$ denote the set of all $d-$dimensional convex compact subsets with barycenter at the origin of the $d$-dimensional Euclidean space $\mathbb E^d$. Given an element $C\in\mathcal C_d$ ...
12
votes
4answers
633 views

Name of a polytope

What is the name of the polytope $\Sigma\cap (-\Sigma)$ for $\Sigma$ a $d-$simplex with barycenter at the origin? In dimension $2$, one gets a hexagon, in dimension $3$ an octahedron (given by the ...
11
votes
0answers
315 views

Lower Bound on the Volume of Certain Polytopes

Given a partition $\rho\in\mathcal{P}(n)$ with $k$ blocks $$ \rho=\{B_1,B_2,\ldots,B_{k}\} $$ we can define the set of equations $$ E_{i}:\sum_{j \in B_{i}}{x_{j-1}}=\sum_{j \in ...
36
votes
4answers
2k views

Polynomial roots and convexity

A couple of years ago, I came up with the following question, to which I have no answer to this day. I have asked a few people about this, most of my teachers and some friends, but noone had ever ...
2
votes
1answer
163 views

Subspace of $\mathbb{R}^n$ spanned by the image of convex $(n-1)$-polyhedra under the face-counting map

Fix $n \in \mathbb{N}$. A convex polyhedron $C$ in $\mathbb{R}^n$ is the convex hull of finitely many points with nonempty interior. For $H$ a supporting hyperplane, ie $C$ is contained in one of the ...
16
votes
1answer
658 views

About a Delzant polytope. (In particular dodecahedron)

Hi. I have a question. Definition. Delzant polytope $P$ is a rational convex simple polytope with the smooth condition. Here, "smooth" means that for each vertex $v$, the $n$ edges containing $v$ ...
0
votes
1answer
165 views

ask for the time complexity of a convex quadratically constrained quadratic program (QCQP) problem

Could someone tell me the time complexity of a convex quadratically constrained quadratic program (QCQP) problem? And any references? Thank you very much.
8
votes
3answers
1k views

Listing lattice points in a simplex

Let $n \in \mathbf{Z}_{\geq 1}$. Is there an algorithm which, given a simplex $\Delta \subset \mathbf{R}^n$ specified as the convex hull of $v_0,\dots,v_n \in \mathbf{Z}^n$, computes the set $\Delta ...
6
votes
0answers
474 views

Counting Lattice Points in Real Polytopes

Suppose one did have an exact formula for the number of $\mathbb{Z}^n$-lattice points intersecting an arbitrary dilate of a (not necessarily rational) finite, closed and convex $n$-polytope. As a ...
2
votes
1answer
514 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 ...
7
votes
1answer
363 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 ...
9
votes
2answers
679 views

What is determined by the combinatorics of the shadows of a convex polyhedron?

Define the shadow of a convex polyhedron $P$ in direction $u$ to be the orthogonal projection of $P$ onto a plane whose normal is $u$. The shadow is a convex $k$-gon. I am wondering to what degree $P$ ...
3
votes
2answers
763 views

The space of probability measures and its intersection with hyperplanes in the space of measures

Let $X$ be some uncountable standard Borel space (e.g., the real line). Let $D$ be the set of Borel probability measures on $X$. Let $M$ be the set of signed Borel measures on $X$ Now let ...
17
votes
9answers
4k 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 ...
7
votes
1answer
477 views

Estimating the Volume of the Metric Polytope

A metric on $n$ points $N$ can be represented as a vector $x \in \mathbb{R}_+^{n \choose 2}$. For each pair of distinct $i, j \in N$, we have $d(i,j) = d(j,i) = x_{i,j}$. The set of all metrics is ...
4
votes
0answers
179 views

What's the best way to test if a sphere is a polytope? (algorithms for the Simplicial Steinitz Problem)

The problem of recognizing whether a simplicial face lattice is polytopal is sometimes called the Steinitz problem. Sturmfels and Bokowski advanced a set of methods in the late 80s to test whether ...
8
votes
2answers
328 views

Do singular values of a point set determine its shape?

Suppose I have $k$ points in $d$ dimensions. Let A be a $k\times d$ matrix with $i$th row giving the coordinates of $i$th point. Do singular values of this matrix have an interpretation as some kind ...
1
vote
1answer
143 views

stabilizer of convex cones in a linear space

Let $V$ be a finite dimensional vector space over $\mathbb{R}$, and $C\subset V$ a convex cone of the form $C=\mathbb{R}_{\geq0}v_i$ for finitely many $v_i$'s in $V$. How can one describe the ...
1
vote
1answer
178 views

Weighted Polytope

I am curious if this kind of construction (or something similar) exists: Consider a convex polytope $P$ and then consider the graph of the polytope $G(P)$ (1-skeleton). Suppose a weighting structure ...
21
votes
4answers
1k views

Ellipse naturally associated with a polygon

My colleagues and I have stumbled onto a way to associate an ellipse, or equivalently a positive definite symmetric matrix, to a polygon that is different from other better known ways. We want to know ...
42
votes
1answer
2k views

two tetrahedra in R^4

It is relatively easy to show (see below) that if we have two equilateral triangles of side 1 in $R^3$, such that their union has diameter 1, then they must share a vertex. I wonder whether we have an ...