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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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

2
votes
0answers
27 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
51 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
48 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 ...
13
votes
2answers
361 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
113 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 $...
2
votes
0answers
43 views

Relative interior of subdifferential

$\def\ri{\mathop{\rm ri}}$ Conjecture: Let $f{:}\ \mathbb{R}^n\to\mathbb{R}$ be convex and let $x,y\in\mathbb{R}^n$. If $0\in\ri\partial f(x)\cap\ri\partial f(y)$ then $\partial f(x)=\partial f(y)$. ...
7
votes
2answers
214 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
219 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
99 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
160 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
73 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
41 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
100 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
521 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
29 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
123 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
89 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
69 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
113 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
37 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
98 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
453 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
153 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
149 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
151 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
318 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
31 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
194 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
37 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
169 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
217 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
201 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
295 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
151 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
51 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
128 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
323 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
68 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
140 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 $$...
1
vote
0answers
36 views

Quantitative error control in Minkowski-Stein formula

Let $K\subseteq\mathbb R^d$ be a compact convex body with non-empty interior, and $E$ be a $(d-1)$-dimensional linear subspace of $\mathbb R^d$. Let $\theta\in\mathbb R^d$ be the unit vector such that ...
5
votes
0answers
54 views

Numerical approximation of the $\ell_p$ surface area

What numerical method can approximately compute the $(n-1)$-dimensional surface area of the $\ell_p$ ball $\{x\in\mathbb R^n: \sum_{i=1}^n |x_i|^p=1\}$, for $p\in[1,\infty)$? Ideally the method should ...
5
votes
2answers
229 views

Volume ratio of general $\ell_p$ balls and surfaces

This question is a generalization of the question Volume ratio of $\ell_1$ balls and $\ell_1$ surfaces For any $p\in[1,\infty]$ define $\|x\|_p := (|x_1|^p+\cdots+|x_d|^p)^{1/p}$ for $p\in[1,\infty)$ ...
5
votes
1answer
207 views

On faces of convex sets of positive semidefinite matrices

A face $F$ of a convex set $C$ is a set such that, if $x \in F$ is a convex combination of other elements in $C$, then they must also be in $F$. I will denote by $F(C,x)$ the smallest face of $C$ ...
-1
votes
1answer
95 views

Does a half plane contain intersection of some other half planes? [closed]

I'm doing research in Optimization and I have found this obstacle in the way. If we have set of half planes like $c_ix\leq b_i$ where $i\in \{1,\ldots ,k\}$ there is an algorithm(it would be better ...
4
votes
0answers
76 views

recursively convex plane curves

For the lack of a better term let's call a convex simple loop $u(t)$ recursively convex if for any $n \geq 0$ the $n$-th derivative $u^{(n)}(t)$ is a convex simple loop. We conjecture that any ...
4
votes
1answer
152 views

On the 1/2 assumption on concentration of measure for continuous cube

The concentration of measure on $ [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 have: $$...
10
votes
2answers
646 views

Does Helly's theorem hold in the hyperbolic plane?

The Helly theorem in the Euclidean plane asserts that if $S_1, \dots, S_n$ are $n \ge 3$ convex subsets such that $S_i \cap S_j \cap S_k \ne \emptyset$ for all distinct triples $i,j,k$, then the total ...
0
votes
0answers
108 views

Are there examples of both strongly convex and smooth functions for $l_p$ norm?

Given an $l_p$ norm $\| x \|_p = (\sum_{i=1}^n |x_i|^p)^{1/p},$ we call a convex differentiable function $f: \mathbb{X} \rightarrow \mathbb{R}$ both strongly convex and smooth if there exists $m, M &...