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
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?
user6976
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
6
votes
1
answer
715
views
Elementary problem about triangles inside a convex polygon
Let P be a convex polygon with area A(P), and to each side of P, attach the largest area triangle possible that lies entirely within P. Must the sum S(P) of the areas of these triangles always satisfy ...
- 1,318
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
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
16
votes
5
answers
1k
views
A characterization of convexity
While doing some research on polytopes I came to the following question. Maybe it's already somewhere but anyway I'll post it here.
Let $X\subset \mathbb{R}^3$ be such that, for every plane $P$, $P\...
- 1,001
5
votes
2
answers
879
views
Intersection homology for toric varieties
is there any algorithm known for computing (middle perversity)intersection homology of complex toric varieties based on their combinatorial data? I'm not looking for a computer program.
Regards,
...
- 93
5
votes
2
answers
475
views
Making 'circles' on a lattice/ Making distinct fractions from partitions of a number
First formulation: discrete geometry
Pick your favourite 2D square lattice (I'm sure we all have one...) and try to place n points 'in a circle' (that is: in general position [no 3 should be colinear] ...
- 3,230
4
votes
4
answers
594
views
Upper bound for the number of subsets of N points which exhaust their convex hull
Hello.
Looking at a set S of N points in the plane, I call a subset B of S "legal" if the set of points contained in the convex hull of B is exactly B itself. In other words, a subset B of S in legal ...
uuu
13
votes
3
answers
1k
views
When are Ehrhart functions of compact convex sets polynomials?
Given a lattice $L$ and a subset $P\subset \mathbb R^d$, we define for each positive integer $t$ $$f_P(L,t)=|(tP\cap L)|$$ the number of lattice points in $tP$. Let's say $P$ is nice if $f_P(L,t)$ is ...
- 85.6k
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
1
answer
865
views
A Counterexample to the HIrsch Conjecture
Recently Francisco Santos has announced that he has a counterexample to the Hirsch conjecture. The last I heard it was circulating among several people and there would be a public version of it ...
- 6,523
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
6
votes
5
answers
2k
views
How to prove that a set of facets are all the facets of a convex polytope.
Say that you know all the vertices of a polytope P, and a set of facet defining hyperplanes that you guess give all the facets of P. What are some good ways to try to prove that the guess is right?
A ...
- 614
8
votes
1
answer
556
views
A variation on "Hearing the shape of a drum" for polytopes.
Let $\varphi:\mathcal S^{d-1}\longrightarrow \mathbb R_{>0}$ be a strictly positive function describing the boundary $\varphi(\mathbf x)\mathbf x,\mathbf x\in\mathbb S^{d-1}$ of a $d-$dimensional ...
- 17.9k
19
votes
3
answers
2k
views
Cutting convex sets
Any bounded convex set of the Euclidean plane can be cut into two convex pieces of equal area and circumference.
Can one cut every bounded convex set of the Euclidean plane into an arbitrary number $...
- 17.9k
8
votes
3
answers
1k
views
Area of cross-section (at midpoint perpendicular to longest diagonal) in the unit cube of dimension N
Take a unit cube (of side 1) in N dimensions. Construct the cross-section at the midpoint of the longest diagonal. What is the area of this N-1 dimensional region? I can compute this, but it would be ...
- 81
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
34
votes
2
answers
2k
views
Do plane projections determine a convex polytope?
Suppose a compact convex body $P \subset \Bbb R^3$ has only polygonal orthogonal projections onto a plane. Does this imply that $P$ is a convex polytope?
This question occurred to me when I was ...
- 17k
6
votes
2
answers
659
views
How many vertices of a polytope can be chopped off to produce a k-vertex facet?
Let P be a simple n-facet d-polytope with facet F, and let F have k vertices. Let H be a halfspace and Q be a simple (n-1)-facet polytope such that H ∩ Q = P.
In terms of k, what is an upper ...
- 275
0
votes
2
answers
2k
views
Finding a bounding volume (line segments) from a kDop definition.
I have a problem.
I'm trying to recover a bounding volume (actually line segments that form the bounding volume) from a kDop definition (in a 3D space). (its to draw the kDop on screen)
In my kDOP ...
- 3
12
votes
1
answer
651
views
Does a triangulation without fixed simplex property always exist?
Suppose we are given a triangulable topological space $X$. If $X$ has the fixed point property (FPP), then obviously for every triangulation $K$ of $X$ and every simplicial map $f:K\to K$ a simplex $\...
- 2,104
8
votes
2
answers
217
views
Flipping Hilbert series of semigroup rings
I'll first give intuition, and then give a precise statement.
For $|z|<1$, we have $\sum_{i \geq 0} z^i = 1/(1-z)$. For $|z|>1$, we have $\sum_{i<0} (-1) z^i=1/(1-z)$. Thus, the two ...
- 156k
0
votes
2
answers
611
views
2
votes
2
answers
2k
views
Mathematical tools appropriate to analyse convex polyhedra
What mathematical tools (means: set of areas of mathematical knowledge) are appropriate to begin with to analyse (to enumerate face vectors associated with polyhedron, to calculate the combinatorial ...
7
votes
2
answers
1k
views
Maximal Ellipsoid
John's Theorem can be stated as "To every compact, convex body, there is a unique inscribed ellipsoid, whose volume is maximal among all inscribed ellipsoids." It goes on to classify this maximal ...
- 1,588
12
votes
6
answers
1k
views
Database of polyhedra
As part of many hobbies (origami, sculpting, construction toys) I often find myself building polyhedra from regular polygons. I am intimately familiar with all of the Archimedean and Platonic solids, ...
- 241
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
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
11
votes
1
answer
2k
views
Characterizing faces of 3-dimensional polyhedra. (Related to Victor Eberhard's Theorem [1890]:)
Originally asked by Ali Dino Jumani; EXTENSIVELY EDITED by David Speyer. The previous version was a bit confused, but Steven Sivek and Graham, in the comments, figured out what was going on.
G. C. ...
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
26
votes
7
answers
10k
views
Uniformly Sampling from Convex Polytopes
How to choose a point uniformly from a convex polytope $P \subset [0,1]^n$ defined by some inequalities, $Ax < b$? (Here $A$ is an $m \times n$ matrix, $x \in \mathbb{R}^n$, and $b \in \mathbb{R}^...
- 22.8k
8
votes
6
answers
1k
views
Combinatorial distance ≡ Euclidean distance
Definition: A polytope has property X iff there is a function f:N+ → R+ such that for each pair of vertices vi, vj the following holds:
disteuclidean(vi, vj) = f(distcombinatorial(vi, vj))
with ...
- 9,720
22
votes
4
answers
3k
views
Can you determine whether a graph is the 1-skeleton of a polytope?
How do I test whether a given undirected graph is the 1-skeleton of a polytope?
How can I tell the dimension of a given 1-skeleton?
- 9,720
3
votes
1
answer
439
views
Convex n-polytope general position vectors to general position vectors of tetrahedron
I asked this question in a comment to this question, but got no response. I thought that perhaps it needed more exposure, so I made it a question in itself.
Define a set of general position vectors $...
- 4,842
4
votes
2
answers
3k
views
Break polyhedron into tetrahedron
Given a polyhedron consists of a list of vertices (v), a list of edges (e), and a list of surfaces connecting those edges (...
- 381
18
votes
1
answer
644
views
Egalitarian measures
A question I got asked I while ago:
If $T$ is a triangle in $\mathbb R^2$, is there a function $f:T\to\mathbb R$ such that the integral of $f$ over each straight segment connecting two points in the ...
- 47.3k
34
votes
16
answers
7k
views
Generalizations of the Birkhoff-von Neumann Theorem
The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices.
The question is to point out different ...
- 24.7k
7
votes
2
answers
846
views
What is known about polyhedra nets that allow overlapping?
It is an open problem that the net of any convex polyhedron can be unfolded onto a flat plane with no overlapping. Is anything known if we allow x faces to overlap? For example, is it known if any ...
- 2,615
13
votes
2
answers
2k
views
Combinatorics of the Stasheff polytopes
First a little background for those unaware. The Stasheff polytopes (or associahedra) are certain convex polytopes that arise in the theory of $A_\infty$-algebras. There is one polytope for each $n\...
- 3,423
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
44
votes
11
answers
26k
views
Algorithm for finding the volume of a convex polytope
It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...
- 441