Questions tagged [convex-geometry]
Use this tag when posting questions related to the concept of convexity and geometry. For example, for convex polygons.
0
votes
0answers
12 views
Computing projection onto the following closed convex set
Let $\mathbf{S}^n$ denote the space of symmetric, real-valued $n \times n$ matrices.
Consider the closed convex set
$$
\mathcal{C} := \{(X, x) \in \mathbf{S}^n \times \mathbf{R}^n : X \succeq xx^T,...
0
votes
0answers
14 views
Well-definedness of greatest convex function smaller than function
A proof I am reading relies on the existence in $\mathbb{R}^d$ of a greatest convex function $f_0:\mathbb{R}^d \rightarrow \mathbb{R} \cup \{-\infty\}$ less than or equal to a (continuous) function $f:...
0
votes
0answers
25 views
Is the Legendre transformation continuous?
Is the Legendre transformation continuous on the space of the convex $\mathbb R^{n} \to \mathbb R$ functions for the topology of the simple convergence?
First the limit of a sequence of convex ...
0
votes
0answers
14 views
Polyhedra, half spaces and compact
I would like to show that $\{ x ; \forall j \in \{1,...,n\}, \langle x, z_{j} \rangle \le s_{j} \} $ is compact when the convex cone generated by the $(z_{j})_{1 \le j \le n}$ is $R^{d}$.
I have been ...
0
votes
1answer
34 views
hyperbolic hexagon construction [on hold]
Can someone show a proof of the existence of a hyperbolic right
angled regular hexagon?
How would I make a decoration of $4n$ of these hexagons in a way where it glues the diagram for a hyperbolic ...
0
votes
2answers
24 views
Separation of two disjoint convex closed sets
Assume that $A,B\subset \mathbb{R}^n$ are two disjoint closed convex sets. Without using that $A$ and $B$ are closed sets, it follows already, that there is a non zero element $v$ and a real number $c$...
0
votes
0answers
16 views
In spectrahedra, are minimal rank points always extreme points?
Consider a matrix $A$ in a spectrahedron $S$ such that
$$\mbox{rank}(A) \leq \mbox{rank}(B)$$
for all $B\in S$ and assume that at least one matrix $C \in S$ we have that $\mbox{rank}(A) < \mbox{...
0
votes
0answers
15 views
Maximal enclosed D-simplex
Is it possible to construct convex D-polyhedron $P$ that there exists a D-simplex $A$ spanned on vertices of $P$, that its ...
0
votes
2answers
96 views
Distance between a cone and a disjoint hyperplane
I seek to prove the following, which I guess is true:
Define $A:=\{x \ge 0\} \subset \mathbb{R}^m$ and assume that $U\subset \mathbb{R}^m$ is an affine subspace with $A \cap U=\emptyset$. Show that ...
2
votes
1answer
46 views
Bounding a convex set by ellipses
Given any compact convex set $K$ in $\mathbb{R}^d$ with non-empty interior, does there exists an affine transformation $T$ such that:
$$\overline{B} (0, 1) \subset T(K) \subset d \cdot \overline{B} (...
0
votes
0answers
41 views
Does a convex set look the same near its face?
Recall that a face of a convex set $X\subseteq\mathbb{R}^n$ is a convex subset $F$ of $X$ such that every line segment with endpoints in $X$ whose relative interior meets $F$ lies entirely in $F$.
...
2
votes
0answers
46 views
How did Steiner prove his famous formula?
In convex integral geometry and geometric measure theory, Steiner's formula is the name of the following elegant result:
Let $B_n$ be the unit ball in $\mathbf R^n$. If $S$ is a nonempty bounded ...
0
votes
1answer
26 views
Euler's Formula To Show 2E=3V
I have this question:
"Consider a convex polyhedron, all of whose faces are square or regular pentagons. Say there are m squares and n pentagons. Assume that each vertex lies on exactly 3 edges"
...
0
votes
0answers
11 views
Find a bound of the biggest radius of hypersphere in convex hull centered on centroid
Setting:
We have a probability distribution on a space $\mathcal{X} \subset \mathbb{R}^d$, called $\rho(x)$, and we are given a sample of iid points $S^n = \{x_i\}_{i=1}^n$ from $\rho$.
Let $K: \...
1
vote
1answer
23 views
Is an open midpoint convex set in $\mathbb{R}^n$ always convex?
It can be easily shown that a closed midpoint convex set in $\mathbb{R}^n$ is always convex, but it has occurred to me that the counter-examples showing a midpoint convex set may not be convex, are ...
0
votes
1answer
28 views
$conv\{\bar{x},\bar{y},\bar{z} \} \cap conv\{\bar{x},\bar{y},\bar{t} \} \cap conv\{\bar{x},\bar{z},\bar{t} \} = \{\bar{x} \}$
Let $\{\bar{x},\bar{y},\bar{z},\bar{t}\}$ be 4 points in $\mathbb{R^2}$, such that $conv\{\bar{x},\bar{y},\bar{z} \} \cap conv\{\bar{x},\bar{y},\bar{t} \} \cap conv\{\bar{x},\bar{z},\bar{t} \} = \{\...
0
votes
0answers
14 views
Distance on the sphere is convex
Let $\mathbb{S}^n$ be the unit sphere and choose $p_0$ as the north pole. Consider the function $d:\mathbb{S}^n \to [0, \infty)$ defined by $d(p) = d(p,p_0) = \cos^{-1}( \langle p, p_0 \rangle)$. It ...
0
votes
0answers
23 views
Prove that this set of expected values is convex
I am facing the problem of proving that the following set $K$ is convex, it's part of a proof for the First Fundamental Theorem of Asset Pricing:
$$K := \{d \cdot E_\mathbb{Q}(\boldsymbol{X}): \...
0
votes
1answer
65 views
For which $C\subset \Bbb R^n_{++}$, the set $\log(C)$ is convex?
Let $\Bbb R^n_{++}=\{x\in\Bbb R^n\mid x_i>0, i=1,\ldots,n\}$ and let $\log\colon \Bbb R^n_{++}\to \Bbb R^n$ be the component-wise logarithmic function, i.e.
$$\log(x)=(\log(x_1),\ldots,\log(x_n))\...
0
votes
1answer
15 views
sum of convex cone with apex at 0 and its closure
Let $K\subseteq\mathbb R^n$ be an open convex cone with apex at 0, and let $\mathrm {cl}K$ be its closure, how to prove that
$K+\mathrm {cl}K=K?$
0
votes
0answers
11 views
How to understand the Minkowski content? [duplicate]
Picture below is from https://en.wikipedia.org/wiki/Minkowski_content .
Although I can the word, but I really don't know what is upper Minkowski content and lower Minkowski content , how to ...
0
votes
0answers
8 views
Measure convex hull point and ball
The Lebesgue's measure (in $R^{n}$) of the convex hull of $B(0,a)$ and a point $p$ is $C_{n} a^{n-1}|p|$ with $C_{n}$ constant depending only on the dimension $n$.
I don't know how to prove it, I ...
0
votes
0answers
21 views
Cone in higher dimensions
Let $\Omega$ be a bounded open convex set of $R^{n}$, $u \in C^{0}(\bar{\Omega})$ a convex function, and $v$ a convex function whose graph is the upside down cone with vertex $(x_{0},u(x_{0}))$ and ...
0
votes
0answers
12 views
Finitely generated cone definition clarification
The definition for a finetley generated cone says that a set $C$ is a finetly generated cone if there exists {$x^{(1)},x^{(2)},...,x^{(k)}$} such that $C$ = {$\sum\lambda_ix^{(i)}, \lambda \geq 0$}. ...
2
votes
1answer
37 views
Intuition behind existence of mixed volumes?
Consider "Volume" as a function from set of $d$-dimensional convex bodies to real numbers. This function is homogeneous of degree $d$ (under rescalings of the convex bodies). Minkowski's theorem ...
4
votes
1answer
42 views
Definition of convexity via probability measure
I found this alternative definition of convexity in a set of lecture notes on convex optimization:
A subset $K \subset \mathbb R^n$ is convex if and only if for every probability measure $\mathbb P$ ...
0
votes
1answer
22 views
How to prove $||P_\Omega(v)-P_\Omega(u)|| \le ||v-u||, \forall u,v \in \mathbb{R}^n$?
Suppose $\Omega$ is a closed convex set in $\mathbb{R}^n$. Let $P_\Omega(u)$ represent the projection of $u$ onto $\Omega, \forall u \in \mathbb{R}^n$. That is to say $P_\Omega(u)= \underset{v \in\...
0
votes
1answer
18 views
Given two polytopes $P$ and $Q$, show that $(P^* \times Q^*)^* = P \oplus Q $
Using definitions, I got so far as to express $(P^* \times Q^*)^*$ in the following form:
$$(P^* \times Q^*)^* =
\left\{\,\begin{pmatrix} z^* \\ w^* \end{pmatrix}
\in \mathbb{R}^{d+e}
\,\middle|\,...
1
vote
1answer
24 views
Uniform sampling of convex polytopes: why is it hard?
There is a surprising number of posts asking about the uniform sampling of convex polytopes (e.g. 1, 2, 3), and an equally surprising number of non-answers (e.g. a, b).
From what I have read, this ...
0
votes
1answer
45 views
Separating hyperplane
Let $K_1,K_2$ be disjoint convex sets in $\mathbb C$. Let $z_1\in\partial K_1,z_2\in\partial K_2$ be the minimizers of $\mbox{dist}(K_1,K_2)=\inf{|x-y|}$ where $x\in K_1$ and $y\in K_2$. Is it true ...
0
votes
1answer
15 views
Basic question about definition of random polytopes
I am trying to read about random polytopes, the convex hull of n random points $x_1,\ldots, x_n$ chosen independently inside a convex body $K$ with respect to uniformly distribution. My questions are:
...
0
votes
0answers
15 views
Volume-minimizing symmetric convex body of constant width
If $K$ is any symmetric convex body with ${\rm vol}(K)={\rm vol}(B_1(0))$ where $B_1(0)$ is the unit ball in $\mathbb R^n$, do we always have ${\rm width}(K)\leq{\rm width}(B_1(0))$?
2
votes
0answers
52 views
Finding a counterexample to a claim about nonnegative polynomials
A sketch of the proof of the following statement is in Barvinok's "A Course in Convexity".
Fixing positive integers $k$ and $n$, define $H_{2k,n}$ to be the real vector space of all homogeneous ...
0
votes
0answers
15 views
Classifying Radon partitions in $\mathbb{R}^n$ whose affine hull is $\mathbb{R}^n$
Specifically, I want to determine all distinct "types" of Radon partitions of $n+2$ points in $\mathbb{R}^n$ for which the affine hull is all of $\mathbb{R}^n$. This is a homework question, so I'm ...
1
vote
1answer
28 views
Proof of Kirchberger's Theorem in Convex Geometry
I am having trouble understanding certain parts of the proof of Kirchberger's Theorem, as presented here. Specifically, I am having problems understanding the proof of the following combinatorical ...
0
votes
0answers
17 views
Convex sets of width 1 have segments of length 1 in every direction
A strip of width w is a part of the plane bounded by two parallel lines at distance $w$. The width of a set $X \subseteq \mathbb{R}^2$ is the smallest width of a strip containing $X$. Prove that a ...
1
vote
1answer
63 views
Finding the convex hull of m x n matrices
Given a set of $\mathbb{R}^{m \times n}$ matrices, I would like to find the matrices forming the vertices of their convex hull.
Would this be the same problem as finding the convex hull of a set of ...
1
vote
0answers
56 views
Intersection of any 2 intervals $\implies$ all intervals intersect
Let $\mathscr{F}$ be a finite family of open or closed intervals in the line $\mathbb{R}^1$. Show by an elementary proof (without referring to Helly's theorem), that if any $2$ of the intervals ...
0
votes
0answers
26 views
A more efficient convex hull algorithm
Before I start, I would like to say that this is for a programming project of mine I'm doing but I figured my question is only about the part involving math so here I am.
So in Grahams Scan algorithm, ...
0
votes
0answers
12 views
Mapping between two sets of half spaces
Consider a non-empty, bounded $\mathcal H$-polyhedron described by
$$P = \left\{ x \in \mathbb{R}^n : Ax \leq b \right\}$$
Now I have a linear transformation, $y = B x$, where $B \in \mathbb{R}^{m\...
0
votes
1answer
17 views
Affine space and convex sets in the context of Euclidean space
I am a bit confused as to the relationship between the ideas of vector space, affine space, and convex sets in the context of Euclidean space $\mathbb{R}^d$.
As of now, this is how I see it. $\mathbb{...
0
votes
0answers
31 views
Always a hyperplane through the origin between a point and a convex cone
Let $C$ be a closed convex cone in $\mathbb{R}^d$, that is, a closed convex set $C\subseteq \mathbb{R}^d$, so that for every $x\in C$ and for every $\lambda \ge 0$, the point $\lambda x$ is also ...
1
vote
0answers
41 views
When is the measure of spherical cap large?
It is known that in high dimensions, the measure of the spherical cap is small, due to the measure concentration for the sphere. In particular, we have the following inequality in $n$ dimension:
$$
1-\...
2
votes
0answers
91 views
Proof that makes use of the differentiability of a function and of its convex conjugate
I would like your help to understand what are the crucial assumptions driving the claim reported below.
Let me start with the notation
$\mathcal{Y}\equiv \{1,2,...,M\}$.
$S$ is a random vector with ...
0
votes
1answer
21 views
Asymptotic behaviour of the intersection volume of balls with the same radius
Let $x,y \in \mathbb{R}^n$ be two fixed points. Is there an easy proof of the fact that
$$A(r):=\frac{ \text{Vol}(B(x,r) \cap B(y,r))}{\text{Vol}(B(x,r))}$$
tends to $1$ when $r \to \infty$. I ...
0
votes
1answer
29 views
What is the difference between convex cone and convex hull?
I am reading this definition of convex cone and this definition of the convex hull of a finite set of points and I am in trouble in understanding the difference.
Am I right that, given a set of ...
1
vote
1answer
34 views
What does the set : $\{ (\lambda_1, …, \lambda_n) \in \mathbb{R}_+^n \mid \sum \lambda_i = 1 \}$ represent
What the set :
$$S = \{ (\lambda_1, ..., \lambda_n) \in \mathbb{R}_+^n \mid \sum \lambda_i = 1 \}$$
represent geometrically ?
I tried in dimension $2$ and it seems that I get a triangle. But I ...
0
votes
1answer
44 views
Why is the epigraph of Moreau-Yosida Regularization a projection of a convex set?
The Moreau-Yosida Regularization is given by
\begin{equation}
f_\mu(x) = \inf_y \left( f(y) + \frac{1}{2\mu} \| x - y \|^2 \right).
\end{equation}
We know that $L(x, y) = f(y) + \frac{1}{2\mu} \| x -...
2
votes
1answer
64 views
Algorithms for projecting a point onto the convex hull spanned by a set of vectors
Given a set of vectors $V = \{ \mathbf{v}_1, \ldots, \mathbf{v}_n \} \subset \mathbb{R}^d$, I want to project a point $\mathbf{x}_0 \in \mathbb{R}^d$ onto the convex hull $\text{conv}(V)$ of the ...
3
votes
0answers
67 views
Where to find some subset of Khovanskii's 15 proofs of the BKK theorem?
I'm a fan of the Bernstein-Khovanskii-Kushnirenko theorem (that the number of solutions in $(\mathbb{C}^*)^n$ to a generic system of Laurent polynomials is the mixed volume of the polynomials' Newton ...
