All Questions
1,385 questions
1
vote
0
answers
28
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
-1
votes
0
answers
41
views
Is it possible to backtrack an optimization solver? [closed]
I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
1
vote
0
answers
122
views
Growth polynomial of the Associahedron graph ? (Is it approximately Gaussian ?)
Consider Associahedron, consider graph build from its vertices and edges. Choose some vertex. Let us count the number of vertices on distances $k$ from the selected vertex. Write a generating ...
- 24.8k
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
0
votes
0
answers
26
views
How to calculate the vertices of a convex polytope (k-DOP)
I am currently reading Christer Ericson's Real-Time Collision Detection Book. The topic I'm particularly interested in, is the chapter about Discrete-orientation Polytopes (k-DOPs). In his words "...
- 1
8
votes
0
answers
281
views
Meaning of the Ehrhart polynomial at $-1/2$?
I am studying a large collection of lattice polytopes, all of them being simple and empty. The dimension can be any integer. The dilatation by $2$ gives non-empty polytopes.
For many of these ...
- 3,587
1
vote
0
answers
56
views
Tiling with one of each 3D shape
Encouraged by the positive solutions to my question,
Tiling with one of each shape,
I'd like to pose the $\mathbb{R}^3$ equivalent:
Q. Is there a tiling of $\mathbb{R}^3$ by (bounded) polyhedra, one ...
- 151k
9
votes
0
answers
143
views
Which polytopes have compact realization spaces?
Let $P\subset\Bbb R^d$ be a convex polytope.
Its reduced realization space is the space of all combinatorially equivalent polytopes modulo projective transformations.
I am interested in polytopes for ...
- 13.6k
7
votes
2
answers
242
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
0
votes
0
answers
44
views
Lattice points in the boundary of a Minkowski sum of two convex lattice polygons
Let $P$ and $Q$ be two convex lattice polygons in $\mathbb{R}_+^2$ and let $P+Q$ be their Minkowski sum. Given a set $S \subset \mathbb{R}^2$, we let $L(S) =\#( S \bigcap \mathbb{Z}^2)$.
The equality $...
- 183
0
votes
0
answers
36
views
Constructing a minimum-volume outer approximation polytope with fewer facets
I am tackling the following problem:
Given a set of points $D \in \mathbb{R}^d$ and their convex hull, represented with $n$ facets, I want to construct a convex polytope $P$ with at most $m<n$ ...
- 101
6
votes
1
answer
346
views
Is a ball the hardest body to approximate by polytopes (in the Banach–Mazur metric)?
$\DeclareMathOperator\conv{conv}\DeclareMathOperator\Vol{Vol}$In the paper "An extremal property of the hypersphere" by Macbeath, the following functionals were introduced (here $n$ is fixed,...
- 93
1
vote
0
answers
72
views
Existence of a sequence of $-1/1$-polytopes with certain geometric properties
Let $P_n \subset \mathbb{R}^n$ be a sequence of polytopes (A polytope is the convex hull of finitely many points). Let $B_n \subset \mathbb{R}^{n}$ denote the Euclidean unit ball. I am interested in ...
- 93
3
votes
1
answer
239
views
A palindromic formula for simple convex polytopes
Let $P$ be a simple convex $d$-polytope (a $d$-dimensional convex polytope in which the number of edges incident to a vertex is $d$) and let $n_i$ be the number of $i$-faces of $P$. Is it true that ...
- 161
2
votes
4
answers
212
views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 157
1
vote
0
answers
99
views
Shortest loop through vertices of a convex polytope
Let $P$ be a convex polytope in Euclidean space $\mathbf{R}^3$ and $\Gamma$ be a closed curve which passes through all vertices of $P$. How small can the length $L$ of $\Gamma$ be? More specifically, ...
- 7,149
1
vote
1
answer
106
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 13
0
votes
0
answers
69
views
Degree of reflectional symmetry of (unbounded) convex polyhedra in Euclidean spaces
Let $U \subset \mathbb{R}^m$ be an open domain. I'm trying to come up with a measure of its degree of reflectional symmetry and I have a question. The post in two-part, where in PART I I introduce the ...
- 1,465
0
votes
0
answers
81
views
A generalized permutohedron as the sum of the dilatations of the faces of the standard simplex
I am trying to understand the proof of the statement, specifically it refers to a theorem stated by Postnikov in his text on permutohedra. So, this sentence claims the following:
If $\{Y_I \}$ is a ...
- 251
2
votes
1
answer
147
views
Are there polytopes with precisely two realizations?
A convex polytope is projectively unique if it has a unique realization up to projective transformations. Such polytopes are somewhat mysterious but still well-studied. Examples are simplices, the ...
- 13.6k
1
vote
1
answer
197
views
Description of the generalized permutahedron
According to Postnikov, we know that the generalized permutahedron are describe as "polytopes obtained by moving vertices of the usual permutohedron so that directions of all edges are preserved&...
- 251
1
vote
0
answers
41
views
Is there any software package to find the vertices of convex polytope where the inequality constraints are bounded by variable?
I know of this package lcon2vert that computes vertices from given inequality and equality constraints describing a bounded polyhedron. Here the bounds of constraints only accept numerical values, i.e....
0
votes
0
answers
51
views
Minimizer of forward and reverse Kullback-Leibler divergence with sum constraints on marginals
Consider minimization of the Kullback Leibler divergence between two discrete distributions $p$ and $q$:
\begin{align*}
D_{KL} \left( p \parallel q \right) = \sum_i p_i \log \left( \frac{p_i}{q_i} \...
0
votes
0
answers
48
views
A question on a quantitative form of Farkas' lemma
Suppose A is an $m \times n$ matrix whose entries are non-negative integers and $\mathbf{b}$ is a vector with rational entries. A version of Farkas lemma implies that if the equation $$A\mathbf{x}=\...
- 6,214
0
votes
0
answers
31
views
Group or semi-ring on polytope family
I want to determine how to provide structure to the polytope family; I guess the main article where this is discussed is the one by Peter Mcmullen entitled “The polytope Algebra”, here they talk about ...
- 251
2
votes
0
answers
318
views
What's the number of facets of a $d$-dimensional cyclic polytope?
A face of a convex polytope $P$ is defined as
$P$ itself, or
a subset of $P$ of the form $P\cap h$, where $h$ is a hyperplane such that $P$ is fully contained in one of the closed half-spaces ...
- 43
1
vote
0
answers
99
views
Minimum of the maximum element frequency given the family size and the universe size
[Crossposted at math.stackexchange].
Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$.
I have written and solved ...
- 988
2
votes
0
answers
83
views
Is the volume of the image of the moment map an invariant of a symplectic toric manifold?
Given a symplectic toric manifold is known that the image of the moment map is a Delzant polytope that fully characterises the manifold. What about the volume of the polytope? Is it possible that two ...
0
votes
0
answers
115
views
Software for computing polytopes
As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
- 1
0
votes
0
answers
72
views
Probability of being inside a convex n-dimensional polytop
I am currently conducting some post-grad research about wireless transmissions with uncertain transmission delays.
As part of the research, each individual transmission is modelled using a probability ...
0
votes
0
answers
52
views
Polyhedra volume, faces and edges from vertices
Given a set of vertices in 3D corresponding to a convex polyhedron, what is the most efficient way to find its volume, faces, and edges?
I've found some techniques using convex hulls. But I think I ...
- 101
5
votes
1
answer
176
views
Efficient counting of integer solutions to linear system
In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in ...
- 151
10
votes
2
answers
254
views
Is the face lattice of the cube a polytope graph?
The face lattice of a
convex polytope $P\subset\Bbb R^d$ is the partially ordered set whose elements are the faces of $P$ ordered by inclusion. We can turn it into a graph by considering its Hasse ...
- 13.6k
3
votes
1
answer
239
views
The realization space of non-convex polyhedra - What is known?
The space $\mathfrak R_{\mathrm c}(P)$ of convex realizations of a (3-dimensional, spherical) polyhedron $P$ is known to be well-behaved: it is a contractible manifold of dimension $\#\text{edges}+6$ (...
- 13.6k
1
vote
1
answer
115
views
Alexandrov's uniqueness theorem in Minkowski spacetime
Suppose $P$ is a convex polyhedron in $\mathbb{R}^{2,1}$.
Each face of $P$ comes with induced metric tensor,
if the face is space-like, then it is euclidean metric;
every time-like face is isometric ...
- 45k
0
votes
1
answer
133
views
Centroid of Minkowski sum
Let $A$ and $B$ be two compact convex subsets of $\mathbb{R}^n, n\geq 2$. Assume $x_A$ and $x_B$ are their respective centroid. If we form the Minkowski sum $C=A+B = \{x+y\mid x\in A, y\in B\}$, what ...
- 161
4
votes
0
answers
46
views
Implementation of Friedman's algorithm of reconstructing simple polytopes
In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
0
votes
1
answer
103
views
Convex sets via fixed point equations
I have an equation of the general form
$$ X = S \cup T X $$
where $S \subset \mathbb R^n$ is a convex polytope (given by its bounding hyperplanes), $T\colon \mathbb R^n \to \mathbb R^n$ is a linear ...
- 857
1
vote
0
answers
40
views
Polyhedra inscribed in a sphere with mutually non-congruent, equal area faces
Two constrained versions of the main question given in this post: Polyhedrons with mutually non-congruent faces, all of equal area. An earlier post that could be related: Cutting a spherical surface ...
- 5,979
1
vote
0
answers
114
views
Homeomorphism between interiors of simplex and permutohedron
The $n$-dimensional permutohedron $P_n$ is a polytope whose facets (i.e.\ codimension $1$ faces) are in 1-to-1 correspondence with all faces (of codimension${}\geq 1$) of the $n$-simplex $\Delta_n$, ...
- 1,804
13
votes
0
answers
378
views
Is a convex polyhedron determined by its edge lengths and angular defects?
Let's consider 3-dimensional convex polyhedra $P\subset\Bbb R^3$.
The angular defect at a vertex $v$ is $2\pi$ minus the sum of the interior angles of the incident faces at $v$.
Question:
Is a ...
- 13.6k
0
votes
0
answers
78
views
Using Ehrhart polynomials to count primes?
As indicated below, one could use the Ehrhart polynomials of the simplex in number theory.
Here are the questions without context first:
Questions:
The sum $$\sum_{k=0}^t (-1)^k ( \operatorname{...
- 3,054
7
votes
3
answers
703
views
A continuous version of Carathéodory's convex hull theorem
A well-known theorem of Caratheodory states that any point in the convex hull of a set $X\subset R^n$ lies in the convex hull of at most $n+1$ points of $X$. I am wondering about a version of this ...
- 7,149
0
votes
0
answers
39
views
Max-flow modeling with unified vehicle and commodity variables
I am working on a network flow problem that involves routing through a time-space network. The network consists of:
A single source node and a single demand node.
A fleet of vehicles with specified ...
- 101
0
votes
0
answers
30
views
Application of greedy approach for optimization
I want to maximize an objective given by $$\max_{\{q_n,p_n\}} \sum_{n=0}^\infty (\alpha_1 - \beta_1 n) p_n + (\alpha_2 - \beta_2 n) q_n$$
where $\alpha_1 > \beta_1 >0$ and $\alpha_2 > \beta_2 ...
- 23
3
votes
0
answers
110
views
Sampling uniformly from the convex cone
Let $n$ vectors of dimension $d$ (e.g., $n = 100$, $d = 10000$), each with infinity norm of $1$, be given. The conic combination of those $n$ vectors generates a convex cone.
How to uniformly sample ...
- 31
2
votes
0
answers
64
views
Eulerian polynomial from Bruhat interval - h* of something?
Let $\sigma \in S_n$ be a fixed permutation.
Consider the polynomial
$$
P_{\sigma}(t) = \sum_{\substack{\pi \in S_n \\ \pi \leq \sigma}} t^{\textrm{des}(\pi)}
$$
where $\leq$ denotes Bruhat order, and ...
- 15.8k
6
votes
0
answers
199
views
Zero-one pairings between sets of vectors
Let
$A\subseteq V$ and
$B\subseteq V^\star$
be spanning sets in
a finite-dimensional real vector space $V$ and
its dual $V^\star$.
Suppose that
$$
\langle b,a\rangle\in\lbrace0,1\rbrace
$$
for all
$a\...
- 809
2
votes
1
answer
213
views
Is matrix B obtained from matrix A?
Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
- 49
0
votes
0
answers
36
views
ILPs with square constraint matrix
Given the Integer Linear Programming ($\text{ILP}$) problem
\begin{array}{ll}
\text{minimize} & c^T x \\
\text{subject to}& \mathbf{A}^T x \ge b \\
\text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
- 13.2k