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

527 questions
Filter by
Sorted by
Tagged with
20 views

### Decomposition of closed convex sets which don't contain any affine lines in a finite demension.

I am studying convex analysis especially the structure of convex closed sets in a finite demension. I am trying to digest this is theorem below, and yes I understand the demonstration and all but I ...
1 vote
15 views

### What is an upper bound on the diameter of a convex polytope?

Given a convex polytope defined by $Ax \le b$, with $V = \{ x_1, \ldots, x_n \}$ vertices, I would like to find the maximal distance $\max_{i,j} || x_i - y_i||_2$ as a function of $A$ and $b$ (some ...
20 views

### Good resources that talk about geodesically convex sets for riemannian manifolds?

Are there any good resources that talk about geodesically convex sets, and in particular convex hulls, for riemannian manifolds? I’ve been wanting to learn more about them, their geometry and ...
53 views

### Compact set which isn't convex hull of its extreme points

Consider $\ell^\infty$. Let $$A := \overline{\operatorname{conv}}\left(\left\{\dfrac{e_n}{n}\right\}\right)$$ It's not hard to see that this set is compact (using the Banach-Alaoglu theorem). But how ...
33 views

### Convex hull and optimal solutions

Consider the LP problem: $max$ $3x_1 + 2x_2+x_3$ $s.t$ $3x_1 + 4x_2 + x_3 ≤ 6$ $2x_1+x_2 + 3x_3 ≤ 5$ $x_1,x_2,x_3 ≥0$ I have solved the problem and found that the optimal value is 6 at $x=(2,0,0)$. ...
1 vote
147 views

### Point in Polytope?

Context: This question is somewhat identical to this on MathOverflow, it’s different in that it only focuses on the formula of the solution to the underlying problem. Suppose I have a convex hull $H$ ...
8 views

### Can you always find a d-dimension sphere that can circumscribe d-1 polytope

Is it possible to always find a circumscribing sphere in d-dimensions for any polytope in d-1 dimensions? Im thinking of the following papir: https://kenclarkson.org/coresets1.pdf on page 3 they state ...
17 views

10 views

### Maximum norm over 'spherical hull' of vectors

Consider $k$ vectors in $\mathbb{R}^n$, $v_1,...,v_k$. Let us define the set $$S_v = \{ x \in \mathbb{R}^n| x = \sum_{i=1}^k \lambda_i v_i, \lambda_i \geq 0, \sum_i \lambda_i^2 = 1\},$$ that is, it is ...
1 vote
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 ...
1 vote
46 views

### Fastest way to solve vertex enumeration problem in python

I have a set of 73 linear non-strict inequalities that describe a convex polytope in the 36-dimensional space. All but one of the inequalities are of the form $x>=b$ or $x<=b$. In every but one ...
29 views

### Shortest helical path with bumps on a cylindrical surface : 3D Convex 'Line' instead of hull?

I am studying the effect of fiber overlap during filament winding on a cylindrical surface. Every time a fiber crosses over another fiber, due to the thickness of the fiber under it, it 'bridges' for ...
135 views

58 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 ...
16 views

65 views

### What is a dimension of a convex hull?

Let $S$ be a set of data points in $E^d$, a real Euclidean space of dimension $d$. What would be the dimension of the convex hull of that data? In general, what is the definition of the dimension of ...
1 vote
68 views

47 views

### Convex $k$-gon containing $k+1$ points must contain $k+2$ points

Let $\{a_1,a_2,\cdots, a_{2k+2}\}$ be vertices of a convex $(2k+2)$-gon, labelled counterclockwise. Let $A = \{a_1,a_3, \cdots, a_{2k+1}\}$ be the subset labelled by odd integers. Intuitively, any ...
39 views

### Characterize convex sets that are the convex hull of their extreme points

The famous Krein-Milman theorem states that every compact convex set in a topological vector space is the convex hull of its extreme points. Note, however, that many convex sets exist in $\mathbb R^n$ ...
1 vote
25 views

### How can we exclude vertices of a compact polyhedron and represent it as a convex hull?

It is known that every compact (closed and bounded) polyhedron $P$ can be written as a convex hull of finitely many points, i.e., $\text{conv}\{x_1, \dots, x_m\}$. Questions How can I make sure that, ...
Suppose that $\boldsymbol{x}\in\mathbb{R}^p$. Also, assume $\Omega\subseteq \{1,2,\ldots,p\}$ is a subset of the indices, and $\Omega^c$ denotes the complement of $\Omega$. The notation $\boldsymbol{x}... 3 votes 1 answer 44 views ### Proof that$\left(\frac{1}{x}, \frac{1}{y}\right)$is a convex region if$(x, y)$is I'm trying to convince (prove) myself that if a set$S \subset \mathbb{({R^+})^2}$is a convex region, then$S' := \left\{ \left(\frac1{x}, \frac1{y}\right) ; (x, y)\in S \right\}$is also a convex ... 0 votes 0 answers 47 views ### Max/min values over convex hulls. Let$\mathbf{v}_1,\dots,\mathbf{v}_r$be vectors in a Euclidean space$\mathbf{V}$. Let$f \colon \mathbf{V} \to \mathbb{R}$be a linear function. Prove that$f$has both a maximum and a minimum value ... 0 votes 1 answer 55 views ### Prove convex hull is a compact set Let$\mathbf{v}_1,\dots,\mathbf{v}_r$be vectors in a Euclidean space$\mathbf{V}$. Prove that the convex hull$\mathrm{Conv}(\mathbf{v}_1,\dots,\mathbf{v}_r)$is a compact set. I believe the convex ... 2 votes 0 answers 21 views ### Sufficient condition for convex conjugates (does one imply the other?) We say$(f_1,f_2,\cdots,f_N)$a convex conjugate if for any$i=1,2,\cdots,N$and any$x_i\in\Bbb R^d$, we have:$$f_i(x_i)=\sup\left\{\sum_{k=1}^{N}\sum_{j=k+1}^N x_k x_j - \sum_{j=1,j\neq i}^N f_j(... 6 votes 0 answers 141 views ### Distance between point and convex hull in high dimensions I am trying to develop an intuition for the properties of the convex hull of a set of points in high ($d>20$) dimensions. Consider a set of$n$data points which are iid distributed according to ... 0 votes 0 answers 43 views ### How to prove the Carathéodory theorem? How to prove the following theorem: Theorem (Carathéodory) : Let$S\subset\mathbb{R}^{n}$. Any$x\in\mathbf{conv}(S)$can be represented as a convex combination of at most$n+1$points. I just started ... 0 votes 1 answer 43 views ### Jordan decomposition functional$C^*$-algebra [closed] Consider the following fragment from the thesis Injective and Semidiscrete von Neumann Algebras by Rasmus Sylvester Bryder: Why is the boxed equality true? In particular, I don't see why the right ... 6 votes 1 answer 86 views ### When is the smallest point on a hull a convex combination of the smallest vertices? Let$x_1, \dots, x_n\in\mathbb{R}^d$be a finite set of points and denote the convex hull by$H$. Assume that$0\not\in H$and also that each$x_i$is an extreme point, meaning that it cannot be ... 1 vote 1 answer 27 views ### convex hull and convex combination Let$X\subseteq R^d$and$u\notin conv(X)$. I want to prove that any$y\in conv(X\cup u)$can be written as$\lambda u + (1 − \lambda)x$for some$x \in conv(X)$and$λ \in [0,1]$. I intuitively get ... 1 vote 1 answer 48 views ### Expanding a convex set to a convex set with nonempty interior, while maintaining disjointness from a point Suppose$X$is a finite-dimensional normed space over$\mathbb{R}$. Let$\emptyset\neq M\subseteq X$be a convex set with empty interior, and let$x\in\overline{M}\backslash M$be a point on the ... 4 votes 2 answers 88 views ### A set of points is contained in a sphere$S$. When is$S$also the circumsphere? Given points$p_1,\ldots,p_n\in\Bbb R^d$so that all of them are contained in a common sphere$S\subset\Bbb R^d$(by which I mean the usual$(d-1)$-dimensional sub-manifold of$\Bbb R^d$). Note that$...
Let $S$ be a nonempty closed bounded subset of a normed vector space $(X,\|\cdot\|)$. Denote by $\overline{\mathrm{co}}(Y)$ the closed convex hull of a set $Y$. Question. Is it true that \$\{\|x\|: x \...