Questions tagged [convex-geometry]
Use this tag when posting questions related to the concept of convexity and geometry. For example, for convex polygons.
1,163
questions
2
votes
0
answers
39
views
We have two convex sets $S,T$ such that $S\subseteq T$. Prove or disprove that the circumference of $S$ must be smaller than that of $T$. [duplicate]
This question originated from an exercise asking to compare the arclength of $y=x^2$ between $(0,0)$ and $(1,1)$ and $\frac{\pi}{2}$.
The solution starts by constructing the circle with center $(0,1)$ ...
- 21
0
votes
1
answer
44
views
What is a convex combination of graphs?
For example in this paper, they refer to a "convex combination of trees" (pg. 2, first paragraph), and also, more generally, to "convex combination of graphs" (pg. 2, footnote).
-&...
-3
votes
0
answers
19
views
Two questions about Convex Sets [closed]
There are 2 questions that I can't make any idea while solving. Can you give an idea how I can solve it?
For C convex, show that C is closed if and only if C $\cap$ L is closed, for any affine line L?...
0
votes
0
answers
38
views
Sufficient condition for convexity involving an average of slopes
Suppose $h(x)\ge0$ is increasing and concave for all $x\ge0$. For $\Delta>0$, let
$$
f(x)=\frac{h(x+\Delta)-h(x)}{\Delta}.
$$
I feel that $f$ is a convex function, i.e.
$$
f(tx+(1-t)y)\le t f(x)+(1-...
- 285
2
votes
0
answers
16
views
A (sub)neighborhood $S'$ of a set $X^*$ such that the line segment connecting any point in $S'$ and its projection to $X^*$ is contained in $S'$.
Consider a closed set $X^* \subset \mathbb{R}^n$. Let $Proj_{X^*}(x)$ denote the set of metric projections of $x \in \mathbb{R}^d$ to $X^*$:
$$Proj_{X^*}(x) = \arg\min_{x^* \in X^*} d(x, x^*)$$
where ...
- 295
4
votes
0
answers
52
views
If a polyhedron's faces and vertex figures are convex, is the polyhedron convex?
Suppose a polyhedron's faces are convex polygons, and its vertex figures are convex spherical polygons (or convex cones, depending on definitions). Must the polyhedron be convex?
The polyhedron may be ...
- 4,151
0
votes
0
answers
27
views
Is there a characterisation for the convex set which is fully embedded inside a convex polytope?
As per the Krein-Milman theorem, any convex compact set (in a finite-dimensional vector space) is equal to the convex hull of its extremal points.
I am now imposing that a given convex compact set $C$ ...
5
votes
2
answers
142
views
Minimal polytope enclosing a sphere
Given a unit ball in d dimensions (euclidean distance) and an allotment of points $n > d$, can we choose the set of n points such that their convex hull contains the ball and the volume of the ...
- 51
0
votes
2
answers
38
views
When the convex combinations of two vectors are all non-negative?
Let $x=(x_1,\cdots,x_N),y=(y_1,\cdots,y_N)$ be two elements of the Euclidean space $\mathbb{R}^N$. What are the necessary and sufficient conditions on $x$ and $y$ for the following statement to be ...
- 725
1
vote
0
answers
24
views
Closed mid-point convex set and it's usefulness
$(X, \|•\|) $ be any normed space and $E\subset X$ .
$(I)$ For every sequence $(x_n), (y_n) \in E$ with $x_n\to x $ and $y_n\to y $ in the space $(X,\|•\|) $ implies $\frac{x+y}{2}\in E\space \space $...
- 3,929
1
vote
0
answers
48
views
What's the combination of vectors with all coeffiencts between 0 to 1？
Assume a combination of the form:
$\vec{S}=\sum_ip_i\vec{v}_i$ with $0\le p_i\le 1$, what is this combination called?
And considering the set:
$$\mathcal{S}=\{\sum_ip_i\vec{v}_i \mid 0\le p_i\le 1\}$$
...
- 11
2
votes
1
answer
32
views
Some doubts regarding determinant lower bound of linear discrepancy
I am reading the book on Discrepancy Theory by Matousek. A famous theorem of Lovasz et. al. implies the following lower bound on linear discrepancy of a set system. (I am attaching a screenshot of the ...
- 718
0
votes
0
answers
16
views
Generalization of Eaves' Theorem
Let $K\subset \mathbb{R}^n$ be a nonempty convex compact and $f:K\to K$ be a function. Let $g:K\to \mathbb{R}^n$ be $g(x)=f(x)-x$. Is there always a point $x_0\in K$ such that for all neighbourhood $U\...
- 425
1
vote
1
answer
52
views
Maximize the trace of the convariance of a bounded random vector
Given a random variable $X$, satifying $P(0\leq X \leq 1)=1$, and $\mathsf{E}[X^2] = \alpha$. We know its maximum variance $\text{Var}(X) = \alpha(1-\alpha)$ achived by a binary random variable $P(X =...
- 23
-5
votes
2
answers
73
views
Concavity of the function $|f|$ , while $f$ is concave [closed]
Prove or disprove, "if $f$ is concave function, then $|f|$ is also concave".
I know the result is false for conves function, but for concave function, I guess it is true. But I am unable to ...
- 12.3k
1
vote
1
answer
42
views
Support cones and linear functionals
Let $S\subset\mathbb{R}^n$ be any set. A convex cone $C$ with apex $a$ and non-empty interior is a support cone of $S$ at $a$ if
i) $a \in S,$
ii) $S \subset (\text{int} \;C)^{\complement}$ (i.e ...
- 107
0
votes
0
answers
27
views
Probability of convexity of a polytope in $\mathbb{R}^2$ and possibly $\mathbb{R}^3$?
I have had this question burning in my mind for awhile and was wondering if a more experienced geometer, statistician or probability theorist has any insight:
Given the facets of a polytope in $\...
- 39
1
vote
0
answers
39
views
Separation of polyhedra via Farkas' lemma
Let $A\in\mathbb{R}^{m_1\times n}$, $B\in\mathbb{R}^{m_2\times n}$, $a\in\mathbb{R}^{m_1}$, and $b\in\mathbb{R}^{m_2}$. Consider the intersection of an "open" polyhedron and another closed ...
- 11
3
votes
0
answers
71
views
Show that the image of the given function is convex
Define a function $f: [-b,b]^d\mapsto \mathbb{R}^d (d>1)$ by
$$ f(x)=\int_{[-a, a]^d} \frac{u}{1 + \exp(u^\top x)}du $$
Can we show that the image of $f$ is a convex set? I did some simulations ...
- 1,283
0
votes
2
answers
56
views
Strictly convex function proof
Is the following function strongly convex for $x\succeq 0: \sum_{i} x_i = 1$ and $c_i > 0$ for $i\neq 1$?
$$
f(x) = \max_{i\neq 1}f_i(x) = \max_{i\neq 1}\frac{\frac{1}{x_1} + \frac{1}{x_i}}{c_i}.
$$...
- 248
1
vote
0
answers
33
views
A question regarding the proof of Lévy–Steinitz theorem
I am reading the proof of Lévy–Steinitz theorem from ON THE POWER OF LINEAR DEPENDENCIES, which asserts that given a finite set $V$ of the unit ball $B$ of any norm(in $\mathbb{R}^d$) such that $\...
- 718
0
votes
0
answers
66
views
Statement of Kakutani's Theorem on Convex Bodies
In this paper we find a proof that for every continuous function $f:S^n\to\mathbb{R}$ there exist $n+1$ pairwise orthogonal points $x_0$ through $x_n$ such that $f(x_0)=f(x_1)=\cdots=f(x_n)$. They ...
- 1,569
0
votes
1
answer
46
views
Show that $\min\{\lambda≥0:x\in\lambda K\}=h(K^{*},x)$
Let $K\in\mathscr{C}^n$ with $\overrightarrow{0}\in$ int$K$ and let $h(K,\cdot)=\sup\{<x,y>:y∈ K\}$ be the support function. Also, for $\overrightarrow{x}\in\mathbb{R}^n$ we define $$|\...
- 248
0
votes
1
answer
36
views
Construct $(P^*)^*$ for a polyhedron
I am trying to solve the following problem:
Consider the polyhedron
$P = \{x\in \mathbb{R}^3 \mid x_1 + x_2 + x_3 \geq 1, x_j \geq 0 \; j \in [3] \}$.
The polar of a set $S$ is defined as $S^* := \{y\...
- 109
0
votes
0
answers
19
views
Distance between two closed convex bounded non-empty subsets in a CAT(0) space
Let $(X,d)$ be a complete CAT(0) space, where $d$ is the metric on the space $X$. Being CAT(0) here means that for any $x,y\in X$, there is some $m\in X$ such that for any $z\in X$, we have the ...
- 33
0
votes
1
answer
13
views
Is the intersection of quasi convex sets also quasi convex?
A subset $A$ of a geodesic space $X$ is called quasi convex if there exists a constant $k > 0$ so that if $x,y \in A$, the geodesic joining $x$ to $y$ is in the $k$ neighborhood of $A$. Is it true ...
- 392
0
votes
0
answers
59
views
How to check whether a point is inside the black regions or not?
I have a huge map which is similar to bellow,
Problem:
I want to find feasible path between two points in the map. Since size of map is huge it takes enormous time to calculate the path. The ...
- 139
1
vote
1
answer
38
views
Efficient algorithms for testing simplicity of a 2D polygon given its vertices?
I'm working on a project that requires me to test if a polygon is convex and I was able to write an algorithm that successfully tests for convexity for simple polygons but fails to provide the correct ...
1
vote
1
answer
16
views
How to prove an inequality of gauge norms?
Let $A$ be a compact convex set in $\mathbb R^n$. Let $y\in \mathbb R^n$ be an arbitrary point not belonging to $A$. Let $P$ be a hyper-plane which separates $A$ and $y$. Let $x$ be the projection of $...
- 1,208
0
votes
0
answers
23
views
Can a union of $k$ half spaces be partitioned into $O(k)$ disjoint convex polyhedrons?
Suppose $S=\bigcup_{i=1}^k S_i$, where $S_i=\{x\in \mathbb{R}^d|a_i^Tx\le b_i\}$ is a half space. Can we partition $S$ into $k$ disjoint convex polyhedrons?
With the $k$ inequalities defining the $S_i$...
- 49
0
votes
0
answers
15
views
Range of z for convex constraint?
What would the range of z be if this were to be a convex constraint?
$2x_1^2 + (2+z)x_2^2 - x_3^2 \leq 5$
I thought it could be approached by applying the two conditions of a convex hull (i.e, the ...
- 1
0
votes
0
answers
50
views
Name for a closed shape that has an interior point such that every line through the point meets the shape's boundary at exactly $k$ distinct points?
Consider a closed shape/set $S \in \mathbb{R}^2$ such that there exists an interior point $(x, y) \in S$ (need not be unique) such that any line passing through $(x, y)$ intersects $S$'s boundary at ...
- 1
3
votes
1
answer
50
views
Two convex sets with same Lebesgue measure of projection at any direction
This question comes from my real analysis class.
For any $v=(\cos\theta,\sin\theta) ,\theta\in[0,2\pi)$, let $\pi_{v}(x)=\langle v, x\rangle .
$
Let $A, B$ be two bounded open convex sets in $\mathbb{...
- 31
1
vote
1
answer
48
views
Does the closed convex hull of a compact set in the interior of a convex cone is still contained in the interior of the cone?
Let $C$ be a convex cone in a Banach space $X$ with nonempty interior. The set $A\subset {\rm Int}C$ is a compact subset, where ${\rm Int}C$ means the interior of $C$. Denote the closed convex hull of ...
- 23
0
votes
0
answers
28
views
Are half spaces in Hadmard manifold geodesically convex?
Given a Hadamard manifold $M$ (complete, simply connected and of nonpositive curvature) and two points $x,y\in M$ I want to consider the half space $H(x,y)=\{z\in M\mid d(x,z)\leq d(z,y)\}$. I wonder ...
- 1
3
votes
0
answers
123
views
A linear system optimization
Let $A: \mathbb{R}^n \to \mathbb{R}^d$ be a matrix.
Let
$$\max_{\|y\|_2 \leq 1 } \min_{\|x\|_2 \leq R}\|Ax-y\|_2 = \epsilon\;.$$ (where $R$ is the radius of the norm ball that $x$ is constrained to).
...
- 395
4
votes
1
answer
73
views
Geometry Question: A property of a convex polyhedron.
I'm trying to interpret a verified solution for the following problem.
Show that $v_3+f_3>0$.
Here, $v_n$ denotes the number of vertices of a convex polyhedron that meet with $n$ edges, and $f_n$ ...
- 1,248
3
votes
1
answer
71
views
Projection of $\lambda y$ onto a polytope is fixed for sufficiently large $\lambda$?
Le $y\in \mathbb R^n\setminus\{0_n\}$.
Let $X\subset \mathbb R^n$ be a compact polytope (intersection of finite half-spaces).
For a sufficiently large $\lambda\in \mathbb R_+$, I have the impression ...
- 1,208
0
votes
0
answers
51
views
Is minimum of two convex functions also convex? [duplicate]
We are provided with two convex functions f(x) and g(x) and we are supposed to comment on the convexity of min{f(x),g(x)}.
I start out by writing the equations implied when we convexity of f(x) and g(...
2
votes
2
answers
83
views
Proof of Straszewicz's theorem
I'm interested in the following result, known as Straszewicz's theorem:
(1) For $C$ a compact convex set, the set of exposed points $\text{exp}\ C$ is dense in the set of extreme points $\text{ext}\ ...
- 3,989
1
vote
0
answers
16
views
Convex description of the positive orthant without the y-axis
I know that the following set is convex
\begin{equation}
X = \{(x,y) \in \mathbb{R}^2 : x>0 ,~ y\geq0 \}~ \cup~\{(0,0)\}
\end{equation}
i.e. the positive orthant without the y-axis but with the ...
- 15
3
votes
2
answers
57
views
Interior points in a convex set can be represented as convex combination of different points from the set
Can we assume that any interior point $z$ in a convex set $S\subseteq R^n $ be represented by $2$ points $x \in S$ and $y \in S$ such that $z = \lambda x +(1-\lambda)y $, where $x\neq y \neq z$ , and ...
- 33
1
vote
1
answer
63
views
"Convexity" of a family of distributions
Let $\alpha\in(0,1)$. Consider a family of CDFs $\mathcal{X}$ that contains every CDF $X$ defined on $[0,\infty)$ with increasing hazard rate (IHR) which satisfies $$\mathbb{P}[x>y]=\alpha,$$ where ...
- 175
1
vote
0
answers
21
views
Membership Oracle (MO) for $K+\epsilon B$ given MO for $K$ [closed]
Let $K$ be a convex compact set in $\mathbb{R}^d$. Suppose that a Membership Oracle $\mathcal{M}_{K}$ for the set $K$ is available; given a point $x\in \mathbb{R}^d$, the Oracle returns ''true'' if $x$...
- 317
1
vote
0
answers
41
views
Request detailed explanation about Stephen Boyd cvxbook-solutions-manual exercise 2.8(a) expressing a set S in the form S = {x | Ax<=b, Fx = g}
cvxbook-solutions exercise page-5 exercise 2.8(a)
2.8(a)
$S = \{y_1a_1 + y_2a_2 | − 1 ≤ y_1 ≤ 1, − 1 ≤ y_2 ≤ 1\}, \text{where }a_1, a_2 ∈ R^n$.
The following is the solution mixed with my question.
...
- 77
0
votes
0
answers
14
views
Parametrize continuous deformation from one convex body to another
Suppose one has a continuous deformation, $Z(s)$, from an initial zonotope $Z(0)=Z_0$ to a final one $Z(1)=Z_f$, such that $Z(s)\subset Z(s^\prime)$ whenever $s<s^\prime$. I need to define ...
- 65
0
votes
0
answers
19
views
What are the extreme rays of this cone?
I have given the following cone:
$P=\lbrace x | Ax \geq 0\rbrace$ where $A=\begin{pmatrix}
-1& 1 & 0 & 0 & 0&0\\
0& -1 & 1 & 0 & -1 & 0\\
0 & 0 & -1 &...
- 578
0
votes
0
answers
26
views
Best way to describe distance from surface point to projected interior point
Is there a better way to describe the following idea in words? I've been really struggling. My first thought is to call this "skewness" but I don't know where I got that from and it might ...
- 2,058
0
votes
0
answers
25
views
Show that the $l_1$ ball is a convex set based on the convexity of polytope
$P$ is defined as the set of points $x \in \mathbb{R}^d$ satisfying the following constraints: for an integer $m > 0$, for $m$ vectors $a_1, ..., a_m \in \mathbb{R}^d$ and $m$ values $b_i \in \...
- 43
2
votes
2
answers
71
views
Are these two "Mazur's" theorems the same?
According to Royden:
Mazur's Theorem: Let $K$ be a nonempty convex subset of a normed linear space $X$; $K$ is strongly closed if and only if it is weakly closed.
According to Wikipedia:
Mazur's ...
- 8,284