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

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

1
vote
0answers
49 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
18 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
86 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
24 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
96 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
60 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
87 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
209 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
71 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
76 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
31 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
53 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
465 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
132 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
224 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
232 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
101 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
166 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
83 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
43 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
102 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
527 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
134 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
91 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
70 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
38 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
103 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
158 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
151 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 ...
2
votes
1answer
170 views

Several convex polytopes in a simplex; fix an extreme point for each; how many can be supported by a function monotonic on all line segments?

Sorry the title may be unclear. I do not know how to give it a good title..... Let $\Delta$ be a probability simplex of $R^N$; i.e. set of all points $x$ such that $x\geq0$ and $\sum_{k=1}^Nx^k\leq1$....
22
votes
1answer
329 views

What is the minimal volume of the intersection of a self-dual cone and the unit ball?

When thinking of some other problem, I stumbled upon the following innocently looking question that is natural enough to have been considered (and, possibly, solved) many years ago. However my ...
0
votes
0answers
44 views

Finding a point in the relative interior of the convex hull of a set of integer-valued vectors

Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...
1
vote
0answers
46 views

Relations between conjugate ℓₚ unit ball surface areas

I understand that little is known on the surface area of the unit ball in $\ell_p$, excepting the cases $p=1,2,\infty$, but can anything be said on the relation between the surface areas for $p$ and ...
11
votes
1answer
197 views

Rigidity of doubled convex caps

Suppose that we have a convex cap, i.e., a convex surface in $R^3$ homeomorphic to a disk whose boundary lies in a plane. Reflect the cap through the plane of its boundary and glue it back to the ...
1
vote
0answers
41 views

Projecting two convex polyhedra onto their intersection

Suppose we are given two convex polyhedra $\mathcal{C}_1, \mathcal{C}_2 \subset \mathbb{R}^n$ with non-empty intersection $\mathcal{C}_1 \cap \mathcal{C}_2 \neq \emptyset$. For the orthogonal ...
3
votes
2answers
181 views

Extreme points of a convex set

Let $S$ denote the set of all complex non-negative definite matrices with all diagonal elements being less that or equal to one. Can we show that any matrix which belongs to the set of all non-zero ...
3
votes
3answers
221 views

Inner radius of a random convex hull

Let $\sigma_1,\ldots,\sigma_M$ i.i.d. random vectors in $\mathbb{R}^d$, and for notational convenience, let $\Sigma=(\sigma_1,\ldots,\sigma_M)$. I am interested in understanding $$ \gamma(\Sigma) = \...
2
votes
2answers
202 views

How to show that the origin is not in the convex hull, in this problem?

I am given $3$ points $(x_i,y_i,z_i) \in \mathbb{R}^3\setminus \{\mathbf{0} \}$, for $i=1,2,3$, satisfying the following two polynomial equations (the first equation is actually not the intended one, ...
1
vote
0answers
30 views

Limiting law of quadratic functions of sample averages

Let $X_1,\cdots,X_n$ be independent centered univariate random variables. Let also $\{w_{ij}\}_{i,j=1}^{k,n}$ be a set of deterministic scalar weights, where $k\ll n$. Define sample averages $$ \...
11
votes
2answers
310 views

Convex hull of the Stiefel manifold with non-negativity constraints

Consider the Stiefel manifold $$\mathrm{St}(n,k) :=\{X \in \mathbb{R}^{n\times k} : X^TX = I_k\},$$ where $I_k$ is the $k$-dimensional identity matrix. It is well known that $$\mathrm{conv} \left( ...
3
votes
0answers
152 views

What is a natural way to extend a function from a subset of vertices to faces?

Let $n$ be a positive integer, and suppose $f$ is a probability distribution on the $2^n$ subsets of $[\![n]\!] := \{1,\ldots,n\}$. What is a "natural" way to extend $f$ to a distribution $\bar{f}$ on ...
2
votes
0answers
52 views

Enveloping a Jordan curve with a trace of another one

This question is inspired by this one, or rather the way I understood it. Let $\gamma$ and $\delta$ be parametrised Jordan curves on the plane (i.e. homeomorphisms from $S^1$ onto its image in $\...
1
vote
1answer
130 views

“Minkowski Multiplication” of Convex Sets?

Apologies if this question might be trivial or has been asked already (haven't found an equivalent post), but I am trying to figure out whether the following is true: Given two convex sets $\mathcal{...
5
votes
3answers
335 views

Is there a dense subset on closed Jordan curve $C$ which its points make intersections under certain rotations?

Is it true that for any given closed Jordan curve of $C \subset \mathbb{R}^2$ there is a dense subset $A$ such that for every point $p\in A$ we have the following property: If we rotate $C$ around $p$...
4
votes
0answers
71 views

On symmetry and measure concentration rate for convex bodies

The concentration of measure on the cube $ [0, 1]^n $ equipped with uniform probability measure $\mu_{\infty}$, states that for any $A \subset [0, 1]^n $ with $ \mu_{\infty}(A) \geq \frac{1}{2} $, we ...
5
votes
0answers
141 views

Homogeneous linear and quadratic inequalities

I have a bunch of vectors $b_i \in R^n$ for $i = 1,\ldots,N$ and a bunch of (indefinite) matrices $A_j$ for $j = 1,\ldots,M$. Let's consider the set $S \subset R^n$ of $x \in R^n$ vectors such that $$...