Stack Exchange Network

Stack Exchange network consists of 175 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]

Use this tag when posting questions related to the concept of convexity and geometry. For example, for convex polygons.

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 ...