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
942 questions
1
vote
0
answers
107
views
Stronger condition than being a normal polytope?
A polytope $P$ with integer vertices is called normal if
for every $p = \sum_j a_j p_j $ such that $a_j \geq 0$, $\sum_j a_j = k \in \mathbb{N}$,
$p_j$ are vertices of $P$ and $p$ is an integer ...
- 15.8k
1
vote
0
answers
50
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 $\operatorname{...
- 773
1
vote
0
answers
193
views
Lattice-point enumeration question involving linear combinations of matrices
I would like to know some references to learn more about an answer to this question, if there are any references:
Let $A_1, \dots , A_m$ and $B$ be $n\times n$ symmetric matrices. Let $$S = \{(x_1, \...
- 170
1
vote
1
answer
288
views
Realizing not-quite-barycentric subdivision of a polytope
Given a poset $S$, one can form a new poset $I(S)$ whose elements are intervals in $S$ (i.e. either $\emptyset$ or $[a,b]$ for some $a\leq b\in S$) with ordering by (set) inclusion. If $S$ is ranked, ...
- 3,093
9
votes
0
answers
738
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
1
answer
79
views
The minimal number of halfspaces to represent a convex but non strongly convex cone
We say a cone at the origin in $R^n$ means that it is an intersection of finitely many halfspaces, i.e.
$$C=\bigcap_{i\in I}H_i,\text{ where }|I|<\infty.$$
A cone is strongly convex if $C\cap -C=\...
- 301
1
vote
0
answers
94
views
Does the set of points minimizing their distance to a multiset of convex polytopes result in a polytope?
Let $\mathbb{R}^n$ be a normed affine space of finite dimension $n$, and $d : \mathbb{R}^n \times \mathbb{R}^n \mapsto \mathbb{R}^+$ be the distance derived from the norm under consideration. A convex ...
- 125
3
votes
0
answers
76
views
Minimax-like theorems involving union and intersection of regions in $\mathbb R^d$
From Minimax theorems, we roughly know that if $f(x,y)$ is convex on $X$ and concave $Y$ for both compact $X,Y$, then:
$$
\max_{x\in X}\min_{y\in Y} f(x,y)=\min_{y\in Y}\max_{x\in X} f(x,y).
$$
We can ...
- 752
13
votes
0
answers
1k
views
Constructive aspects of Caratheodory's theorem in convex analysis
Let me paraphrase Caratheodory's theorem in a probabilistic setup:
Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such ...
- 1,839
3
votes
0
answers
68
views
Polynomials connected with Gale's condition and cyclic polytopes
I was reading about cyclic polytopes and (I think naturally) became interested in polynomials $f(X) \in \mathbb{R}[X]$ which have a factorization of the form $f(X)=g(X)g(X+1)$ for some $g(X) \in \...
- 1,081
5
votes
0
answers
503
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 ...
- 156k
1
vote
0
answers
450
views
When is the conical hull of a finite set of vectors a subset of the space? (and tilings)
Consider a hypercube in n-dimensions, and take some projection down to an m-dimensional subspace. Now take all vertices and m-1 dimensional facets visible from some direction outside the projection. ...
- 1,314
0
votes
0
answers
66
views
construction of four dimensional regular convex polytopes
Could anybody give me a reference book about the explicit construction of the 6 regular four dimensional convex polytopes. I cannot easily find Schläfli's original paper so I am looking for a modern ...
- 311
2
votes
1
answer
216
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 ...
- 1,063
8
votes
1
answer
236
views
Finding a point that lies in a majority of polytopes
Suppose I have $k$ $n$-dimensional polytopes $P_1,\ldots,P_k$, each explicitly specified as the intersection of a collection of hyperplanes. If there was a point $p \in \mathbb{R}^n$ that lay in the ...
- 794
3
votes
3
answers
311
views
Are there infinite sets of stellations of polyhedra?
Lists of stellations of polyhedrons are given particular rules like in the book The Fifty Nine Icosahedra which follows "Miller's Rules".
There seems to be no "correct" ruleset to use, so more ...
- 2,615
2
votes
0
answers
112
views
Optimization over a variable domain defined as a convex hull of given points [closed]
I have an optimization problem:
$\max_{\bf{x}} Z(\bf{x})$,
s.t. $\bf{x} \in conv(\bf{S})$
where $\bf{x}$ is an $n$-dimensional vector, $Z(\bf{x})$ is a non-linear function. The domain of $\bf{x}$ ...
- 29
1
vote
0
answers
185
views
Compute generalized pentagram map
Hi,
(This is my first question on MathOverflow! :-)
Imagine you have a set of points $S = \{p_1, \ldots, p_n\}$ in $\mathbb{R}^d$, of which $t$ are "bad". I want to compute a "safe convex hull", ...
- 11
0
votes
0
answers
63
views
Paths on Cartesian products of graphs satisfying linear constraints
Assume integers $d > r > 0$ and a connected graph $G$ with $d$ vertices. Every point on the $r$-fold Cartesian product of $G$ with itself, $G^{\square r}$, is equivalent to a dimension-$d$ non-...
- 1
3
votes
0
answers
242
views
Place n telescopes on a sphere in R^d to see the whole sky
Where would one put $n$ telescopes on the surface of the earth
to see the whole sky as well as possible ?
Use the cosine metric to define how well we can see in direction $x$:
$ \qquad \text{cansee}( ...
- 265
3
votes
0
answers
335
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 ...
- 31
1
vote
1
answer
277
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 $g:D\to\...
- 1,638
7
votes
0
answers
370
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 $...
- 24.7k
3
votes
1
answer
255
views
Can any vertex remain when removing halfspaces from a projectively transformed polytope?
Let P be a simple polytope defined as an intersection of n halfspaces.
A facet F of P, supported by halfspace H, is removable if the intersection of the remaining (n-1) halfspaces is bounded. F is ...
- 275
7
votes
0
answers
649
views
When should a moment polytope have "smooth" faces?
A codimension $d$ face of a polytope is called rationally smooth if it lies on only $d$ facets, because this is exactly the condition for the corresponding toric variety to have only orbifold ...
- 27.8k
3
votes
1
answer
375
views
Connections between a polytope's symmetry group and the existence of periodic orbits
Given an $n$-dimensional convex polytope $P$, one may set into motion a point-mass, starting on one of the facets of $P$, which travels along a straight trajectory inside $P$ except on collision with ...
- 269
11
votes
0
answers
366
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 B_{i}}{x_j}\quad\text{...
- 3,626
2
votes
1
answer
257
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 ...
- 475
0
votes
0
answers
155
views
Area of spherical polygons in high dimensions
Given 4 points on $S^3$. If we look at the spherical polygon formed on $S^3$, is there a formula for the 3-dimensional Hausdorff measure for it?
E.g.: When I tried to set up a spherical coordinate ...
- 113
3
votes
0
answers
280
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 ...
- 3,323
2
votes
1
answer
172
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,305
1
vote
1
answer
419
views
Is the direction of the longest line of a polytope unique?
The question pertains to a polytope that is generated by the intersection of an affine subspace with a hypercube in $p$ dimensions.
The affine subspace is given by:
$X \mbox{ u} = y$
where
$u$ &...
- 121
3
votes
1
answer
354
views
"Threaded" Truncated Icosahedon
Please have a look at
http://www.cijoint.fr/cjlink.php?file=cj201006/cijHr27640.jpg
the object in question is a truncated icosahedon whose sides are pearls.
It is an interesting little bauble ...
- 39
5
votes
0
answers
204
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 http://arxiv....
- 4,636
3
votes
0
answers
234
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$ ...
- 17.9k
5
votes
0
answers
104
views
Regularity of simplices, part deux
This question is directly inspired by Pietro Majer's question and my answer to it.
One can define a simplex, and the dihedral angles thereof in an infinite dimensional Hilbert space (one has to take ...
- 96.4k
4
votes
1
answer
363
views
Efficiently sampling points from an integer lattice.
Let $\mathcal{L}$ = {x$\in$ $N^n$ : ||x||$_1$ $\leq$ m} denote the set of integer points in the positive orthant of the $\ell_1$ ball of radius $m$, where $m < n$. For each $x \in \mathcal{L}$, let ...
- 41
3
votes
0
answers
102
views
Versions of Helly's Theorem for Unbounded Parallelpipeds
I'm studying Frobenius splitting of toric varieties based on Sam Payne's characterization of Frobenius splitting ("Frobenius splittings of toric varieties" (2008)) and I came across a sort of Helly's ...
- 31
1
vote
0
answers
169
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 ...
- 105
2
votes
0
answers
51
views
Conditions under which a set of points have a low weight representation under some basis
Let $S \subset R^d$ be a convex polytope in $d$ dimensional real space. Say that $S$ has weight $w$ if there exists some basis $x_1,\ldots,x_d$ such that for every point $v \in S$, we can write $v = \...
- 794
3
votes
1
answer
199
views
Edge-maximizing projective transformation on polytopes
Let P and Q be simple polytopes such that P = Q ∩ H and let H be a halfspace with normal vector n. Let projn(e) denote the length of the projection of edge e onto vector n.
Consider the set E of ...
- 275
3
votes
0
answers
173
views
Collapsing the medial axis of a polytope
Let X be a convex polyhedron in hyperbolic 3-space.
Let M be the medial axis of X.
Question: Is M collapsible?
It is easy to see that M is contractable.
In the case of Euclidian 3-space, instead ...
- 133