Questions tagged [convex-geometry]
Use this tag when posting questions related to the concept of convexity and geometry. For example, for convex polygons.
476 questions
0
votes
0answers
10 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
8 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\...
-2
votes
0answers
17 views
How does the polar set of the Reuleaux triangle look like? [on hold]
How does the polar set of the Reuleaux triangle look like?
Is it a disk-polygon? Which one?
0
votes
1answer
14 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
23 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 ...
0
votes
0answers
26 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
65 views
+50
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
18 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
18 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
32 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
37 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
41 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
64 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 ...
1
vote
0answers
28 views
Polytopes given by affine relations of their vertices
This is a reference request for a description of polytopes by affine relations of their vertices. Let me give a few examples of what I'm looking for:
Taking $n+1$ points $a_0,\dots,a_n$ in $\Bbb R^d$ ...
0
votes
0answers
20 views
Quasiconvexity + X implies convexity
Given a continuous function $f$ that is quasi-convex over some interval $[a,b] \subset \mathbb{R}$, what are examples of additional (sets of) properties (themselves weaker than convexity) that ensure ...
1
vote
1answer
44 views
How to show maximizer of an inner product over a convex set happens on the boundary? [closed]
Let $C$ be a convex set and $y \in \mathbb{R}^n$ a given point.
Show that when $y \in \mathbb{R}^n$ is not in $C$, the maximizer of the following problem has to be on the boundary of $C$:
$$
x_* = \...
2
votes
0answers
154 views
Normal of a supporting hyperplane contained in the normal cone of a vertex
Given a vertex $v$ of a polytope P defined by the intersection of $n$ linearly independent hyperplanes with normals $v_1, \ldots, v_n$ and a supporting hyperplane $c^Tx \leq d$ that passes through $v$,...
5
votes
2answers
243 views
Prove that 0 is in the convex hull of points chosen from each orthant
If we arbitrarily choose a point from each orthant in $\mathbb{R}^n$, that is we choose $2^n$ points in total, how do we prove that 0 is in the convex hull of these $2^n$ points? It seems obvious, but ...
0
votes
1answer
35 views
A theorem about convex function
Assume that function $h(x)=f(ax+b)$ is a convex function. What can we say about the convexity of function $f(x)$?
My notes:
By taking the second derivative from both sides of eqaution $h(x)=f(ax+b)$ ...
0
votes
0answers
27 views
A question about convex bodies
I have been trying to prove that if we have $K\in\mathcal{K}^n$(convex body) centrally symmetric and $H_c=\{x\in\mathcal{R}^n:\langle x,u\rangle=c\}$, where $u\in\mathcal{R}^n$. Then $\text{vol}_{n-1}(...
1
vote
1answer
52 views
Maximize $b^Tx$ subject to $x \in C(a) := \{x \in \mathbb R^p | \|a+x\|_2 \le r,\;\|x\|_\infty \le \epsilon\}$
Let $r,\epsilon > 0$ and $a, b \in \mathbb R^p$ with $\|a\|_2 \le r$. Define the set $C(a) := \{x \in \mathbb R^p | \|x+a\|_2 \le r,\;\|x\|_\infty \le \epsilon\}$. Note that $C(a)$ is non-empty (it ...
0
votes
0answers
5 views
Bounds on maximum distance diameter computed with different norms
Let the $\ell_p$ (maximum distance) diameter of a convex polytope defined by $Ax\leq b$ be
$\max_{x,y} \|x-y\|_p$ subject to $Ax\leq b, Ay\leq b$.
Suppose we take the $x, y$ thus found and ...
1
vote
2answers
69 views
What is the difference between a unit simplex and a probability simplex?
The unit simplex is the $n$-dimensional simplex determined by the zero vector and the unit vectors, i.e., $0,e_1, \ldots,e_n\in\mathbf R^n$. It can be expressed as the set of vectors that satisfy
$$...
0
votes
1answer
40 views
How can I prove that $\mathbb{S}_{+}^n$ is a closed and convex set?
$\mathbb{S}_{+}^n$ is the set of positive semidefinite (and symmetric) real matrices of size $n\times n$. I have to prove that this set is a closed convex cone. How can I do?
2
votes
1answer
46 views
Sums of unit vectors contained in a half-space
Consider $n$ unit vectors $\{v_1,...,v_n\}$ with $v_i\in \mathbb{R}^3$. Now define
$\text{H}(w):=\{w'\in\mathbb{R}^3 \ | \ (w',w)>0\}, \ w\in\mathbb{R}^3$
(where $(\cdot,\cdot)$ is the standard ...
0
votes
0answers
29 views
Find vertices of a Voronoi diagram of convex polygons
From a set of polygons guaranteed to be :
Convex
Full (no holes)
Non-intersecting (polygons may share edges/points, but not penetrate each other)
How do I find the vertices of the Voronoi diagram ...
2
votes
1answer
22 views
How to prove normal cones are closed?
Let $C$ be a convex subset of $\mathbb{R}^{n}$ and let $\bar{x} \in C$. Then the normal cone $N_{C}(\bar{x})$ is closed and convex. Here, we're defining the normal cone as follows:
$$N_{C}(\bar{x}) =...
1
vote
1answer
25 views
Permutahedron of three vectors (1,1,0,0), (−1,1,0,0), (−1,−1,0,0).
I'm getting stuck on parts b, c, and d. Since visualizing the polytope is not possible, I think the way to find the facets and edges of P is to determine which combinations of points form facets and ...
3
votes
3answers
147 views
Product of two polytopes is a polytope
Please have a look at my attempt for this problem.
Let $x = \begin{pmatrix} x_1\\ x_2 \\ \end{pmatrix}, x_1 \in P_1, x_2 \in P_2$.
I want to show that $x \in conv\{P_1 \times P_2\}$, i.e. $x$ can be ...
2
votes
1answer
49 views
How to prove that continuous convex functional on normed vector space must be lower bounded by some continuous affine functional?
Let $X$ be a normed vector space. Let $f:X\mapsto \mathbb{R}$ be a continuous convex function. How to show that there exists a continuous linear functional $l$ and a constant $c\in\mathbb{R}$ such ...
1
vote
1answer
20 views
convex polygon considering three angles
If I choose three vertexes A,B,C in a convex polygon, it so happens that the sum of angleA,angleB,angleC appears to be 180 or larger. Why is this true? I tried drawing the polygon and making triangles,...
0
votes
1answer
53 views
A doubt from the paper “Newton-Okounkov bodies, semigroups of integral points, graded algebras and intersection theory”
I am currently reading the paper "Newton-Okounkov bodies, semigroups of integral points, graded algebras and intersection theory" by Kiumars Kaveh, Askold Georgievich Khovanskii (paper). In the page ...
0
votes
1answer
34 views
Angles of convex polygons
For a convex polygon, show that the sum of any two interior angles is greater than the difference between any two interior angles. (the polygon has more than 3 sides)
If I pick 4 dots A,B,C,D and say ...
1
vote
0answers
26 views
Guarantee strict convexity at a point
Suppose we have a univariate function $f(t), t\in [0,1]$. We define
\begin{align}
G(p) = \sup_{t\in [0,1]} p f(t) + (1-p) f(1-t), \text{ for } p\in [0,1].
\end{align}
Clearly $G(p)$ is a convex ...
1
vote
1answer
52 views
How to show directly that finitely generated cone contains polyhedral cone of nonnegative vectors?
Let $P=\{x \in \mathbb{R}^n \mid Ax \geq b, x \geq 0 \}$ be a nonempty polyhedron for matrix $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$.
According to Minkowski-Weyl theorem $P$ can be ...
2
votes
1answer
61 views
How to show polyhedral cone of nonnegative vectors contains finitely generated cone?
Let $P=\{x \in \mathbb{R}^n \mid Ax \geq b, x \geq 0 \}$ be a nonempty polyhedron for matrix $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$.
According to Minkowski-Weyl theorem $P$ can be ...
2
votes
1answer
42 views
What is the convex hull of $\text{conv}(u_1,u_2,\cdots,u_p)+\text{conv}(v_1,v_2,\cdots,v_s)$?
Let $u_i, i= 1,\cdots,p$ and $v_j, j= 1,\cdots,s$ be finitely many vectors in $\mathbb{R}^n$. Show that
$$
\text{conv}(u_1,u_2,\cdots,u_p)+\text{conv}(v_1,v_2,\cdots,v_s)=\text{conv}\{u_i+v_j \mid i=...
1
vote
0answers
37 views
Convex piecewise linear functions - partitioned vs max representation
I know that convex piecewise linear function $f$ can be defined in two closely related ways -
There exist $Q \subseteq P(X)$ s.t. $\bigcup Q = X$ and on every $A \in Q$ the function is linear (...
3
votes
1answer
48 views
Why can't a vertex of a $d$-dimensional polytope be in fewer than $d$ edges?
This is motivated by the definition of simple polytopes: if all vertices of a $d$-dimensional convex polytope $P$ are in exactly $d$ edges (i.e. $1$-dimensional faces of $P$), then $P$ is simple.
I ...
2
votes
1answer
50 views
Show that $\prod_K(x)+\prod_{-K^*}(x)=x$ $\forall x \in \mathbb{R}^n$where $K$ is a cone in $\mathbb{R}^n$.
Let $K$ be a closed convex set in $\mathbb{R}^n$, $K^*$ be the dual cone of $K$, and $\prod_K(x)$ denote the Euclidean projection onto $K$.
Show that $\prod_K(x)+\prod_{-K^*}(x)=x$ $\forall x \in \...
1
vote
1answer
77 views
Show minimum distance to a convex set is a convex function.
Show that
$$
g(x)=\inf_{z \in C}\|x-z\|
$$
where $g:\mathbb{R}^n \rightarrow \mathbb{R}$, $C$ is a convex set in $\mathbb{R}^n$ (nor close neither bounded), and $\|\cdot\|$ is a norm on $\mathbb{R}^...
0
votes
1answer
42 views
Do $|f'|$ and $f$ have the same minimisers for strictly convex functions?
Call the differentiable function $f: \mathbb K \to \mathbb R$ on some compact convex $K \subset \mathbb R^n$strictly convex to mean $f(\lambda x + (1- \lambda)y) < \lambda f(x) + (1-\lambda)f(y)$ ...
2
votes
0answers
17 views
Can a Jordan convex curve be rewritten as the image of 4 monotone real functions?
Is it true that a smooth Jordan curve $C \subseteq \mathbb{R}^2$ that is convex (in the sense that the region bounded by this curve is convex) can be rewritten as the union of the image sets of 4 ...
0
votes
0answers
30 views
Why cones are represented by matrices
I see there are multiple definitions of cones:
1) Cone $K$ is defines as a set of vertices $[x_1, x_2, x_3, ...]$ with $[0]$ as the base (starting point)
2) Cone $K$ is defined as intersection of ...
1
vote
0answers
11 views
How to maintain concavity while normalising a set of samples?
I have a set of 2D samples that approximate a geometric shape that I am trying to construct. Due to measuring errors some samples are slightly off, generating "jaggy" artifacts in the surface of the ...
4
votes
0answers
29 views
For two polytopes $A$ and $B$, when can we find $C$ such that $A=B+C$?
$A\subset\mathbb{R}^d$ is a polytope if $A$ equals the convex hull of some finite set.
For any two sets $B$ and $C$, $B+C\equiv\{x+y:x\in B,y\in C\}$.
My question:
Let $A$ and $B$ be polytopes in $\...
3
votes
2answers
62 views
Why is $\alpha^n\beta^m+\alpha^m\beta^n\le\alpha^s\beta^t+\alpha^t\beta^s$ if $(n,m)\preceq(s,t)$?
I've recently come across the following statement:
$$\alpha^n\beta^m+\alpha^m\beta^n\le\alpha^s\beta^t+\alpha^t\beta^s$$
for $\alpha,\beta\ge0$, $n,m,s,t\in\mathbb N_+$, $n+m=s+t$, and $(n,m)\preceq(s,...
1
vote
1answer
17 views
Prove that the normal cone $N_{\text{gph}(f)}$ of the graph of the affine function $f$ has the given form.
GIVEN
Let $f : \mathbb{R}^n \longrightarrow \mathbb{R}^m$ be the affine function defined by $f(x) = Mx + b$ where $M$ is an $m \times n$ matrix and $b$ is a vector in $\mathbb{R}^m$. Prove that for $(...
0
votes
2answers
46 views
Find the convex subdifferential $\partial d_K$ of the distance function $d_K$ associated to a convex set $K$ at in-set points $x_0 \in K$.
GIVEN
Let $K \subset \mathbb{R}^n$ be a nonempty, closed and convex set. The associated distance function is $d_K$. Find the subdifferential $\partial d_K(x_0)$ for all $x_0 \in K$.
USEFUL ...
1
vote
0answers
39 views
Determine the normal and tangent cones $N_C (x)$ and $T_C (x)$ for all $x \in C$.
GIVEN
Let $C = \{ x \in \mathbb{R}^n : Ax=b \}$, where $A$ is an $m \times n$ matrix and $b \in \mathbb{R}^m$.
Determine the normal cone $N_C(x)$ and $T_C(x)$ for all $x \in C$.
USEFUL ...
