Questions tagged [convex-hulls]

For questions on the convex hull of a set, a set $X$ of points in a Euclidean space which is the smallest convex set that contains $X$. Consider adding (convex-analysis), or, for questions related to algorithms, (computational-geometry) and/or (discrete-geometry).

Filter by
Sorted by
Tagged with
1
vote
0answers
17 views

Algorithm to find convex hull from linear constraints

Given a set of linear constraints $A_{in} x \leq b_{in}$ and $A_{eq} x = b_{eq}$ (with $x \in \mathbb{R}^n$) is there any algorithm to obtain the vertices of the convex hull generated by these ...
1
vote
1answer
41 views

Convex hull of the set of distributions with constant entropy

Let $H(p):=-\sum_{i=1}^n p_i \log p_i$ be the Shannon entropy defined on the set of probability distributions on $\{1,2,...,n\}$. Let $h$ be a constant such that $0\leq h \leq \log n$. The question is:...
0
votes
0answers
19 views

Convex sets and their extreme points

Let $C\subseteq \mathbb{R}^d$ be a convex set and let $M$ be the set of extreme points of $C$ (and thus $C$ is the convex hull of $M$). Let $S\subseteq \mathbb{R}^d$ be another convex set. It is known ...
0
votes
2answers
26 views

Inclusion of polytopes

Let $C_{1}$ and $C_{2}$ be polytopes in $\mathbb{R}^{n}$ such that $C_{1}=conv\left( V\right) $ with $V$ being a set of vertices. If $V\subseteq C_{2}$, my question is $C_{1}\subseteq C_{2}$?
3
votes
1answer
82 views

Does connecting any two points in a graph result in a convex set? [closed]

This is a follow-up question. Let $F:[0,1] \to [0,\infty)$ be a continuous function, and let $G=\{ (x,F(x))\,|\, x \in [0,1] \}$ be the graph of $F$. Is $\cup_{(x,y)\in G^2} [x,y]$ convex?
0
votes
1answer
28 views

Does connecting any two points in a set result in a convex set?

This might be silly, but I am not sure. Let $A \subseteq \mathbb R^2$. Suppose that for any two points $x,y \in A$, I "add" the straight segment $[x,y]$ between them. Is the result convex? That is, ...
1
vote
1answer
22 views

Convex hull as intersection of affine hull and positive hull

For a set $S\subseteq\mathbb R^m$ we denote with $pos(S)$ the set \begin{equation} \{\alpha_1x_1+\cdots+\alpha_nx_n:\alpha_i\geq 0,x_i\in S, n\in\mathbb N\}. \end{equation} How to prove that $conv(S)=...
1
vote
0answers
31 views

Haar measure on unit sphere

I am reading a paper where weak solutions to the Euler equations should be found by using the concept of convex integration. Therefore the proofs are very short and I've got some problems ...
0
votes
2answers
50 views

How to prove that the expectation of a random vector lies in the convex hull of its support?

Let $Y$ be a nonnegative random random variable on some probability space, and Let $F:[0,\infty) \to \mathbb R$ be continuous function. How to prove that the "vector expectation" $(E(Y),E(F(Y)))$ ...
0
votes
0answers
6 views

Approximation of convex hull by projecting points to four planes and then taking their supeposition? How does it work?

Anyone understand more generally the idea used to approximate convex hull of a tree top shape in this paper: At first, the crown points were projected onto four vertical planes through the ...
0
votes
0answers
22 views

How do I prove that the intersection of two convex polyhedra is a convex polyhedron?

I'm studying about convex geometry, and that is my problem. for more details: A polyhedron is a convex hull of finite points. P is a polyhedron then P := conv{x1,..,xn}
0
votes
0answers
10 views

Bound Volume of Convex Hull

Suppose I have some multidimensional volume parameterized by $f(\theta)$ where $\theta$ is a vector and $f$ returns a perhaps different dimensional vector. Is there a way that I can upper bound the ...
0
votes
1answer
35 views

Proving a set is a convex hull of another set

