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
0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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. ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
27 views

Number of connected components of the polynomially convex hull of a compact $K\subset\Bbb C^n$

Let $K$ be compact in $\Bbb C^n$, without loss of generality $K$ connected. We define its polynomially convex hull as $$ \widehat{K}:=\{z\in\Bbb C^n\;:\;|f(z)|\le\|f\|_K\;\forall f\in\mathcal O(\Bbb C^...
2
votes
0answers
38 views

Derive an algorithm of convex hulls intersection with $O(n)$ time

You are given two sets of points in the plane, the red set $R$ containing $n_r$ points and the blue set $B$ containing $n_b$ points. The total number of points in both sets is $n = n_r + n_b$. Give an ...
-1
votes
1answer
103 views

$\|x_0 − y_0\| = \operatorname{dist}(A, B)$ [closed]

Let $X$ be a reflexive Banach space and let $A, B$ be non-empty, closed, and convex subsets of $X$. If $B$ is bounded, prove that there exist $x_0$ in $A$ and $y_0$ in $B$ with $\|x_0 − y_0\| = \...
0
votes
0answers
22 views

Topological Properties of Measures with a Common Barycenter

Let $A$ be a convex subset of a locally convex vector space $X$ and consider $M(A)$ the set of regular Borel probability measures on $A$ with the weak* topology. For a fixed point $x_0 \in \overline{A}...
0
votes
0answers
24 views

Compact set and simplex

Assume I have an open, nonempty Set $X \subseteq \mathbb{R}^n$ and a compact set $K \subseteq X$. Intuitively, there must be a simplex $S$ such that $K \subseteq S \subseteq X$. I would love to see a ...
1
vote
1answer
28 views

analytical form for extreme points of polynomial on intervals.

Given coefficient $w_0, w_1, \cdots w_d$ of d degree polynomial $f(x) = \sum_{i=0}^d w_ix^i$. And some interval $x \in [x_1, x_2] \subset \mathbb{R}$, I'm interested in the extreme points of this ...
0
votes
0answers
21 views

extreme points on cumulative sequence.

Given a sequence of vectors $(a_1, 1), \cdots, (a_i, 1), \cdots, (a_n, 1)$ such that $ a_i \in \mathbb{R}^+$. And my interest is to find extreme points(extreme points of the convex hull) of the ...
0
votes
0answers
23 views

Finding the minimum volume of all possible regions made by a concave polyhedron and its convex hull

I'm working on a project creating 3d-printed joint models and I would like to minimize the amount of plastic needed in adding protrusions that would form the perfect makebed. A visual example of the ...
0
votes
0answers
25 views

Convexity of a configuration of $n$ points

Let's say we have $n$ points say in $\mathbb{R}^2$, and $h$ points of the $n$ points where $n \ge h \ge 3$ are on the convex hull of this configuration. How many ways are we able to create a non-...
0
votes
0answers
22 views

Given $K$ points in the $N$-simplex, when is there a unique $M$-polytope that contains the $K$ points?

Given $K$ points in the $N$-simplex, when is there a unique $M$-polytope that contains the $K$ points? For example, in the below image $K=13, N= 2, M=3$. Clearly the polytope (the inner triangle) can ...
0
votes
1answer
31 views

How many points are required to represent the unit ball in the $\ell_{\infty}$-norm as a convex hull?

Given the unit ball in the $\ell_{\infty}$-norm: $$C = \{ x : |x_i | \le 1,\ i = 1, \dots, n\}$$ how many points are needed to describe $C$ in the convex hull form of: $$\{\theta_1v_1 + \cdots + \...
2
votes
1answer
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 ...
1
vote
1answer
89 views

Linear programming: What is the set of gradients of the objective function for which a given extreme point of the feasible region is optimal?

Consider the linear program, $$ \begin{array}{ll} \text { Maximize } & \mathbf{c}^{\mathrm{T}} \mathbf{x} \\ \text { subject to } & A \mathbf{x} \leq \mathbf{b} \\ \text { and } & \mathbf{...
0
votes
3answers
66 views

Calculate volume of intersection two non-aligned cuboids

I'm on the lookout to finding an algorithm that calculates the volume of the intersection between two cuboids. Most answers so far assume all the axes of the two cuboids in question are nicely aligned....
0
votes
0answers
39 views

Finding the core of a 4 player game

How do you find the core of this game? $V({0}) = V({1}) = \dots = V({4}) = 0 , V({1,2,3}) = V({1,2,4}) = 6, V({1,3,4}) = 5,V({2,3,4}) = 3, V({N}) = 11$ This is supposed to be the core: $C(v)=conv( { (...
0
votes
1answer
48 views

Unbounded convex hull is possible?

I'm reading this lecture note for additional study.(https://people.orie.cornell.edu/dpw/orie6300/fall2008/Lectures/lec05.pdf) For Q the convex hull of a finite number of vectors v1, v2, . . . , vk, Q ...
1
vote
0answers
19 views

Find projections of a convex region

Consider the following convex region $$ \{x\in \mathbb{R}^K: Ax\leq b \} $$ where $A$ is a known $m\times K$ matrix and $b$ is a known $m\times 1$ vector. Let $x_i$ be the $i$-th element of $x$. I ...
1
vote
1answer
46 views

For every pair of points $x,y\in S\subset\mathbb{R}^2,\exists z\in S$ s.t. $z$ lies on the straight line formed by $x,y.$ Can $S$ be finite?

Actual question: If $S\subset\mathbb{R}^2$ contains at least $3$ noncollinear points and for every pair of points $x_1,x_2$ of $S$, there exists a third point $x_3$ which lies on the (extended) ...
0
votes
1answer
32 views

Every noncollinear $3$ points of $S\subset\mathbb{R}^2$ contains inside of it another point of $S$. Is $S$ is a dense subset of some convex hull?

Proposition: Suppose $S \subset \mathbb{R}^2$ contains at least $3$ noncollinear points. Suppose further that for every noncollinear $3$ points of $S$, the triangle formed by those $3$ points contains ...
0
votes
0answers
26 views

Find convex hull of union

Determine the convex hull for convex set: $$ \{(x_1, x_2) \in \mathbf{R^2} : x_{1}^2 + x_{2}^2 =1, x_1 \geq 0\} \cup \{(2,0)\}$$ I think that is should look like this with the convex hull depicted by ...
4
votes
0answers
105 views

Mistake in Paper about LMI characterisation of trigonometric polynomial curve?

The following is taken from Efficient Large-Scale Filter/Filterbank Design via LMI Characterization of Trigonometric Curves by Hoang Duong Tuan, Tran Thai Son, Ba-Ngu Vo, and Truong Q. Nguyen Consider ...
1
vote
0answers
24 views

Partition of polytope (with respect to convex hull)

Let's assume a given (convex) polytope P. There are a number of papers regarding partitions, but I couldn't find a starting point for my problem: I'm looking at a partition of P into polytopes P_i ...
6
votes
1answer
78 views

How to prove that the line outside a convex polygon, having the minimum sum of distances is one of the edges?

As part of a computational geometry question, I need a result for an intermediate step. Suppose there is a convex polygon S, with finitely many points inside the polygon. Now, we want to find the line ...
0
votes
0answers
36 views

Conic hull of S

There is a set S such that $S = \{(x_1,x_2):(x_1-1)^2+x_2^2=1 \}$ I need to find the conic hull of this set. So, I know that the conic hull is basically defined as $\mathbb{cone}(S)=\{ \sum a_i x_i: ...
0
votes
1answer
26 views

Infinite convex combination is in the closure of the convex hull.

Let $V$ be a topological vector space and $\{x_i\}_{i \in I}$ be a net in $V$. Further, let $\{\lambda_i\}_{i\in I}$ be a net in $[0,1]$ such that $$\sum_{i \in I}\lambda_i =1.$$ Assume $x= \sum_{i \...
0
votes
1answer
69 views

How to find the largest ellipsoid which fits within a convex hull?

I am looking for a mathematical realization of finding the largest ellipsoid which fits within a convex hull. Let's say the ellipsoid is defined as $$ E = \left\{ By+d \mid \left \| y \right \|_2\ \...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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? ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
35 views

Prove that the zeros of this sum of rational functions have less than a certain modulus

From 2.1 of Sheil-Small: Define $$R(z):=\sum_{k=1}^n \frac{c_k}{\left({z-z_k}\right)^m},$$ where $c_k>0$ and $|z_k|\leq 1$. Prove that all finite zeros of $R(z)$ are in $\{|z|\leq \frac{1}{2^{1/m}-...
0
votes
0answers
32 views

A characterisation of the convex hull that is not obvious.

It says that if x is not in the convex hull of a compact K, then there exists an affine map ...
-1
votes
2answers
53 views

Prove that you can choose three of spotlights.

The plane is illuminated by several spotlights, each of which illuminates a half-plane. Prove that you can choose three of these spotlights, which also illuminate the entire plane?
1
vote
1answer
87 views

Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball

Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
0
votes
1answer
43 views

Convex hull and number of vertices

Let $S_N \subseteq \mathbb{R}^n$ be the convex hull of a finite set of $N$ points in $\mathbb{R}^n$, i.e., $S_N := \mathrm{conv}(\{x_1, \ldots, x_N\})$, and let $V_N$ be the associated set of extreme ...
0
votes
0answers
21 views

Check if a formulation is correct for a set and vertex belong to set

Given following set: $ X =\{x=(x_1, x_2, x_3, x_4)^T \in \{0, 1\}^4 : 83x_1 + 61x_2 + 49x_3 + 20x_4 \le 100 \} $ how I can check if: $ P =\{x \in R^4 : 0 \le x \le (1,1,1,1)^T,$ $ 4x_1 + 3x_2 + 2x_3 + ...
0
votes
0answers
41 views

The relation between convex shape and its convex hull (minimum bounding box)

The minimum bounding box (MBB) is the kind of convex hull that the smallest enclosing rectangle/box around a set of points. The vertices of convex polygon and polyhedron in two and three-dimension are ...
0
votes
0answers
23 views

Union of convex hull

I have a following problem: $$ {\bigcup_{i \in I(\bar{x})}\operatorname{co}\left\{\partial g_{i}\left(\bar{x}, v_{i}\right): v_{i} \in V(\bar{x})\right\}} $$ Where $I(\bar{x})=\left\{i \in\{1,2, \...
2
votes
2answers
53 views

Find convex closure of certain set

I'm having trouble solving this problem: Given the set $X\subset\mathbb{R}^2$ defined as $$X=\{(x,y)\in\mathbb{Z}\times\mathbb{R} : y\geq 0,x^2\leq b^2+y\},$$ being $b\in\mathbb{R}$. Is $X$ covex? ...

1
2 3 4 5
9