Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [convex-geometry]

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

10
votes
0answers
53 views

Can we always shift two disjoint convex bodies a little bit to decrease the volume of their convex hull?

Let $K,L\subset\mathbb R^d$ be two disjoint compact convex sets with non-empty interiors. Can $x=0$ be a point of local minimum for the function $F(x)=\text{vol}_d(\text{conv(K,L+x))}$? I was asked ...
1
vote
0answers
37 views

Volume of caps of a polytope

Let $K$ be a polytope in $\mathbb R^d$, blow it up by a factor $\lambda>0$. For a unit vector $u \in \mathbb S^{d-1}$, $\lambda K$ has 2 support hyperplanes $H_1$ and $H_2$ with corresponding ...
4
votes
1answer
75 views

Regularity of John's ellipsoid

Consider a finite dimensional real Banach space $E$, with norm say $|\cdot|$. Let $N$ denote the set of all norms on $E$. Suppose that $\varphi_1, \varphi_2 \in N$ have unit balls $B_1$ and $B_2$, ...
2
votes
1answer
79 views

Reference for Minkowski functional when 0 is not in the interior

The Minkowski functional on a normed linear space $E$ is usually defined for convex (or sometimes even non convex) subsets $C$ of $E$ such that $0 \in \operatorname{int}(C)$. Is there any standard ...
0
votes
1answer
70 views

Is an ambiguity set with Wasserstein distance of order 1 is convex?