I need to prove that the convex hull of the finite set: $$S= \{x\in\{0,1\}^d|\left\Vert x \right\Vert_0\leq k\}$$ is the set: $$T=\{x\in\left[ 0,1\right]^d|\left\Vert x \right\Vert_1\leq k\}$$ ...
0
votes
0answers
20 views

Why is $\operatorname{aff}(B(x,r))=R^n$?

Why is $\operatorname{aff}(B(x,r))=\mathbb R^n$ ? $\operatorname{aff}$ means hull affin. $B(x,r)$ means ball in $\mathbb R^n$.
0
votes
1answer
38 views

Can we say that: $ cl\big(\text{co}\cup_{k\geq n}{\frac{1}{k}A}\big) $ is weak compact?

Let $(X,\|.\|)$ be a separable Banach space and $A$ be a nonempty weak compact convex subsets of $X$. Let $n\geq 1$. Can we say that: $$ cl\big(\text{co}\cup_{k\geq n}{\frac{1}{k}A}\big) $$ is weak ...
0
votes
0answers
21 views

Separation Theorem (Hyperplanes)

Given the "Separation Theorem I" in Hyperplane Separation Theorem Let A and B be two disjoint nonempty closed convex sets, one of which is compact. Then there exist a nonzero vector v and real ...
2
votes
0answers
23 views

Dimension of Minkowski Sum of in Lp space

Let $X$ be a $d$-dimensional subspace of $L^1([0,2])$, let $X_i:=\left\{ f \in L^1([0,2]):\, f =gI_{[i,i+1]} ,\, g\in X \right\}$, for $i=0,1$, essentially supported on $[0,2]$. Then, if I'm not ...
0
votes
1answer
49 views

Convex hull that maximizes number of covered points

There is a set $A$ of 2D points, $|A| = m$. My task is to find a subset $B \subset A$, $|B| = n$, such that the convex hull based on $B$ minimizes the number of points from $A$, that do not lie in ...
0
votes
0answers
28 views

extreme points of a convex set spanned by a set of points in high dimension

Let's say I have a set of 1000 points in 25-dimensional space. I know this set of points generates/spans a convex set in 25-dimensional space. I would like to know which of these points are extreme i....
0
votes
0answers
30 views

Computing the set of integral points of a convex hull

Assume that we have integral points $x_1, \ldots, x_n \in \lbrace 0, \ldots, l - 1 \rbrace^3$ for some $l \in \mathbb{N}_{> 0}$, that the vertices of the associated convex hull are given by $v_1, \...
2
votes
0answers
48 views

Diameter of a convex hull (S) = diameter (S)

