All Questions
56 questions
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
25
votes
4
answers
1k
views
Do random projections (approximately) preserve convexity?
The Johnson-Lindenstrauss lemma implies that any set of $k$ points in $\mathbb{R}^d$ can be randomly projected into $d' \approx \log(k)/\epsilon^2$ dimensions such that the distances between each pair ...
- 253
21
votes
5
answers
1k
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 ...
- 151k
20
votes
4
answers
950
views
The limit of edge-midpoint convex polyhedra
Starting with a convex polyhedron $P_1 \subset \mathbb{R}^3$,
replace that with $P_2$, the convex hull of the midpoints of the edges of $P_1$.
Continuing this process, we obtain a ...
- 151k
20
votes
0
answers
433
views
Is the dodecahedron flexible (as a polytope with fixed edge-lengths)?
Consider the (regular) dodecahedron $D\subset\Bbb R^3$. I want to continuously deform it so that throughout the deformation
it stays a convex polytope,
it stays a combinatorial dodecahedron (i.e. its ...
- 13.6k
18
votes
3
answers
2k
views
Are the Platonic solids shadows of 4-polytopes?
Say that a 3D shadow of a 4-polytope is a parallel projection to 3-space, not necessarily orthogonal to that 3-space (that would make it an orthogonal projection).
I am wondering if each of the five ...
- 151k
17
votes
3
answers
2k
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 ...
- 151k
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
14
votes
0
answers
479
views
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?
After reading these very interesting questions, I came up with another one:
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
- 532
13
votes
0
answers
406
views
Surface area of convex hull [duplicate]
Let Q be the convex hull of a non-convex polyhedron P. Is it true that the surface area of Q is not greater than the surface area of P?
- 131
13
votes
0
answers
252
views
Does there always exist a self dual polytope that contains a given polytope contained in its dual?
Suppose a polytope $P$ is contained in its dual polytope $\tilde{P}$. Does there always exist a polytope $Q$ that contains $P$ and is self dual $Q=\tilde{Q}$? Is there any bound on the minimal number ...
- 241
9
votes
2
answers
321
views
Is a polytope that has in-spheres for faces of all dimensions already regular?
Let $P\subset\Bbb R^d$ be a convex polytope (convex hull of finitely many points).
A $k$-in-sphere of $P$ is a sphere centered at the origin to which each $k$-face of $P$ is tangent. So a 0-in-sphere ...
- 13.6k
9
votes
1
answer
240
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 ...
- 151k
7
votes
1
answer
483
views
Furthest distance half the diameter?
Let $S$ be the surface of a convex body, polyhedral or smooth,
embedded in $\mathbb{R}^3$.
For a point $x \in S$, let $F(x)$ be the set of furthest points
from $x$, measured by shortest paths on the ...
- 151k
7
votes
1
answer
274
views
Partitioning a convex object without harming existing convex subsets
$C$ is a convex planar figure and $C_1,\dots,C_n$ are pairwise-disjoint convex subsets of $C$, like this:
A convex-preserving partition of $C$ is a partition $C=E_1\cup\dots\cup E_N$, , such that $N\...
- 3,549
7
votes
1
answer
318
views
Minimum area of the convex hull of the union of a parallelogram and a triangle
This question is somewhat dual to my previously stated question about Maximum area of the intersection of a parallelogram and a triangle, where the triangle and parallelogram each is assumed to be of ...
- 7,276
7
votes
1
answer
648
views
Maximal volume of a simplex inscribed in a spherical cap
Let $B_n$ be the $n$-dimensional unit ball, and $B_n(\varepsilon)$ be the spherical cap with height $\varepsilon$ I am interested in the quantity
$$\Gamma:=\sup_{\Delta:\textrm{ inscribed simplex in }...
- 599
6
votes
1
answer
544
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 $\partial ...
- 151k
6
votes
1
answer
347
views
Measurement of "symmetry" of a convex body
I often hear that the regular simplex is "the least" symmetric convex body, and I've heard that there are some measures of symmetry of a body, that the simplex minimizes.
Could you please explain or ...
- 1,893
6
votes
1
answer
347
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
6
votes
2
answers
207
views
Volume satisfying inequality constraints (simplex subset)
Is there a way to find the volume of the "feasible region" of a standard simplex satisfying simple range constraints?
$x_1+x_2+...+x_n = 1$
$a_1 \le x_1 \le b_1$
$a_2 \le x_2 \le b_2$
$...$
$a_n \le ...
- 61
6
votes
1
answer
185
views
Maximizing ratio volume/diameter^n by an affinity
Suppose we have a convex compact body $D\subset \mathbb R^n$. We can try to apply affine transformation keeping the volume and decreasing the diameter of $D$.
It is clear that there is a constant $\...
- 5,063
6
votes
1
answer
254
views
Triangulations of convex surfaces
Let $M$ be a smooth closed positively curved surface in Euclidean 3-space, $T$ be a geodesic triangulation of $M$, and $E$ be the edge graph of the convex hull of vertices of $T$.
It is easy to see ...
- 7,194
5
votes
2
answers
294
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 ...
- 7,194
5
votes
2
answers
134
views
Is there a non-orthogonal linear deformation of a polytope that preserves edge-lengths and vertex-origin-distances?
Is there a polytope $P\subset\Bbb R^d$ (convex hull of finitely many points, not contained in a proper affine subspace), and a linear, but non-orthogonal transformation $T\in\mathrm{GL}(\Bbb R^d)\...
- 13.6k
5
votes
0
answers
93
views
Which polytopes can be deformed while keeping their edge-lengths?
Let $P\subset\Bbb R^d$ be a convex polytope (a convex hull of finitely many points). Lets call it flexible, if it can be continuously deformed while
keeping its combinatorial type, and
keeping its ...
- 13.6k
4
votes
4
answers
536
views
Vertex-transitive polytopes in any dimension with any number of vertices?
Given positive integers $d$ and $v$ with $v \geq d+1$, does there always exist a (convex) vertex-transitive $d$-polytope with $v$ vertices? It seems that the answer should be "obviously" true, but I ...
- 51
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
4
votes
1
answer
333
views
n-simplex in an intersection of n balls
Consider any $n$-simplex, $n \geq 2$. For each edge $(i,j)$, consider $n$-ball $B_{ij}$ such that vertices $x_i$ and $x_j$ are antipodal on this ball. Fix a point $x_0$ in the simplex. The question: ...
- 195
4
votes
2
answers
1k
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 (http://www.cs.berkeley.edu/~wkahan/Ellipint....
- 263
4
votes
1
answer
256
views
Polar interpretation of convexity
Let $C$ be a convex polygon in the plane containing the origin, and let $r(\theta)$ for $\theta\in[0,2\pi)$ be a parametrization of its boundary. Is there a condition on $r$ that is equivalent to (or ...
- 645
4
votes
1
answer
124
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 ...
- 7,194
4
votes
0
answers
52
views
Quantifying error in the reconstruction of convex polytopes from moments
The problem of reconstructing a geometric object from its moments is of interest in a variety of fields. In the paper The Inverse Moment Problem for Convex Polytopes, the authors show that a convex ...
- 181
4
votes
0
answers
224
views
Characterization of curves contained in the boundary of convex bodies
Given a continuous closed curve $\gamma$ in $\mathbb R^n$ does there exist a convex body $K$ (convex set with non-empty interior) such that $\gamma\subset \partial K$?
I am looking for a reference to ...
4
votes
0
answers
230
views
How to find the dimension of the polar cone of a convex cone generated by some given vectors
Suppose we have access to a generating set $\{v_1, ..., v_k\}\subseteq\mathbb{R}^n$ of the convex cone $C=cone(v_1, ..., v_k)$, where $cone(\cdot)$ is the conical hull (i.e. nonnegative span) of ...
- 461
3
votes
1
answer
804
views
Approximation of a convex body by a contained polytope
This question deals with approximating a convex body (a compact convex set of $\mathbb{R}^d$ with non-empty interior) by convex polytopes.
For a given $\delta$, let $n_\delta$ be the number of faces ...
- 591
3
votes
0
answers
52
views
Deformations that flatten small curvature
I'm trying to show that any 3-dimensional polyhedron with many vertices can be mildly deformed so that its vertices are no longer convexly independent. I suspect it suffices to look at a vertex with ...
- 31
2
votes
1
answer
141
views
Volume of a polytope with relaxed constraints
Consider a polytope in $n$ dimensions defined by a set of linear constraints:
$$P = \{x \in \mathbb{R}^n : Ax \leq b\}$$
where A is some $m \times n$ constraint matrix, and $b = (b_1,\ldots,b_m)$ is ...
- 21
2
votes
1
answer
367
views
Angle between 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
$\mathbf{w}\_k=(w_{k1},\ldots,...
- 111
2
votes
1
answer
308
views
Intersection of the simplex with a linear subspace of codimension $2$
The sets are defined in $\mathbb{R}_+^n$ $(n\geq 1)$. The relative interior of a convex set $C$ is denoted $\mathring C$.
Let $S$ be the $n$-simplex:
$$S=\left\{x\in\mathbb{R}_+^n,\,\sum_{i=1}^n x_i=1\...
- 449
2
votes
0
answers
51
views
Estimating the Hausdorff distance of parallel facets of convex polytopes
Background
Let $\mathcal{K}_P^n$ denote the class of open, convex, $n$-dimensional polytopes in $\mathbb{R}^n$ containing the origin. For each $K\in \mathcal{K}_P^n$, its gauge function $f_*:\mathbb{R}...
- 21
2
votes
0
answers
103
views
Polytopes with large dihedral angles
The regular $d$-simplex has dihedral angle $\arccos(1/d)<90^\circ$, and the $d$-cube has dihedral angle exactly $90^\circ$.
The maximal dihedral angle of a prism over a $(d-1)$-simplex is also $90^\...
- 13.6k
2
votes
0
answers
41
views
Describing hull of vertex intersections of two convex bounded polytopes?
We have two convex bounded polytopes $P_1$ and $P_2$ where
a. $P_2\subseteq P_1$
b. $\mathcal{V}(P_2)\cap\mathcal{V}(P_1)\neq\emptyset$.
Is there a name for the polytope $P=\mbox{Conv}(\mathcal{V}(...
- 13.9k
2
votes
0
answers
415
views
Find the intersection between two convex hulls, in this specific case
We work over $\mathbb{R}^K$. Let $V$ be the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$.
Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
- 233
1
vote
2
answers
431
views
Higher dimensional convex hull
Let $CH(S)$ be a convex hull of a finite set $S$ and denote the set of all the vertices of $CH(S)$ as $Vert(S)$. For a vertex $v \in Vert(S)$, it has an associated set $E(v)$ which is defined as $E(v)=...
user33954
1
vote
1
answer
1k
views
Extreme points of convex hull of Minkowski sum [closed]
Let $\operatorname{conv}(a_1,\ldots,a_m)$ denote the convex hull of $\{a_1,\ldots,a_n\}$. Let $P = \operatorname{conv}(a_1,\ldots,a_p)$ and $Q = \operatorname{conv}(b_1,\ldots,b_q)$ be two convex sets ...
- 1,713
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
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
61
views
Fitting a convex polytope with 𝑛 facets between two nested spheres
This is related to a research problem that is interested in approximation of spheres by convex polytopes.
Let $C_r$ and $C_R$ be two spheres in $\mathbb R^d$ of radius $r$ and $R$, respectively, where ...
1
vote
0
answers
43
views
Quantitative error control in Minkowski-Stein formula
Let $K\subseteq\mathbb R^d$ be a compact convex body with non-empty interior, and $E$ be a $(d-1)$-dimensional linear subspace of $\mathbb R^d$. Let $\theta\in\mathbb R^d$ be the unit vector such that ...
- 373