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

338 questions
Filter by
Sorted by
Tagged with
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 ...
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:...
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 ...
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}$?
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?
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, ...
22 views

48 views

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 ...
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 ...
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$ ...
24 views

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

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 ...
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 ...
### 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^{...
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 ...