Questions tagged [convex-geometry]
A branch of geometry dealing with convex sets and functions. Polytopes, convex bodies, discrete geometry, linear programming, antimatroids, ...
1,007
questions
1
vote
1
answer
93
views
Volume ratio of polytopes with few vertices
The volume ratio of a convex body $K\subset \mathbb{R}^{n}$ is $v_r(K) = \inf_{\mathcal{E}\subset K} \left(\frac{Vol(K)}{Vol(\mathcal{E})}\right)^{1/n}$ where the infimum run over ellipsoids included ...
- 4,743
2
votes
0
answers
174
views
Approximation of zonoids
I have a question regarding the papers on approximating zonoids with zonotopes. I'll first write down the approximation problem and then state what my question is.
Problem of Approximating Zonoids. ...
- 620
2
votes
1
answer
65
views
Optimal unions of planar convex regions
This post continues Optimal intersections between planar convex regions.
Question: Given two planar convex polygonal regions $C_1$ and $C_2$, how does one algorithmically find how to place and orient ...
CommunityBot
- 1
7
votes
2
answers
836
views
Applications of Cauchy's Arm Lemma
Cauchy's Arm Lemma is used in the proof of Cauchy's Rigidity Theorem for convex polyhedra. The Lemma states that in the plane or on the sphere that if all but one of the side lengths of two convex ...
- 1,446
1
vote
0
answers
110
views
Maximizing a parametric integral over the unit sphere
I am trying to compute the nonnegative quantity
$$
\underset{y\in\mathbb{S}^{d-1}}{\sup}\int_{0}^{t}(\Vert A(\tau)y\Vert_{1}- \Vert A(\tau)y\Vert_{q})d\tau, \quad 1 < q < \infty
$$
where $\...
- 1,498
4
votes
1
answer
171
views
How to solve this minimax matrix optimization problem?
Recently, I want to know how well can a $\ell_1$ ball be approximated by the image of a $\ell_2$ ball under a linear transform. I formulate this problem as the following optimization problem.
\begin{...
- 3,964
1
vote
1
answer
83
views
Can upper bounds on totally monotone functions be taken (WLOG) to be themselves totally monotone?
Consider the following: fix a function $\bar{b} : \mathbf{R}_+ \to [0, \infty]$, and define
\begin{align}
\mathcal{S} \left( \bar{b} \right) := \left\{ b : \mathbf{R}_+ \to [0, \infty] \, \text{s.t.} \...
- 118k
5
votes
1
answer
315
views
Are the polyhedral cones the only examples of cones that remains closed when they are added to vector subspaces?
Let $C \subset \mathbb{R}^{n}$ be a closed convex cone. If one wants to know whether the linear map $T:\mathbb{R}^{n} \to\mathbb{R}^m$ sends the closed set $C$ to another closed one, $T(C)$, it is ...
- 203
1
vote
1
answer
105
views
Measurable sets of $\mathbb R^n$ forming unique absolutely continuous convex combinations?
If we consider a finite set $A\subset\mathbb R^n$, uniqueness of the convex decomposition of points in $A$ is equivalent to the absence of $\mu\neq0$ signed measure supported on $A$ such that $\mu(\...
1
vote
1
answer
117
views
A neighborhood $Y$ of a set $X$ such that the line segment connecting any point in $Y$ and its projection to $X$ is contained in $Y$
A direct line from a point $p$ to a set $X$ is a line segment with one endpoint at $p$ and one endpoint in $X$, which is as short as any other line segment from $p$ to $X$. Given a closed set $X$ and ...
- 22.2k
1
vote
0
answers
28
views
Adjacent vertices of a permutohedron which is the orbit of a point $x$ with repeated coordinates
Question: Let $x=(x_1, ..., x_n) \in \mathbb{R}^n$, and let $P$ be the convex hull of the points formed by permuting the coordinates of $x$. Given a vertex $y$ of $P$, what is a general rule for ...
- 539
4
votes
0
answers
61
views
Good resources that talk about geodesically convex sets for riemannian manifolds?
Are there any good resources that talk about geodesically convex sets, and in particular convex hulls, for riemannian manifolds? I’ve been wanting to learn more about them, their geometry and ...
- 518
1
vote
0
answers
33
views
Reference for a general theory of spaces of one-directional rays?
There is a lot of work done on projective spaces, over real, complex numbers or over an abstract field. But I do not find a reference for similar theory where the vectors are projected to the same &...
- 330
2
votes
2
answers
153
views
Angle between a point in a convex polytope and the nearest point of a face
Let $P \subset \mathbb{R}^d$ be a convex polytope, and let $F$ be a face of $P$ (of co-dimension 1, let's say). Now let $x \in P \setminus F$ and let $y \in F$ be the nearest point of $F$ to $x$. Then ...
- 11
7
votes
4
answers
252
views
Existence of a non-null and non-negative vector in $F\cup F^\perp$
In $\mathbb{R}^n$ ($n\ge 1$) endowed with the usual dot product, for any linear subspace $F$, does there exist a non-null vector with non-negative coordinates in $F\cup F^\perp$?
- 259
1
vote
0
answers
44
views
Support functions for subset and superset
I have an ellipse $\mathcal{E} = \{x^TAx = 1\}$, and I have a connected subset of an ellipse $U\subset \mathcal{E}$
For a given $\theta$ let $x_U^*(\theta) = \arg \sup\{\langle x,\theta\rangle, x\in ...
- 205
31
votes
2
answers
2k
views
The logic of convex sets
Let me start with Helly's theorem: Let $A_1$, $A_2$, ..., $A_{n+2}$ be $n+2$ convex subsets of $\mathbb R^n$. If any $n+1$ of these subsets intersect (this means: have nonempty intersection), the so ...
- 33.2k
2
votes
1
answer
375
views
Minkowski sum, zonotopes, convex hull
For any set $P,Q$ in the Euclid space, define Minkowski sum '+' as follows: $P+Q=\{p+q|p\in P, q\in Q\}$. And define 'zonotope': a zonotope is the Minkowski sum of some (finite) segments (for example, ...
CommunityBot
- 1
1
vote
0
answers
71
views
Is there any previous study on the relationship between convexity and the order of points in the general position?
Let's assume $V =(v_1,v_2,v_3,… ,v_n)$ is a set points in a general-position. For each point $v_i$, let's list the points in the order we encounter as we rotate around a certain direction (say ...
- 11
0
votes
0
answers
98
views
Sharp, salient and opposite cones
I have been reading about star shaped sets and support cones from this article.
Can anyone please help me with examples the difference between a sharp and dull cone.
How come a salient cone has a ...
- 60.2k
0
votes
0
answers
174
views
Regarding definition of convex cone and apex
I have been reading about star shaped sets and support cones from this article. I am wondering about the definition of the cone as to why is it defined this way? Why is it $C-a$? I am familiar with ...
- 27
28
votes
0
answers
538
views
Can every 3-dimensional convex body be trapped in a tetrahedral cage?
Can every 3-dimensional convex body be trapped in a tetrahedral cage?
Although the question is fairly unambiguous, I give all relevant definitions:
$\bullet$ A subset $C$ of $\mathbb{R}^n$ is an $n$-...
- 60.2k
20
votes
4
answers
910
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 ...
- 30k
2
votes
2
answers
232
views
Distribution of the support function of convex bodies: beyond mean width
Let $K$ be a symmetric convex body in $\mathbb{R}^n$ (that is the unit ball of a norm). Let $h_K$ be its support function, that is $h_K(u) = \sup_{x \in K}\langle x,u \rangle$. The quantity $w(K) = \...
- 4,743
1
vote
1
answer
215
views
For $x_1,...,x_n$ iid random on sphere of radius $\sqrt{d}$ in $R^d$, what is a good upper-bound on min distance of $x_{n}$ from the other $x_i$'s?
Let $n$ and $d$ be large positive integers with $n \le d^\gamma$, for some absolute constant $\gamma>0$; i.e., $n$ is at most polynomial in $d$. Let $x_1,\ldots,x_n,x_{n+1}$ be drawn iid from the ...
- 6,726
0
votes
0
answers
67
views
Diameter of inner parallel body
Let's say I have a convex polytope $\mathcal{P} \subset \mathbb{R}^n$ with non-empty interior.
Let $\mathcal{P}=\bigcap_{i=1}^mH_i$ for some halfspaces $H_i$ and let $d=diam(\mathcal{P})=\sup\{\|x-y\|:...
- 9
5
votes
1
answer
240
views
Dimension reduction for non-negativity of elementary symmetric polynomials
Fix integers $1 \leq k \leq n$ and suppose $\mathbf{x} \in \mathbb{R}^n$ is such that $e_j(x_1,x_2,\ldots,x_n) \geq 0$ for all $1 \leq j \leq k$, where $e_j$ is the $j$-th elementary symmetric ...
- 151k
0
votes
1
answer
99
views
Estimation via projecting onto a convex body
Assume that $\theta$ is in a convex body $K \in \mathbb{R}^n$ and we observe $y = \theta + z$, where $z$ is a noise term (following, say, the normal distribution). Consider an estimator of $\theta$ by ...
- 118k
1
vote
0
answers
49
views
Comparing convex planar regions of equal perimeter and area - 2
We try to extend On comparing planar convex regions of equal perimeter and area .
Given two planar convex regions C1 and C2 both with unit perimeter, we define the difference between C1 and C2 as the ...
- 5,493
6
votes
2
answers
350
views
Parallelotope fundamental domains of the n-torus
The group $\mathbb Z^n$ acts on the topological space $\mathbb R^n$ by translation: if $z = (z_1, \cdots, z_n) \in \mathbb Z^n$ and $x = (x_1, \cdots, x_n) \in \mathbb R^n$, then $z\cdot x := z+x$. ...
- 2,578
1
vote
1
answer
87
views
Affine semigroup generating a lattice
This is a cross-post from MSE.
Everything is assumed to be finite-dimensional. Let $S$ be a finitely generated affine semigroup (i.e. a subsemigroup of a lattice $N$ of a Euclidean space). Assume that ...
- 60.2k
3
votes
1
answer
132
views
Finding the smallest centrally symmetric region that contains a convex planar region
Given a convex polygonal region C, how does one find/characterize the smallest zonogon (centrally symmetric convex polygon https://en.wikipedia.org/wiki/Zonogon) that contains C?
Note 1: In question ...
- 3,964
24
votes
3
answers
1k
views
Average measure of intersection of a convex region with its translate
Let $\lambda$ denote the Lebesgue-measure on $\mathbb{R}^n$, and let $C\subset\mathbb{R}^n$ be a convex region.
My question is about
$$f(C):=\int_{C} \lambda(C \cap (x + C) ) \mathrm{d} x.$$
How ...
- 6,726
0
votes
0
answers
99
views
Weak derivative of projection onto probabilist's simplex
Let $\Delta_n:=\{x\in [0,1]^n:\boldsymbol{1}^{\top}x=1\}$ denote the probabilist's $n$-simplex and let $P:\mathbb{R}^n\rightarrow\Delta_n$ denote the (Euclidean) metric projection onto this simplex ...
- 4,969
2
votes
1
answer
160
views
Existence of preferred direction for a random vector with arbitrary distribution on sphere, under a condition on its covariance matrix
Let $X$ be random vector on the unit-sphere $S_{n-1}$ in $\mathbb R^n$. We don't assume that the distribution of $X$ is uniform on $S_{n-1}$
I'm interested in proving the existence of a (...
- 118k
0
votes
0
answers
74
views
On finding optimal convex planar shapes to cover a given convex planar shape
Covering a specific convex shape S with n copies of another specified convex shape S' (which may be different from S) is well studied - for example, https://erich-friedman.github.io/packing/index.html....
- 5,493
2
votes
2
answers
293
views
Expected value of Tukey’s half-space depth for log-concave measures
Let ${\mathbb P}$ be a probability measure in ${\mathbb R}^n$. Let $x\in{\mathbb R}^n$ be an arbitrary point. Let ${\mathbb H}_x$ be the set of halfspaces of ${\mathbb R}^n$ containing $x$. Let
\begin{...
- 4,743
1
vote
0
answers
75
views
Convex planar regions with optimal average 'centralness' and 'depth'
For a planar convex region $C$ and an interior point $P$ we define:
the centralness ratio at $P$ is
$$\min\left(\frac{\text{shorter portion of }\chi}{\text{longer portion of }\chi}:\chi\text{ is a ...
- 5,493
33
votes
3
answers
2k
views
Polar body of a convex body that avoids a lattice
Let $K \subset {\bf R}^d$ be a symmetric convex body (an open bounded convex neighbourhood of the origin with $K = -K$) with the property that $K + {\bf Z}^d \neq {\bf R}^d$, i.e. the projection of $K$...
- 4,618
7
votes
2
answers
2k
views
What is the "Krein-Milman theorem for cones"?
Update: The question is completely answered. I had overlooked a reduction to the self-adjoint case, and the latter can be proved using a Hahn-Banach separation theorem. Thanks to Matthew Daws for ...
- 60.2k
1
vote
1
answer
89
views
How to compute external angles of a hypersimplex?
Recently, I concern with the volume of the outer parallel body of a hypersimplex that is defined as follows
$$
\mathcal{H}_s(n,k)=\left\{ (x_1,\cdots,x_n):\sum_{i=1}^n x_i=k,x_i\in[0,1] \right\},
$$
...
3
votes
1
answer
190
views
Well-behaved trajectories
Call trajectory any continuous function $f: \mathbb{R}_{\geq 0} \to \mathbb{R}^n$ (here, $\mathbb{R}_{\geq 0}$ is interpreted as time).
A polyhedral partition of $\mathbb{R}^n$ is a finite set of ...
- 4,263
1
vote
0
answers
72
views
A ratio to measure 'roundedness' of planar convex regions
Ref: A center of convex planar regions based on chords
The above discussion quotes the definition of 'centralness coefficient' and defines a center of a planar convex region. 1/2 is the least possible ...
- 5,493
2
votes
1
answer
256
views
On the Lipschitz continuity of $x \mapsto \arg\min_{c \in C}d(x,c)$ w.r.t Hausdorff distance
Let $C$ be a (nonempty) compact subset of euclidean $\mathbb R^n$, and consider the set-valued map $p_C:\mathbb R^n \to 2^C$ defined by
$$
p_C(x) = \{c \in C \mid \|x-c\| = \mbox{dist}(x,C)\},
$$
...
- 8,076
6
votes
3
answers
417
views
Isoperimetric inequality for $\epsilon$-expansion of a set only along a certain subspace
Let $\gamma_n$ be the standard gaussian distribution on $\mathbb R^n$. Let $V$ be a $k$-dimensional subspace of $\mathbb R^n$. Finally let $A$ be any (nonempty) Borel subset of $A$ with $\gamma_n(A) = ...
- 6,726
1
vote
1
answer
175
views
Sufficient conditions for the boundary unit-normal vector field of a closed convex set to be Lipschitz continuous
This is followup to the following question: On the Lipschitz continuity of the unit-normal vector field of a polytope
Let $C$ be a (nonempty) closed convex subset of $\mathbb R^n$. Note that to every ...
- 7,573
2
votes
1
answer
111
views
Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points
Let $K$ be a convex body in $\mathbb R^d$ which contains the origin and let $\theta \in (0,1)$.
Question. Is it always possible to find $n$ points $x_1,\dotsc,x_n \in \mathbb R^d$ such that
$$
\theta ...
- 8,076
1
vote
1
answer
100
views
On the Lipschitz continuity of the unit-normal vector field of a polytope
Let $\mu$ be a probability measure on $\mathbb R^n$ and let $P$ be a compact polytope in $\mathbb R^n$. For any $x \in \mathbb R^n \setminus P$, let $p(x) \in P$ be (unique!) point in $P$ which is ...
- 7,573
7
votes
4
answers
455
views
What does $\mathbb E_V \max_{x \in V,\,\|x\|=1} x^T Ax$ evaluate to when $V$ is random $k$-dim suspace of $\mathbb R^n$ and $A$ is fixed psd matrix?
Let $G_{k,n}$ be the grassmannian of $k$-dimensional vector spaces of $\mathbb R^n$. By the Courant–Fisher characterization, the $k$th largest eigenvalue of an $n \times n$ psd matrix $A$ is given by
$...
- 1,354
9
votes
2
answers
372
views
Which convex bodies roll straight?
Let $K$ be a convex body in $\mathbb{R}^3$.
Suppose $K$ is held at some position and orientation on an inclined plane,
and released.
Let there be sufficient friction so that it rolls without slippage.
...
- 12.7k