Questions tagged [convex-geometry]

A branch of geometry dealing with convex sets and functions. Polytopes, convex bodies, discrete geometry, linear programming, antimatroids, ...

Filter by
Sorted by
Tagged with
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 ...
Nandakumar R's user avatar
  • 5,473
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 ...
Gericault's user avatar
  • 225
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 ...
Shijie Gu's user avatar
  • 1,936
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 ...
Nandakumar R's user avatar
  • 5,473
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{...
RyanChan's user avatar
  • 550
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 ...
Johnny T.'s user avatar
  • 3,547
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 ...
Nandakumar R's user avatar
  • 5,473
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>...
Kaleb's user avatar
  • 71
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 $\...
Mingchen Xia's user avatar
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] ...
user avatar
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,...
Sven's user avatar
  • 11
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 ...
Nandakumar R's user avatar
  • 5,473
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}, ...
Daniel Turizo's user avatar
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 ...
Nandakumar R's user avatar
  • 5,473
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 ...
Noah Stephens-Davidowitz's user avatar
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 ...
Mathlover's user avatar
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 ...
Sam Hopkins's user avatar
  • 22.7k
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{...
πr8's user avatar
  • 688
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,...
Timo59's user avatar
  • 71
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 ...
Nandakumar R's user avatar
  • 5,473
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 ...
Nandakumar R's user avatar
  • 5,473
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 ...
Nandakumar R's user avatar
  • 5,473
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 ...
Nandakumar R's user avatar
  • 5,473
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 ...
lrnv's user avatar
  • 686
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 ...
Nandakumar R's user avatar
  • 5,473
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 ...
dohmatob's user avatar
  • 6,716
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 ...
Daniel Turizo's user avatar
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 ...
Nandakumar R's user avatar
  • 5,473
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 ...
jcdornano's user avatar
  • 469
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 ...
asv's user avatar
  • 21.1k
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 $...
Avi Steiner's user avatar
  • 3,031
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$...
Mathemagica's user avatar
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):=(\...
asv's user avatar
  • 21.1k
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 ...
asv's user avatar
  • 21.1k
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 ...
Inner_peace's user avatar
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 ...
Juan Moreno's user avatar
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 ...
GuyS's user avatar
  • 43
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{...
Olórin's user avatar
  • 179
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 ...
lady gaga's user avatar
  • 153
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-...
user avatar
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 ...
Riccardo Pengo's user avatar
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) = \...
dohmatob's user avatar
  • 6,716
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 ...
Pete's user avatar
  • 115
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 ...
Yoav Len's user avatar
  • 147
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 ...
πr8's user avatar
  • 688
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 \...
user29985's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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$, ...
Tomer's user avatar
  • 135
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. ...
dohmatob's user avatar
  • 6,716
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 ...
arjun's user avatar
  • 921

1
3 4
5
6 7
21