Mathematics Stack Exchange
Mathematics Stack Exchange

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

The convex hull of a set $X$ of points in a Euclidean space is the smallest convex set that contains $X$. They can be visualized by contracting a $n$-dimensional elastic sheet onto $X$.

Over $\mathbb{R}$ it is simply the set $[\min(X),\max(X)]$, over $\mathbb{R^2}$ it is a convex $n$-gon.

635 questions
2
votes
1 answer

How to find the convex hull of a set of points in $\mathbb{R}^4$

I have been tasked with finding the equations defining the convex hull of a set of points in $\mathbb{R}^4$. Specifically, my set of points are all of the vertices of the 4-dimensional unit cube except $\{(1,0,1,1), (1,1,0,1), (1,1,1,0),…
BSplitter
  • 1,553
2
votes
1 answer

Is the convex hull of an epigraph of a function an epigraph of some function?

Let $f: \mathbb R^n \rightarrow \mathbb R \cup \{-\infty,+\infty \}$ be a function. Let $epi f$ be the epigraph of $f$: $$ epi(f)=\{(x,r)\in \mathbb R^n\times \mathbb R:f(x)\leq r \}. $$ Is it true that if $(x,r)\in conv (epi(f))$ and $s>r$, then…
Richard
  • 4,432
2
votes
1 answer

Name of "reverse convex hull"

I have a set of Points representing building footprints (black in the image below). I also have Points (building address Points) that I know lie inside the building footprints (green). I'm searching for the name of a reverse convex hull analysis(?).…
BERA
  • 123
1
vote
1 answer

How to determine if a linear combination of $n$ variables is inside the convex hull of that $n$ variables

I know there is a common answer that the weights used to make a linear combination should be non-negative and sum up to one. But I think this condition is just a sufficient condition, not a sufficient and necessary condition. For example, there are…
Xu Yang
  • 13
1
vote
0 answers

Name of a specific hull

Consider a set of points $S \subset \mathbb{R}^n$ Let $$H(S) = \\\{y \in \mathbb{R}^n, \forall a \in {\mathbb{R}^{+}}^n, \exists x \in S, \langle a,x-y\rangle\geq 0\}$$ This is the set of point for which are "below" at least one point in S under any…
Arthur B.
  • 908
1
vote
2 answers

Why is Sklansky algorithm convex hull wrong

I stumbled across this incorrect O(n) algorithm for calculating convex hulls by Sklansky, but it was later proved to be wrong. My problem is this: why is it wrong? What is an example polygon that could give this error? Who figured it out to be…
code base 5000
  • 183
1
vote
1 answer

convex hull of a set of points equivalent to a set

I am trying to prove the following problem: Given a set of points $S = \{(x_i,t_i)_{i = 1}^K \}$ where $x_i \in R^n, t_i >0 ,\forall i = 1,...,K$ and $Y = \{y \in R^n: y = \frac{x}{t},(x,t) \in conv(S) \}$. I have proved that $Y \subseteq…
Chloe
  • 127
1
vote
1 answer

Does the range of convex hull of a set equal to the range of that set?

I'm trying to construct convex hulls of figures, and this question came up to my mind. Literally what I want to know, is that if the statement is true in Banach spaces. My idea about this is that when I want to make some figure convex, I just…
kolobokish
  • 732
1
vote
1 answer

using Qhull without points?

I'm trying to use the Qhull program to solve for convex hull. It seems to only take points as inputs. But my convex hull is so far only defined by the equation, i.e. ${\displaystyle \mathrm {Conv} (S)=\left\{\left.\sum _{i=1}^{|S|}\alpha _{i}x_{i}\…
Kate
  • 11
0
votes
1 answer

If $X$ is contained in one side of the hyperplane $H$, then $\text{conv}(X) \cap H = \text{conv}(X \cap H)$

I am trying to prove the following result: Let $X$ be a subset of $\mathbb{R}^n$ and $H=\{x \in \mathbb{R}^n:\langle x,u\rangle=\alpha\}$ be a hyperplane with normal vector $u$ such that $X \subset H^-$, where $H^-=\{x \in \mathbb{R}^n:\langle…
ImHackingXD
  • 996
0
votes
0 answers

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 cumulative sequence $B = (\sum_{i=1}^1 a_i,…
peng yu
  • 1,271
0
votes
1 answer

Minimum distance between convex Hull: Naive approach

In order to compute minimum distance between convex hulls, can we just use a naive approach like measuring all the points from first convex hull to second convex hull? And take the minimum value?
Kenny Karnama
  • 5
  • 5
0
votes
0 answers

How to prove a function is convex?

if $V=L^p(S,\Bbb R)$ and $g \in V$, how to prove f is convex for {$f \in V : f \geq g, \mu - a.e.$}? I understand A is convex if $x,y,\in A, (1-a)x+ay\in A$ and $0
hei
  • 51
0
votes
1 answer

Least Required Number for Constructing n-dimensional Convex Hull

Just had learn the concept of Convex set and Convex Hull. At this point I had figured of my self regarding the question as following: "Do I always need to have at least $n+1$ number of elements to construct a convex hull which is embedded in $\Bbb…
Beverlie
  • 2,645
-1
votes
1 answer

Minkowski sums of Convex Hulls

How do I prove that the Convexhull(p1) +(Minskowski Sum) Convexhull(p2) = Convexhull(p1+p2), Where p1 and p2 are convex polygons.
Anonymous Magic
  • 23