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

448 questions
Filter by
Sorted by
Tagged with
17 views

### Support points of Capsule/Cube

There is a formula c+r*v/||v|| which allows us to easily calculate the supporting points (one point within 3d object that is the most extreme in direction of vector v) of Sphere. Are there similar ...
18 views

### Number of vertices of 3D Zonotope in general position with all positive generators

Given $d$ generators $G = \{ g_1, g_2, \cdots, g_d \} \subset \mathbb{R}^2_+$. One can obtain the Zonotope via $Z = CH(\{ \sum_{g \in S} g|S \subset G \})$, here $CH$ is convex hull operation. And the ...
26 views

### The convex hull of a finite subset of $\Bbb{R}^2$ is the intersection of all closed half plane

Let $X \subset \Bbb{R}^2$ be finite. Show that the convex hull of $X$ is the intersection of every closed half space. This is pretty simple in a geometric way, I just can't prove it in a formal way. ...
44 views

### Proving that a convex cone doesn't contain the negative of any point in the cone

Let $x_1, x_2 \in \Bbb R^d$ be two rays that define a ‘noisy’ convex cone $$C := \{ \lambda x_1 + (1 - \lambda) x_2 + \epsilon \mid \lambda \ge 0 \},$$ for some vector $\epsilon \in \Bbb R^d$ with a ...
22 views

### Proving that conic hull of a convex set is convex [closed]

Let $S$ be a convex set. Prove that conic hull of $S$ $cone(S)$ is a convex set. Definition of a cone is S is called a cone if for any $x \in S$ and $\lambda \ge 0$ then $\lambda x \in S$. And the ...
23 views

### Supporting hyperplane

Let $C$ be the convex hull of the points $A = (1,0), B= (0,1)$ and $C=(-1,0)$. Determine the set of points $P \in C$ for which there is a supporting hyperplane of $C$ in $P$ and the points for which ...
27 views

### Proof the conic hull of a finite set of vectors is closed

I want to prove that given a family of vectors $(u_1,...,u_m)$ in $\mathbb{R}^n$ : $$C = \Big\{ \sum_{i=1}^{m} \alpha_i u_i,\; \alpha_i\geq 0 \; \: \forall i \in\{1,..,m\} \Big\}$$ is closed. It is ...
27 views

88 views

### Find out the convex hull of the set $\left\{\pm \mathbf{u} \mathbf{u}^{T} \mid\|\mathbf{u}\|=1\right\}$ in a compact form ($u$ is a n-d vector)

According to the answer from @Cloudscape The first step of finding the convex hull of a given set would be to visualize the convex hull and guess it. The second step would be to prove your guess ...
89 views

18 views

### Brute-force vertex enumeration for polytope

Let $P$ be a polytope of $\mathbb{R}^n$ defined by a (bounded) finite family of half-spaces $t_i \cdot x \leq q_i$ with every $t_i \in \mathbb{R}^n$ non-zero and $q \in \mathbb{R}$. There is no ...
35 views

### Smallest convex set

While trying to prove that the convex hull of a set $S \in R^{n}$ is the smallest convex set containing S, I encountered some issues. However, i found a very useful answer in Prove that the convex ...
65 views

### Generating valid inequalities to describe the convex hull of a set

How to generate the valid inequalities needed to describe the below sets' convex hull? ...
33 views

### Delaunay Triangulation - Forcing convex hull

I was implementing Delaunay Triangulation based on (http://paulbourke.net/papers/triangulate/) under the impression that this triangulation always results convex hull [which is not :( ]. Is there ...
39 views

### Evaluating the Gauss Circle Problem $N(n)$ in $O(n^{\frac{1}{3}+\epsilon})$

I'm interested in the technique of counting the number of positive integer pairs $x$ and $y$ satisfying $x^2+y^2 \leq n$ in $O(n^{\frac{1}{3}+\epsilon})$. The basic idea is that we can only focus on ...
13 views

### The greatest convex minorant approximation for given data

Here, $f$ is unknown but finite numbers of data $(x_i, f(x_i))$ are accessible. I would like to know whether there is an approach to approximating the greatest convex minorant of a function $f$. Is ...
22 views

### Show that the convex hull of vertices of polytope is the same polytope

I know there are many equivalent definitions in this field, so I will define all the properties by the way I studied them, and you can go only from these definitions: I define a polytope - bounded ...
28 views

### Application of Colorful Caratheodory for Directed Cycles

I'm working through Irme Barany's convexity lectures (http://wiki-math.univ-mlv.fr/gemecod/lib/exe/fetch.php/barany_lecture_2.pdf) and I am struggling to prove an exercise the author left to the ...
35 views