Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

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

0
votes
0answers
14 views

Polyhedra, half spaces and compact

I would like to show that $\{ x ; \forall j \in \{1,...,n\}, \langle x, z_{j} \rangle \le s_{j} \} $ is compact when the convex cone generated by the $(z_{j})_{1 \le j \le n}$ is $R^{d}$. I have been ...
0
votes
0answers
14 views

Maximal enclosed D-simplex

Is it possible to construct convex D-polyhedron $P$ that there exists a D-simplex $A$ spanned on vertices of $P$, that its ...
1
vote
0answers
64 views

For a general norm on $\mathbb{R}^d$, how can the intersection of a ball's boundary and a cone be contained in a $(d-1)$-hyperplane?

Consider $\mathbb{R}^d$ under a general norm (not necessarily Euclidean). Consider two fixed concentric balls centered at the origin $B(0, R_1)$ and $B(0, R_1/2)$. Let $x$ be an arbitrary point with $|...
0
votes
1answer
24 views

$conv\{\bar{x},\bar{y},\bar{z} \} \cap conv\{\bar{x},\bar{y},\bar{t} \} \cap conv\{\bar{x},\bar{z},\bar{t} \} = \{\bar{x} \}$

Let $\{\bar{x},\bar{y},\bar{z},\bar{t}\}$ be 4 points in $\mathbb{R^2}$, such that $conv\{\bar{x},\bar{y},\bar{z} \} \cap conv\{\bar{x},\bar{y},\bar{t} \} \cap conv\{\bar{x},\bar{z},\bar{t} \} = \{\...
3
votes
0answers
28 views

Is the set $\overline{\text{conv}}^{w^*} C$ weakly* compact?

Exercise : Let $X$ be a Banach space and $C \subseteq X^*$ be $w^*-$compact. Is the set $\overline{\text{conv}}^{w^*} C$ $w^*-$compact ? Thoughts : I (think) that I know that $w^*-$compact sets ...
0
votes
1answer
33 views

Finding restrictions and convex hull by having a set of extreme points

Suppose we are given a set of extreme points. Is it possible to find out all possible restrictions of the Linear Programming problem by having those extreme points? Well, if we have a linear ...
0
votes
0answers
13 views

Absolute convex hull of rank 1-correlation matrices?

Does there exist a ''universal'' constant, $c > 0$ say, such that for any(!) $k \in \mathbb{N}$ every(!) $k \times k$-correlation matrix $\Sigma$ can be written as $\Sigma = c\Theta$, where $\Theta$...
0
votes
0answers
7 views

Confusion on proving $\operatorname{conv}(E) \subseteq P$ via induction

Terms are translated from a different language, so I am not sure whether they coincide. Let $E$ represent the number of corners of $P(A,b)$ and $P(A,b)$ be a polytope. Prove that $\operatorname{conv}...
0
votes
0answers
13 views

Convex hull and geometric median

Let $X\subseteq\mathbb R^d$ ($d\geq 1$) and let $\Delta_{(X)}$ be the collection of all families $(w_x)_{x\in X}$ of nonnegative numbers, such that $\{x\in X:w_x\neq 0\}$ is finite, and that sum to ...
2
votes
2answers
34 views

Are vectors in $[-1,+1]^d$ a convex combination of vectors in $\{-1,+1\}^d$?

Vectors in $[-1,+1]^d$ are definitely linear combinations of vectors in $\{-1,+1\}^d$. How to show there is a convex combination?
0
votes
0answers
29 views

Convex hull of {-1, 1} rank-1 matrices?

Consider set $\mathbb{R}^{m\times n}$ of $m \times n$ matrices. I'm particularly interested in properties of polytope $P$ defined as a convex hull of all {-1,1} matrices of rank 1, that is, $$ P = \...
0
votes
1answer
16 views

Convex hull of sets in Minimax theorem

Suppose $X\subseteq\mathbb{R}^n$ is a convex and compact set, and $Y\subseteq\mathbb{R}^m$ is a nonconvex bounded set. Consider $$ \min_{x\in X}\max_{y\in Y}x^TAy. $$ Is this equivalent to $$ \min_{...
2
votes
2answers
44 views

Convex hull of the union of compact and convex sets

Let X be a normed space and $A,B \subset X$. I need to prove that if $A$ and $B$ are compact and convex then $conv(A \cup B)$ is compact. (Here $conv(A \cup B)$ is the convex hull of $A \cup B$) If $...
0
votes
0answers
15 views

Classifying Radon partitions in $\mathbb{R}^n$ whose affine hull is $\mathbb{R}^n$

Specifically, I want to determine all distinct "types" of Radon partitions of $n+2$ points in $\mathbb{R}^n$ for which the affine hull is all of $\mathbb{R}^n$. This is a homework question, so I'm ...
1
vote
1answer
95 views

Proof verification for some properties of convex hulls

Let $X$ be a normed vector space and $A$ be a subset of $X$. $\operatorname{conv}(A)$ is called the intersection of all convex subsets of $X$ that contain $A$ a) Show that $\operatorname{conv}...
1
vote
1answer
27 views

Proof of Kirchberger's Theorem in Convex Geometry

I am having trouble understanding certain parts of the proof of Kirchberger's Theorem, as presented here. Specifically, I am having problems understanding the proof of the following combinatorical ...
0
votes
1answer
29 views

Is the convex hull of union of a line and a point an open set?

Given a line $l$ and a point $A$ not on the line, is the convex hull of the two an open set? As per my understanding, the hull will be all points between lines $l$ and line $m$ which passes through $A$...
1
vote
0answers
24 views

Probability of n points from a square area being all on their convex hull

If we uniformly randomly generate n points in the unit square, what is the probability of all of them laying on their convex hull, i.e., they form a convex n-gon? I've been searching the internet and ...
1
vote
1answer
62 views

Finding the convex hull of m x n matrices

Given a set of $\mathbb{R}^{m \times n}$ matrices, I would like to find the matrices forming the vertices of their convex hull. Would this be the same problem as finding the convex hull of a set of ...
0
votes
0answers
26 views

A more efficient convex hull algorithm

Before I start, I would like to say that this is for a programming project of mine I'm doing but I figured my question is only about the part involving math so here I am. So in Grahams Scan algorithm, ...
0
votes
1answer
34 views

Prove projection of convex hull = convex hull of projection

I'm not sure how to show this: $proj_x(conv(S)) = conv(proj_x(S))$ where S $\in R^{n+p}$
0
votes
1answer
19 views

The boundness of a polyhedral set implies that $y \in \mathbb{R}^n $ is equal to zero

I'm solving a problem of nonlinear programming. The problem says: Let $S_1=\{x:A_1 x\le b_1\}$ and $S_2=\{x:A_2 x\le b_2\}$ be nonempty. Define $S=S_1\cup S_2$ and $S'=\{x: x=y+z, A_1y\le b_1\...
2
votes
1answer
56 views

Problems about the convex hull.

I'm stuck in two problems concerning about convex hull. Let $A,B,C \not= \emptyset$, compact sets in $\mathbb{R^n}$. Show that if $A+B=A+C$ then $\text{conv}(B)=\text{conv}(C)$ Let $B\not= \emptyset$...
0
votes
0answers
11 views

How to create a convex polygon which is the superset of a given polygon?

I have a JTS_footprint like this, POLYGON ((46.542770 -65.500984,54.130459 -63.660416,59.213402 -66.664993,51.004562 -68.736069,46.542770 -65.500984)) How do I ...
2
votes
1answer
58 views

Algorithms for projecting a point onto the convex hull spanned by a set of vectors

Given a set of vectors $V = \{ \mathbf{v}_1, \ldots, \mathbf{v}_n \} \subset \mathbb{R}^d$, I want to project a point $\mathbf{x}_0 \in \mathbb{R}^d$ onto the convex hull $\text{conv}(V)$ of the ...
0
votes
1answer
34 views

Modified Quickhull algorithm for finding convex hulls

The quickhull algorithm described here finds the furthers point from the line segment in step 3. I am having trouble reasoning about what would be the result if the algorithm just considered the ...
0
votes
1answer
39 views

Theorem 3.20 rudin's functional analysis, compactness of $K = f(S \times A)$

Reading through theorem 3.20, Rudin's functional analysis (point (a)). If $A_1,\ldots, A_n$ are compact convex sets in a topological vector space $X$ then $co(A_1 \cup \ldots \cup A_n)$ is compact. ...
5
votes
2answers
251 views

Prove that 0 is in the convex hull of points chosen from each orthant

If we arbitrarily choose a point from each orthant in $\mathbb{R}^n$, that is we choose $2^n$ points in total, how do we prove that 0 is in the convex hull of these $2^n$ points? It seems obvious, but ...
0
votes
0answers
22 views

Computing quadrilateral convex hull of the region defined by 2 linear transformations

I am not very familiar with the literature on computing convex hulls. So I thought to ask in case it was something that has already been solved. Assume that we have $f_y$ and $f_z$, linear functions ...
4
votes
0answers
40 views

Proof that the minimum area rectangle is collinear with an edge of the convex hull?

If I have a finite set of points S, is there a way to prove that the minimum area rectangle containing all points in S will be collinear with one of the edges of the convex hull of S? As far as I can ...
1
vote
1answer
29 views

Permutahedron of three vectors (1,1,0,0), (−1,1,0,0), (−1,−1,0,0).

I'm getting stuck on parts b, c, and d. Since visualizing the polytope is not possible, I think the way to find the facets and edges of P is to determine which combinations of points form facets and ...
3
votes
3answers
167 views

Product of two polytopes is a polytope

Please have a look at my attempt for this problem. Let $x = \begin{pmatrix} x_1\\ x_2 \\ \end{pmatrix}, x_1 \in P_1, x_2 \in P_2$. I want to show that $x \in conv\{P_1 \times P_2\}$, i.e. $x$ can be ...
1
vote
1answer
32 views

Closed convex hull of a subset of $\mathbb{C}^d$

Let $W$ be a subset of $\mathbb{C}^d$ and $co (\overline{W})$ be the closed convex hull of $W$ (here $\overline{W}$ is the closure of $W$ with respect to the topology of $\mathbb{C}^d$). I don't ...
1
vote
0answers
26 views

Guarantee strict convexity at a point

Suppose we have a univariate function $f(t), t\in [0,1]$. We define \begin{align} G(p) = \sup_{t\in [0,1]} p f(t) + (1-p) f(1-t), \text{ for } p\in [0,1]. \end{align} Clearly $G(p)$ is a convex ...
2
votes
1answer
35 views

$\bigcap_{i}\mathrm{co}(A_i)=\mathrm{co}(\bigcap_{i}A_i)$

Let $(A_i: i \in I)$ be a family of closed sets contained in $[0,1]$ such that for all $i,j \in I$ there exists $k \in I$ for which $A_i \cap A_j=A_k$. Denote by $\mathrm{co}(X)$ the convex hull of $X$...
1
vote
2answers
50 views

$\bigcap_{i \in I}\overline{co}(A_i)=\overline{co}\left(\bigcap_{i \in I}\overline{A_i}\right)$

Let $(A_i: i \in I)$ be a family of sets in a topological vector space such that for all $i,j \in I$ there exists $k \in I$ for which $A_i \cap A_j=A_k$. Denote by $\overline{co}(X)$ the closure of ...
0
votes
1answer
16 views

Mikowski functional of the set $\{ (x,y) \in \mathbb R^2 \mid (x-1)^2 + y^2 \le 2, (x+1)^2 + y^2 \le 2 \}$

I'm trying to find the explicit formula for the Mikowski functional of the set $$A = \{ (x,y) \in \mathbb R^2 \mid (x-1)^2 + y^2 \le 2, (x+1)^2 + y^2 \le 2 \}\,.$$ It's clear that $A = A_{-1} \cap A_{+...
2
votes
1answer
42 views

What is the convex hull of $\text{conv}(u_1,u_2,\cdots,u_p)+\text{conv}(v_1,v_2,\cdots,v_s)$?

Let $u_i, i= 1,\cdots,p$ and $v_j, j= 1,\cdots,s$ be finitely many vectors in $\mathbb{R}^n$. Show that $$ \text{conv}(u_1,u_2,\cdots,u_p)+\text{conv}(v_1,v_2,\cdots,v_s)=\text{conv}\{u_i+v_j \mid i=...
2
votes
0answers
38 views

Number of Sets of Points Containing a Given Point in its Convex Hull

Consider a lattice grid $[0,N]\times [0,N]$ and a given point $P$ inside the grid. Denote the set of lattice points as $S$ (of course, $|S|=(N+1)^2$). I'd like to ask how to count the number of ...
1
vote
0answers
12 views

How to maintain concavity while normalising a set of samples?

I have a set of 2D samples that approximate a geometric shape that I am trying to construct. Due to measuring errors some samples are slightly off, generating "jaggy" artifacts in the surface of the ...
1
vote
1answer
42 views

Show that support function of a set $S$ and support function of the closure of that set $\bar{S}$ are equal.

Let $S\subseteq \mathbb{R}^n$. The support function of set $S$ is defined as the following $$ \sigma_S(x)=\sup_{y \in S} x^Ty $$ where $x \in \mathbb{R}^n$. Show that $\sigma_S(x)=\sigma_{\bar{S}}(...
1
vote
1answer
50 views

Compact convex set

Let $K$ be a convex set in $\mathbb{R^n}$ a) For arbitrary $x_1,x_2,...,x_{n+1}\in K$ prove that intersection of all sets $\frac{1}{n}x_i+K$ is nonempty for all $i=1,2,...,n+1$. b) If $K$ is compact ...
0
votes
0answers
12 views

Convex hull spanning n-percent of points

I would like to calculate the convex hull of some points, but neglect some "outlier" points. I.e. in the end i would like to have the convex hull spanning, let's say, 90% of the points instead of all. ...
0
votes
0answers
20 views

The Proof of Absolutely Convex Hull?

A set is absolutely convex if and only if it is convex and balanced. Can you prove that ''A set ${\displaystyle C}$ is absolutely convex if and only if for any points $x_1,x_2\in C$ and any numbers $\...
0
votes
0answers
25 views

Why support function describes the (signed) distances of supporting hyperplanes of A from the origin?

The support function of a set $A \in \mathbb{R}^n$ is defined as the following $$ S_A(x)=\sup_{y \in A} x^Ty $$ where $x \in \mathbb{R}^n$. In Wikipedia: Support function it says support function ...
1
vote
1answer
25 views

Question about affine span and symmetric matrices

$A$ and $B$ are real $n\times n$ matrices and $S=\{(x,y)\in \mathbb{R^2}$ : $I+xA+yB$ is positive semidefinite matrix $\}$. Prove that $\mathbb{R^2}= Aff(S)$ if and only if $A$ and $B$ are symmetric. ...
0
votes
0answers
65 views

angle constrained convex hull

Given a set of points $P$ in $R^d$ it is straightforward to compute the convex hull (Graham-scan etc). However, the angle between the adjacent faces are unconstrained. Let us suppose two adjacent ...
1
vote
2answers
87 views

If $f'(x)=0$, is then $f(x+dx)=f(x)$?

I am always struggling with infinitesimals, and not sure I'm getting this right. The title basically states the simplest version of my question: If a function has zero slope at some point, is it ...
1
vote
0answers
21 views

'Two object convex hull' and related operations

The convex hull of a set of points can be defined as the set of all convex combinations of the points in the set. For example and for contrast with my question, in the following two-dimensional ...
0
votes
1answer
36 views

Convex hull of some points on the convex position

Definition: The Convex hull of a set of points is the smallest convex set which contains them. Question: Assume that $n$ points like $P=\{p_0,p_1,p_2,...,p_{n-1}\}$ are given and all we ...