Questions tagged [convex-geometry]
A branch of geometry dealing with convex sets and functions. Polytopes, convex bodies, discrete geometry, linear programming, antimatroids, ...
1,006
questions
3
votes
1
answer
131
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 ...
1
vote
0
answers
58
views
Minimum bounding rectangle of symmetric convex bodies in the plane : is the ball the worst case
The minimal rectangle containing the euclidean ball in the plane is the standard cube $B_\infty = [-1;1]^2$. I would like to know if the euclidean ball is the worst symmetric convex body to be ...
4
votes
1
answer
95
views
Separation of convexity on uniquely geodesic space
A metric $d: X \times X \to [0,\infty)$
is said to be intrinsic provided that the distance between any two points is the infimum of the lengths of
paths joining the points. A space is an inner metric ...
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 ...
4
votes
1
answer
169
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{...
5
votes
0
answers
208
views
Reference request for convex geometry?
I am looking for a reference for an elementary convex geometry.
In Appendix A (page 1810) of this paper by Green and Tao, they cover some basic results from elementary convex geometry. The results ...
2
votes
0
answers
71
views
On cutting convex regions with average values of quantities minimized
This post continues from Cutting convex regions into equal diameter and equal least width pieces - 2 and Cutting convex regions into equal diameter and equal least width pieces - 3
A basic (and to my ...
1
vote
0
answers
47
views
When the summands of a positive definite matrix are positive definite
Let $A,B$ be two real symmetric matrices. Let $C = A+B$ be a positive-definite matrix. Write $C>0$ for $C$ being positive-definite. Suppose that $A>0 \implies C>0$ and $B > 0 \implies C>...
3
votes
0
answers
522
views
Mixed volumes of Newton–Okounkov bodies
Let $X$ be a smooth irreducible projective complex variety of dimension $n$. Let $X=Y_0\supseteq\cdots\supseteq Y_n$ be an admissible flag. Consider $n$ line bundles $L_1,\ldots,L_n$ on $X$. Let $\...
3
votes
1
answer
166
views
Parameterizing the space of convex quadrilaterals
If $P=\mathbb{R}^2$ is the plane, is there a continuous surjection from $P^4$ to the space of convex quadrilaterals?
Specifically, I'm looking for a continuous $f:P^4\to P^4$ such that:
[convexity] ...
1
vote
0
answers
57
views
Proving convexity of total distance between two parties with one meeting point [closed]
Apologies if I´m not using the correct mathematical wording or notation. I´ll try my best in the following problem
Suppose you have a coordinate system and 5 coordinates ($A1$, $A2$, $B1$, $B2$, $M_{x,...
3
votes
1
answer
255
views
Inscribed $n$-gons of maximum perimeter for an ellipse
It appears that the max area inscribed $n$-gon for an ellipse is not unique - if one inscribes a regular $n$-gon in a circle with radius a (there are infinitely many orientations for this inscribed ...
0
votes
1
answer
154
views
Maximum vertex amount of low-dimensional simplex projection
Consider an arbitrary simplex $\mathcal{S} \subseteq \mathbb{R}^n$ ($\mathcal{S}$ is a polytope in $\mathbb{R}^n$ with $n+1$ vertices and non-empty interior). Let ${\bf P} \in \mathbb{R}^{m \times n}, ...
1
vote
0
answers
59
views
To extend the Steiner-Lehmus theorem
The Steiner Lehmus theorem (https://en.wikipedia.org/wiki/Steiner%E2%80%93Lehmus_theorem) states: Every triangle with two angle bisectors of equal lengths is isosceles.
Question: What could one say ...
6
votes
0
answers
192
views
Does the ball maximize the "kissing probability" of symmetric convex bodies? [duplicate]
Given a symmetric convex body $K \subset \mathbb{R}^n$ (i.e., a bounded symmetric convex set with non-empty interior), I am interested in the following quantity
$$p_K := \Pr_{x_1, x_2 \sim K}[x_1 \in ...
0
votes
1
answer
343
views
The dimension of the normal cone of a face in a polytope
Let $P$ is a polytope in $\mathbb{R}^n$ if $F$ is one of its faces of dimension $d$ then the dimension of its normal cone $\mathcal{N}(F)$ is $n-d$.\
This seems to be intuitively obvious but I can't ...
2
votes
1
answer
128
views
Discrete random walk on polytope via involutions
Let $P$ be a convex polytope (or more generally convex body, I suppose) in $V=\mathbb{R}^n$. For each $v\in \mathbb{P}V$, we define an involution $\tau_v\colon P\to P$ by setting $\tau_v(p)$ to be the ...
4
votes
0
answers
95
views
Improving log-Sobolev inequalities via quadratic regularisation
Suppose that $\mu(dx) = \exp(-\psi(x)) \, \mathrm{dx}$ is a probability measure on $\mathbf{R}^d$.
For suitable functions $g \geqslant 0$, define
$$\text{Ent}(g) = \int \mu(dx) g(x) \log \left( \frac{...
6
votes
1
answer
222
views
Convex hull of a variety in real space
I am a physicist currently working on a question posed as part of an algebraic geometric description of a physical set:
I did not find a question that is closely related to what I am searching for yet,...
3
votes
0
answers
278
views
Polyhedrons and their centers of mass
Given a convex polyhedron, one considers 3 possibilities:
wireframe - only the edges of the polyhedron have mass which is uniformly distributed.
surface - only the surface is massive with uniform ...
2
votes
1
answer
124
views
Curves of constant width that contain triangles
Wikipedia references: Curve of constant width,
Reuleaux polygon.
We record a pair of questions on the same lines as Smallest 3-ellipses that contain triangles.
Questions:
How does one find and ...
2
votes
1
answer
237
views
Smallest 3-ellipses that contain triangles
Reference: https://en.wikipedia.org/wiki/N-ellipse
Question: How does one find and characterize the smallest 3-ellipses (n-ellipses with n =3) that contain a given triangle? 'Smallest' can mean 'least ...
1
vote
0
answers
52
views
Shadows and planar sections of polyhedra – 2
This post continues Shadows and planar sections of polyhedra and On planar sections of 3D convex bodies
Shadows and planar sections of polyhedra gives an example demonstrating that shadows (orthogonal ...
1
vote
0
answers
76
views
Weird transportation polytope
I'm looking to compute extremal points of a weird polytope. This polytope contains all matrices with positive entries $A \in \mathcal M_{n,m}\left(\mathbb R_+\right)$ such that:
every row sum except ...
5
votes
2
answers
228
views
On intersections of several convex regions
Question: Given n convex planar regions. Required to place them (in suitable position and orientation) so that that part of the plane lying under all the regions (their common intersection) is of ...
0
votes
2
answers
478
views
Wasserstein distance between $N(0,1/d)$ and the marginal distribution of $x_1$ when $x=(x_1,\ldots,x_d)$ is uniform on the unit-sphere in $R^d$
Let $x=(x_1,\ldots,x_d)$ be uniformly distributed on the unit-sphere in $\mathbb R^d$.
Question.
What is a good upper-bound for Wasserstein distance between $N(0,1/d)$ and the marginal distribution ...
0
votes
0
answers
145
views
Minimum circumscribed ellipsoid of $\mathcal H$-polytope
Given matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^n$, consider the $\mathcal H$-polytope $P$ defined as follows
$$ P := \left\{ x \in \mathbb{R}^n : Ax \leq b \right\} $$
I ...
6
votes
2
answers
424
views
On planar sections of 3D convex bodies
Consider the space of planar sections of any given convex 3D body.
Basic Question: What is the lower bound for the ratio
$$\frac{\text{area of section of greatest perimeter}}
{\text{area of section of ...
2
votes
0
answers
122
views
Inscribed square and convexity
Let $b(X)$ be the boundary of any $X$ subset of the plane.
Does there exist $A,B$ convex compact sets of the plane, such that $C:=A\setminus B$ is simply connected and not empty, and such that ...
8
votes
1
answer
145
views
The polytope algebras generated by polytopes with rational vs arbitrary vertices
The polytope algebra was defined by P. McMullen in "The polytope algebra" Adv. Math. 78 (1989) as follows.
Let us denote by $\Pi'_\mathbb{R}$ the quotient of the free abelian group generated ...
3
votes
0
answers
49
views
testing whether a polyhedral complex is convex
Definitions
A (polyhedral) cone in $\Bbb R^n$ is the solution set of a finite number of inequalities of the form $a_1x_1+\cdots+a_nx_n\geq 0$. Note that I don't require strict convexity, i.e. a cone $...
5
votes
1
answer
184
views
Improving regularity of the boundary of a convex set in Riemannian manifolds
Let $X$ be a geodesically complete Riemannian manifold (we may assume that $X$ is simply connected and negatively curved, although I don't think it matters). Given a closed, convex subset $K \subset X$...
4
votes
0
answers
63
views
Length of curves on convex hypersurfaces
Let $\gamma\colon[a,b] \to \mathbb{R}^n$ be a smooth curve.
Let $f_i\to f$ be a sequence of convex functions on $\mathbb{R}^n$ converging uniformly on compact subsets to $f$.
Let $\hat\gamma(t):=(\...
3
votes
1
answer
134
views
Busemann-Feller lemma in hyperbolic space
The classical Busemann-Feller lemma in Euclidean space says the following.
Let $K\subset \mathbb{R}^n$ be a closed convex set.
Then
for any point $x\in \mathbb{R}^n$ there exists unique nearest point ...
0
votes
1
answer
119
views
How hard is a linear programming with a bounded constraint?
Background: I am reading Greg Kuperberg's answer to the question Deciding membership in a convex hull. I am thinking about the complexity of ''Deciding membership in a convex hull''.
Restate the ...
2
votes
0
answers
868
views
Happy ending problem – Why not a proof by induction?
I have been thinking for a while on the happy ending problem, looking for approaches to attack the Erdős–Szekeres conjecture: the smallest number of points for which any general position arrangement ...
1
vote
1
answer
268
views
High-dimensional polytopes
I have two questions regarding polytopes in high dimensions, $\mathbb{R}^d$ where $d > 3$, that I could not find resources for on the web for. Suppose I have a polytope that is non-convex:
How can ...
2
votes
1
answer
260
views
Can the subdifferential become unbounded at interior points?
Consider $f: \mathbb{R}^n \to \overline{\mathbb{R}}$ a lower-semicontinuous, proper, closed and convex. My question is, can the subdifferential of $\partial f$ be unbounded in the interior of $\text{...
0
votes
0
answers
254
views
Convexity of a set of probability densities
Consider the space of probability densities $(P(\mathbb{R}^d), W_2)$ (probability measures on $\mathbb{R}^d$ with 2-Wasserstein distance).
How can we determine if a subset $Q$ is convex?
I know that a ...
2
votes
2
answers
383
views
Given a total variation distance from uniform, how well can we bound the probabilities of sub-intervals?
I made the following claim, which I now see that I don't know how to prove. Can anyone prove it?
Claim. Let $f$ be a concave and non-negative function on $[0,1]$ with $$\int_0^1 f = 1,$$
$$\int_0^1 |f-...
3
votes
0
answers
125
views
Counting lattice polytopes by volume
For any $n \in \mathbb{N}$ and $B \in \mathbb{R}_{\geq 0}$, let $\mathcal{P}(n,B)$ be the set of $n$-dimensional convex polytopes $\Delta \subseteq \mathbb{R}^n$, taken up to integral, unimodular ...
2
votes
1
answer
168
views
Analytic expression for the Moreau envelope of $x \mapsto \|Ax\|$
Given an $m \times n$ matrix $A$ and a vector $c \in \mathbb R^n$, define $\eta(A,c) \ge 0$,
$$
\eta(A,c) := \sup_{u \in \mathbb R^n} u^\top c - \frac{1}{2}\|u\|^2 - \|Au\|.
$$
Note that $\eta(A,c) = \...
7
votes
1
answer
212
views
Rigidity for convex surfaces in elliptic/hyperbolic space
From Alexandrov's work we know that any metric on the sphere with lower curvature bound $\kappa$ (in the sense of Alexandrov) can be realized as a closed convex surface (i.e. boundary of a compact ...
2
votes
0
answers
91
views
Linear forms and the second Voronoi decomposition
This is not my area of expertise, so forgive me if the question is a bit naive. Given a collection of vectors $v_1,\ldots,v_d$ in $\mathbb{R}^n$ (with $d\geq n$), there is a corresponding set of ...
2
votes
1
answer
109
views
Reweighting probability measures by convex potentials, and contraction in transport distance
Let $W: \mathbf{R}^d \to \mathbf{R}$ be a convex function such that $\int \exp(-W) = 1$, and define probability measures $\mu_y$ by
$$\mu_y (dx) = \exp( - W (x - y)) \,dx,$$
i.e. each $\mu_y$ is a ...
3
votes
0
answers
52
views
Independence-like property of convex combinations in a vector space
Consider the following property of a set of vectors $S\subset V$, where $V$ is a real vector space:
$$
\sum_{i=1}^m w_ix_i
= \sum_{i=1}^m u_iy_i,\quad
x_i,y_i\in S,\quad
0\le w_i,u_i\le 1, \quad
\...
1
vote
0
answers
63
views
Counting $\bmod 2$ number of vertices of sparsely represented polyhedra
Given a polyhedron
$$Ax\geq b$$
is there an $NC^1$ or an $NC^2$ algorithm to count the number of vertices $\bmod2$?
Assume $A\in\{0,1\}^{m\times n}$ and $b\in\mathbb Z^{m}$ ($m=O(n)$) and assume rows ...
3
votes
2
answers
826
views
Convex set with no interior contained in hyperplane?
Let $K$ be a convex set in a normed space $X$. Assume that $int(K)=\emptyset$ (norm topology). Must $K$ be contained in some (affine) hyperplane?
It's fairly easy to see that this is true in $ℝ^n$, ...
1
vote
0
answers
45
views
Analytic lower-bound for minimal value of $\|x\|^2$ such that $\|Cx-b\|^2 \le c^2$ (a hyperellipsoid)
Let $C$ be an $n \times p$ matrix and $b$ be a column vector of length $n$, and $c>0$. Let $E := \{x \in \mathbb R^p \mid \|Cx-b\| \le c\}$, a hyperellipsoid in nonstandard position.
Question 1. ...
3
votes
0
answers
80
views
Ornstein-Ulhenbeck like semigroup for the orthogonal group with a hypercontractive inequality
I am looking for an Ornstein-Uhlenbeck like semigroup $P_t$ and associated generator $\mathcal{L}$ on $G = \operatorname{SO}(n)$ or $\operatorname{O}(n)$ that has a hypercontractive inequality with a ...