$\DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\co}{co}\DeclareMathOperator{\Aff}{Aff}$ Let be $E$ a normed vector space (non-Banach). $S \subset E$ bounded. Remember that $\diam(S) = \sup \{\...
0
votes
1answer
27 views

How can I find a strictly convex subset of a given convex set?

At a high level, I am trying to approximate a convex set $C$ with a strictly convex subset that is an arbitrarily "close" approximation of $C$. (Recall that a set $B$ is strictly convex if for all $\...
0
votes
2answers
30 views

Why is that linear combinations of coefficients with sum 1 give a line?

In case of $$p = t\cdot p_1 + (1 - t) \cdot p_2, \text{ for } p_1, p_2 \in \Bbb R^2, t \in [0, 1]$$ the end of vector $p$ will always land on the line between the endpoints of $p_1$ and $p_2$. Is ...
1
vote
1answer
46 views

Dimension of intersection of affine subspaces

As an assignment we are to calculate the dimension of the intersection of two affine subspaces $A$,$B$ in $\mathbb{R}^6$ each defined by a system of linear equations of at most 6 variables and a ...
0
votes
0answers
7 views

Characterising extreme points of a set of functions in terms of the extreme points in their codomain

Let $C$ be a convex and compact set, and assume moreover that $C$ is the closed convex hull of its set of extreme points $ex_C$. Let $I$ be any set and $C^I$ the set of functions from $I$ into $C$ ...
1
vote
1answer
24 views

Determine the convex hull of a set

Determine the convex hull of $$V=\{(x,y,0): x^2 + y^2 = 1\}\cup \{(1,0,z): |z| \leq 1\}$$ By drawing a picture, I conjectured that $$Conv(V) =\{(x,y,z): (x-|z|)^2 + y^2 = (1-|z|)^2, |z| \le 1\}=: ...
-1
votes
1answer
43 views

Convex Hull of Unit Circles

I know that if we're trying to get the convex hull of $n$ unit circles, we can simply shrink the circles down to their centers and consider the convex hull of their centers, but I'm trying to prove ...
1
vote
1answer
44 views

Convex hull of compact set is compact in finite dimensional complex vector spaces.

I am wondering whether Caratheodory's convexity theorem extends to finite dimensional vector spaces over the complex numbers. Really, I am trying to prove that the convex hull of the set of ...
2
votes
2answers
65 views

Given $A$ a convex set of $\mathbb{R}^n$ such that $int(A) \neq \emptyset$, prove that $int(cl(A)) = int(A)$.

I was given this problem and I'm struggling with the $int(cl(A)) \subseteq int(A)$ contention. The other contention is trivial and is true regardless of whether $A$ is convex (that is that the line ...
1
vote
0answers
35 views

linear independence, convex hull, and cone

I am trying to show that for any set, $A\neq \{ 0\}$ and any $x\in co(cone A) \subset \mathbb{R^n}$, there exists linearly independent set $A' \subset A$ such that $x\in co (cone A')$. Here, co(A) ...
1
vote
1answer
67 views

Convex hull and projective matrices

If $\mathcal{A}$ is a unital $C^*$-algebra then I want to show that $\operatorname{conv}(\operatorname{Proj}(\mathcal{A}))=\mathcal{P}_1(\mathcal{A}):= \lbrace x \in \mathcal{A^+} : \Vert x \Vert \...
4
votes
1answer
51 views

Is the convex combination of a convex and strictly convex set, strictly convex?

Let $S \subset C \subset \mathbb{R}^d$ be two subsets of $\mathbb{R}^d$, one included in the other. For the sake of simplicity, assume that they are both compact and $\boldsymbol{0}$ belongs to both ...
0
votes
0answers
28 views

Mid-convex functions and convex envelop

Let $X$ be a Banach space. Let $f:X\to\mathbb R$ be a positive function such that there exist $\varepsilon,\alpha>0$ such that for all $x,y\in X$ with $\|x-y\|>\varepsilon$, one has that $f(\...
2
votes
1answer
19 views

Locally mid-convex functions

Let $f:\mathbb R\to\mathbb R$ be a function such that it exists an $\varepsilon>0$ such that for all $x,y\in \mathbb R$ with $|x-y|>\varepsilon$, one has that $f(\frac{x+y}{2})\leq\frac{f(x)+f(y)...
1
vote
1answer
64 views

uniform bound on derivative of convex functions

Let $f$ and $g$ be smooth convex functions, let $h_{\alpha}$ be family of smooth convex functions satisfying the inequality $$f(u)\leq h_{\alpha}(u) \leq g(u) \text{ for all }\alpha \in \textit{F},u \...
2
votes
1answer
35 views

Can there be a convex hull for a non-convex set?

Is it necessary that convex hulls can exist only for convex sets or can it exist for non-convex sets too? For example, see the picture here (Don't have enough reputation to post images). The left set ...
2
votes
0answers
61 views

Expected volume of a normal simplex [duplicate]

Suppose $X_1, ... , X_{n+1}$ are $n$ i.d.d. random points in $\mathbb{R}^n$ with distribution $N(0, I)$ (multivariate normal with zero mean and identity covariance matrix). Suppose $C$ is the convex ...
0
votes
1answer
36 views

Vertices of a convex set

Let $C$ be a convex set in $\mathbb{R}^{n}$ defined by the system of inequalities $Ax\leq b$, where $x\in\mathbb{R}^{n}$ and $b\in\mathbb{R}^{m}$, with $m>n$. My question is the following: a ...
0
votes
0answers
29 views

Big-O Notation as a hull operator?

I have to prove the following: Let $F \subseteq \mathbb{R}^\mathbb{N}.$ Define: $ { \mathcal{O} (F) = \{ g : \mathbb{N}}\rightarrow > \mathbb{R}| \exists f \in F\exists C>0\exists n_0 ...
0
votes
2answers
31 views

Prove that a given set $S$ is convex

Prove that the given set $$S = \left\{(x_1, x_2, x_3) \in \mathbb{R}^3 \middle| 0 \le x_1 \le x_2 \le x_3 \le 6\right\}$$ is convex. My proof: Let $x,y \in S$ and let $t \in [0,1]$ To prove that $S$...
0
votes
0answers
26 views

convexity is invariant under affine maps

I am trying to show that $g(x) = f(Ax + b)$ is convex if x is convex. What I came up with is: $f$ is convex if $f(\lambda x_1 + (1-\lambda)x_2) \leq \lambda f(x_1) + (1-\lambda)f(x_2) $ Therefore ...
0
votes
1answer
25 views

Convex hull of path in $\mathbb R^2$ is the set of convex combination of 2 points of the path

I fell onto this post https://mathoverflow.net/questions/77379/convex-hull-of-path-connected-sets. The first answer is interesting and I can't find a simple argument to show that for $\mathbb R^2$ ...
-1
votes
1answer
23 views

Given two finite point sets $X,Y$, how to efficiently calculate the projection of $conv(X),conv(Y)$ onto their closest points?

Let's say we're given two sets of points, $X:=(x_i)_{i\in k_1},Y:=(y_i)_{i\in k_2}\subseteq\mathbb{R}^n$ and their convex hulls $conv(X),conv(Y)$. Let's assume $conv(X),conv(Y)$ are disjunct. We want ...
2
votes
1answer
142 views

Sufficient criteria for proving convexity of a polygon

We define a 2D polygon to be a simple (ie. non-self-intersecting) closed path consisting of line segments. To be clear, only consecutive segments intersect and only at an endpoint. Moreover, we do not ...
0
votes
1answer
49 views

What is the convex hull of this cone in $\mathbb{R}^n$?

Let $n \ge 3$. Define the subset $D \subseteq \mathbb{R}^n$ as follows: $x=(x_1,\dots,x_n) \in D$ if and only if all the $x_i \le 0$ , and each strictly negative values appears an even number of times ...
2
votes
1answer
204 views

Finding extreme points of closure of convex hull

Let H be a infinite dimensional Hilbert space with orthonormal basis $(e_n)_{n\geq 1}$. Let $f_N=N^{-\frac{1}{2}}\sum_{n=1}^Ne_n$ for all $N\geq 1$ and let K be the norm closure of the convex hull of $...
1
vote
1answer
63 views

The boundary of the convex hull of squares of skew-symmetric matrices

Let $n \ge 3$, and let $C$ be the convex cone generated by the squares of all real $n \times n$ skew-symmetric matrices. Is $C$ closed in $\mathbb{R}^{n^2}$? What is its boundary? $C$ is a strictly ...
1
vote
1answer
32 views

Is a convex cone which is generated by a closed linear cone always closed?

Let $C \subseteq \mathbb{R}^n$ be a closed cone which contains zero. (i.e. $\lambda C \subseteq C$ for every $\lambda \ge 0$). Let $P(C)$ be the convex cone generated by $C$, i.e. the set of all ...
0
votes
1answer
22 views

Altering affine space by changing offset within linear subspace of $\mathbb{R}^{n}$

Let $C\in\mathbb{R}^{n}$ be a convex set with $\text{aff}(C)=W+t$. For $x\in\text{cl}(C)\backslash\text{reint}(C)$, show that there exists $v\in W$, $v\neq0$, such that $$\text{sup}_{x\in C}v^{T}z=v^{...
1
vote
1answer
63 views

Convex hull of a convex curve as an infinite intersection of convex hull of triangles

Let $f(x)$ be a univariate convex curve (say $f(x) = x^2$) and let the domain be bounded. The goal is to prove that the convex hull of this curve in its domain can be expressed as an infinite ...

1
2 3 4 5
7