I have a question about the convexity of an Wasserstein ambiguity set. Let $W_1(\mu, \nu)$ be the Wasserstein distance of order 1 between $\mu$ and $\nu$, defined as $$W_1(\mu, \nu) := \min\limits_{\...
0
votes
1answer
69 views

Closed form solutions for maximal subsets of convex polytopes

I'm looking for any known exact results about inscribing simple convex bodies inside a convex polytope. The most famous is the Löwner-John ellipsoid, but as far as I understood in general there is no ...
2
votes
0answers
53 views

Smooth dependence of convex functions on Monge-Ampère measure

Let $\Omega\subset\mathbb{R}^2$ be a bounded convex domain, $f$ be a positive smooth function on $\Omega$ and $\phi:\partial\Omega\rightarrow\mathbb{R}$ be a continuous function. It is known that as ...
2
votes
0answers
33 views

An implementation of Minkowski reconstruction in 3 dimensions

By a theorem of Minkowski from 1903, an $n$-dimensional polytope $P\subset \mathbb R^n$ is determined up to translation by its unit face normal $u_1,\dots,u_k\in S^{n-1}$ and the corresponding $(n-1)$ ...
0
votes
0answers
33 views

When is the set of faces of a convex polytope algebraically independent?

This is related to another question of mine Let $V=\Bbb R^n$. Morelli defined the (commutative unital) ring $L(V)$ to be the additive group generated by the indicator functions of convex polytopes in ...
3
votes
0answers
67 views

The ring generated by a convex polytope and its faces

Let $V=\Bbb R^n$. Morelli defined the (commutative unital) ring $L(V)$ to be the additive group generated by the indicator functions of convex polytopes in $V$ with multiplication induced by Minkowski ...
2
votes
0answers
61 views

Inclusion of convex polytopes and embedding from $\ell_2$ to $\ell_\infty$

I would like to dig deeper into the problem posted Probability that a convex shape contains the unit ball: If you pick n points uniformly at random from the surface of a d dimensional sphere of ...
1
vote
1answer
169 views

Boundary regularity for the Monge-Ampère equation $\det D^2u=1$

Let $\Delta$ be an open triangle in $\mathbb{R}^2$ and $u\in C^0(\overline{\Delta})\cap C^\infty(\Delta)$ be the convex function satisfying $$ \det D^2u=1,\quad u|_{\partial\Delta}=0. $$ Classical ...
1
vote
1answer
60 views

Linear relations between volume of a polytope and its faces

Let $P$ be a polytope. Is anything known about the set of linear relations that hold between the volumes of the (not-necessarily proper) faces of $P$ as $P$ “varies slightly”? By varies slightly I ...
14
votes
3answers
311 views

What is known about sufficient conditions for the rigidity of a convex surface?

A convex surface is a connected open subset of the boundary of a convex body in $\mathbb{R}^3$. An "infinitesimal bending" of a convex surface $S$ is a deformation of $S$ given by a velocity field $v:...
2
votes
1answer
101 views

Polygon of convex arcs

Convex polygons in the plane $R^2$ arise in linear programming where the constraints are linear. The objective linear function attains its maximum at a vertex of the feasible region(if exists). Assume ...
3
votes
1answer
129 views

Minkowski sum of polytopes from their facet normals and volumes

By Minkowski's work in the early 1900s, every polytope $P\subset\mathbb R^n$ is determined up to translation by its unit facet normals $u_1,\dots,u_k$ and facet volumes $\alpha_1,\dots,\alpha_k$. ...
7
votes
1answer
214 views

Log-concavity of areas of level sets

Suppose $f: \mathbb{R}^d \to \mathbb{R}$ is a smooth convex function. Consider the level sets of the function, namely $M_s = \{x: f(x) = s\}$. Is it true/known that the surface areas of $M_s$ are ...
1
vote
0answers
56 views

On Topological Tverberg Theorem

Let $r$ be a prime power. The Topological Tverberg Theorem says that any continuous map from a $(r-1)(d+1)$-simplex to $\mathbb{R}^d$ identifies points from $r$ disjoint faces. It is not hard to see ...
0
votes
0answers
22 views

Projecting a polyhedral cone onto its intersection with the infinity-norm ball

For a point in a convex polyhedral cone, $x\in \mathcal{C} = \{\sum_{i=1}^m \alpha_i r_i \vert \alpha_i \geq 0, r_i \in \mathbb{R}^n \}$, is there an efficient algorithm to project $x$ onto the ...
2
votes
0answers
98 views

Can computers take uniform samples from a polytope?

For each $r \in \mathbb N $ write $\mathbb Z/ 10^r = \{a/10^r: a \in \mathbb Z\}$ and $P(r)$ for the lattice $(\mathbb Z/10^r)^N \subset \mathbb R^N$. Suppose the plane $P \subset \mathbb R^N$ is ...
3
votes
0answers
35 views

Level sets of strongly convex and smooth functions

Let $f: \mathbb{R}^N \to \mathbb{R}$ be a $\alpha$-strongly convex and $\beta$-strongly smooth function, i.e., $$ f(x) + \langle\nabla f(x), y- x\rangle + \frac{\alpha}{2}\|y-x\|^2 \leq f(y) \leq f(x) ...
4
votes
1answer
98 views

a compact set with nonempty convex sections

Let $X = [0,1]^d$ be the unit cube in the $d$-dimensional Euclidean space. For every $x \in X$ and every coordinate $i=1,2,\ldots,d$ denote by $x_{-i} := (x_j)_{j \neq i}$. Given a set $Y \subseteq X$ ...
3
votes
1answer
63 views

Number of Inner Diagonals of Convex Hulls of $n+2$ Points in Convex Configuration in $E^n$

Question: Is it true that $E^2$ is the only Euclidean space, in which the convex hull of $n+2$ points in convex configuration has two inner diagonals and in all other cases there is only one ...
0
votes
3answers
93 views

On the properness of the graph of a convex function

Let $f : \Omega \subseteq \mathbb{R}^n \to \mathbb{R}$ be a smooth and convex function. Let us assume that $\Gamma_f = \mathrm{graph}(f) $ is a complete hypersurface of $\mathbb{R}^{n+1}$. Then I know ...
5
votes
2answers
234 views

Is every polytope combinatorially equivalent to the intersection of a simplex and a linear subspace?

I wonder whether such a result is known, and if so, whether the proof is trivial. By polytope I mean the convex hull of finitely many points in $\Bbb R^n$. Assume the simplex to be symmetric and ...
4
votes
0answers
73 views

Geometric meaning of the chi-square “measure of association”

In Statistics, there's a standard test of independence of two random variables taking values in finite sets $I,J$. It relies on the computation of $\chi$-square statistics, $$ \chi^2:=\sum_{(i,j)\in ...
2
votes
1answer
77 views

Why the convexity condition on the definition of a face of a convex set?

A face of a closed convex set $X\subseteq\mathbb{R}^n$ is defined to be a set $F\subseteq X$ such that: $F$ is convex. Every line segment from $X$ whose interior meets $F$ is contained in $F$. Is ...
2
votes
0answers
32 views

Extreme points in $d$-dimensional quadrant hull of $n$ random points in a halfplane

Finding the asymptotic growth of the expected number of extreme points of the quadrant hull in $d$ dimensions seems to be a well studied problem. Interestingly, the solution appears to vary widely by ...
0
votes
0answers
58 views

Applying a piecewise linear function to vertices of a polytope while remaining in facet representation

Let $P \subseteq \mathbb{R}^d$ be a polytope with vertices $V$, and let $f : \mathbb{R}^d \to \mathbb{R}$ be a function. Let $P' \subseteq \mathbb{R}^{d+1}$ be the polytope with vertices $\{(v, f(v)) \...
2
votes
0answers
58 views

Convex hull of piece-wise linear functions

Let $K>1$ be a positive integer. Consider a function class $$\mathcal{F}_K:=\Big\{\max_{1\leq k\leq K} a_k^\top x + b_k:\ ||a_k||\leq 1, |b_k|\leq 1, \forall 1\leq k\leq K \Big\}$$ on some compact ...
14
votes
2answers
489 views

Structures of the space of neural networks

A neural network can be considered as a function $$\mathbf{R}^m\to\mathbf{R}^n\quad \text{by}\quad x\mapsto w_N\sigma(h_{N-1}+w_{N-1}\sigma(\dotso h_2+w_2\sigma(h_1+w_1 x)\dotso)),$$ where the $w_i$ ...
4
votes
1answer
142 views

Is the preimage of a face under an affine map a face?

Let $X\subseteq\mathbb{R}^n$ be a convex set. Let $\pi{:}\ X\to\mathbb{R}^m$ be a linear map, with $m<n$ (for example, a projection). Let $\pi^{-1}(y)=\{x\in X\mid\pi(x)=y\}$ denote the inverse of $...
7
votes
2answers
239 views

Visual proof of convergence for Steiner's symmetrization

I want to find a visual proof of the following fact: For any convex figure in the plane there is a sequence of Steiner's symmetrizations that makes it arbitrary close to a circular disc. All ...
8
votes
2answers
239 views

Is it possible to continuously select a probability distribution over fixed points in Brouwer's fixed point theorem?

According to Brouwer's fixed point theorem, for compact convex $K\subset\mathbb{R}^n$, every continuous map $K\rightarrow K$ has a fixed point. However, these fixed points cannot be chosen ...
2
votes
2answers
102 views

Does this formula for caliper diameter hold for concave polyhedra?

I recently asked on MathOverflow and also asked several people I know to prove the following: How do I prove that the average caliper diameter of the polyhedron across all possible rotations is ...
5
votes
3answers
170 views

Average caliper diameter (mean width) of a polyhedron

Define the caliper diameter of a polyhedron as follows: Let $P_1$ and $P_2$ be two planes both of which are parallel to the x axis such that the perpendicular distance between $P_1$ and $P_2$ is the ...
7
votes
0answers
88 views

Ellipsoid minimizing Banach-Mazur distance to convex body

Given a (symmetric) convex body $K \subset \mathbb{R}^n$ (equivalently, given a norm on $\mathbb{R}^n$), there is a unique ellipsoid of maximal volume in $K$, called the John ellipsoid. The John ...
0
votes
0answers
46 views

Choquet Theorem for the cone of non-negative operators

Let $\mathcal B_+$ be the convex cone of bounded non-negative self-adjoint operators on $L^2(\mathbb R)$. With the perspective of applying Choquet's Theorem, I would like to know if the extreme points ...
4
votes
1answer
103 views

Cutting a convex body into two congruent pieces

This question is related to How to make a sandwich from just one piece of bread?, asked on Feb 23 '17 by erz, and it goes as follows: Question. If a convex closed and bounded region $C$ in the ...
11
votes
3answers
532 views

Steiner's inequality reference request

I remember seeing somewhere that for every connected compact set $\Omega$ in $\mathbb{R}^2$ with piecewise $C^1$ boundary we have $$A(\Omega_r)\leq A(\Omega)+L(\partial \Omega)r+ \pi r^2,$$ where $$\...
0
votes
0answers
30 views

Realisation of a Polytope as a convex set [duplicate]

Suppose I have ALL the combinatorial data of an abstract Polytope: a list of all facets and incidence relations. Is there a way to produce linear functions, in a suitable $R^d$, so that the region ...
0
votes
0answers
138 views

Probability that the perturbed convex hull is larger than the original one

I am wondering if any convex geometers/probabilists have looked at the following question: Given $n$ randomly distributed (not sure what assumption to put there) points in $\mathbb{R}^d$, for each ...
3
votes
1answer
93 views

Is the level set of a product of affine linear functions comprised of convex curves?

Internet searches haven't helped. Can you? Let $\, f = \prod_{i=1}^n (a_i x + b_i y + c_i).$ Is each component of $\, f^{-1}(1)$ a convex curve? I expect so, and can prove it for $n=2,$ but I'm ...
0
votes
0answers
73 views

Volume of parametric integral of convex set

Given $t,\mu>0$. I am interested in computing the volume of the $n$-dimesnional set $$\int_{0}^{t}e^{A(t-\tau)}\begin{pmatrix}0\\ 0\\ \vdots\\ 0\\1\end{pmatrix}U\:{\rm{d}}\tau,$$ where the set $U$ ...
2
votes
1answer
114 views

Convex misfit of finite-dimensional convex bodies

The finite-dimensional convex bodies topic belongs to the combinatorial geometry. The direction below has a bit more of an algebraic flavor. Let me/us know if some or all of the notions below are ...
1
vote
0answers
48 views

Relative interior of a normal cone at a face of a convex polytope?

Suppose $A$ is a nonempty convex polytope in $\mathbb{R}^n$. Suppose $F$ is a face of $A$. Consider the normal cone of $A$ at $F$: $C_A(F)=\{v\in\mathbb{R}^n:v\cdot x\geq v\cdot y\ \forall\ x\in ...
3
votes
1answer
108 views

Size of a minimal non-negative conic basis

Suppose $v_1,\dots,v_n \in \mathbb{R}^k$ are entry-wise non-negative (column) vectors with $k<n$. Let $r \leq k$ be the non-negative rank of the matrix $V = [v_1 v_2 \cdots v_n]$ (i.e., the ...
9
votes
2answers
458 views

Parallelepiped is defined by the volumes of its faces

Let $v_1,...,v_n\in \mathbb{R}^n$ be linearly independent. The parallelepiped defined by these vectors is $P(v_1,...,v_n)=\{\sum_{i=1}^{n}\alpha_i v_i|~0\le\alpha_i\le 1\}$. Observe that while the ...
6
votes
1answer
164 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 ...
4
votes
0answers
152 views

Existence of geodesic convex functions

By a result of Shing-Tung Yau [1974, Mathematische Annalen 207: 269-270], there are no non-trivial continuous geodesic convex functions on complete manifolds with finite volume. What happened if we ...