Stack Exchange Network

Stack Exchange network consists of 174 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).

1
vote
1answer
20 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
0answers
21 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
7 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
15 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
14 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
16 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
21 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
83 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
16 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
22 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 ...
1
vote
0answers
49 views

Show that $\{p \in \Delta^n \mid b^T p + p^T Ap \leq \alpha\}$ is a convex set.

Show that $S := \{p \in \Delta^n \mid b^T p + p^T Ap \leq \alpha\}$ is a convex set where $\alpha \in \mathbb{R}$, $A\succeq 0$, $\Delta^n$ is the probability simplex. I have been stuck for this for ...
2
votes
1answer
52 views

How to algorithmically find only the edges of a high dimensional convex hull?

Given to me is a set of points $p_1,...,p_n\in\Bbb R^d$ in general position. I want to determine only the edges of the convex hull $C:=\mathrm{conv}\{p_1,...,p_n\}$, and this as efficient as possible. ...
1
vote
1answer
72 views

Find convex envelope from the non-convex function to prove globally optimal using branch-and-bound

Based on this reference branch-and-bound methods can obtain globally optimal solutions to nonlinear programming problems in which a non-convex function is to be minimized. I have a non-convex function ...
2
votes
0answers
30 views

Convex hull of a countable set

Let $X$ be a Banach space, $S=\left\{x_n\right\}_{n\in \mathbb{N}}\subset X$ a pre-compact and countable set. Is there an easy way, heavily based on the fact that $S$ is countable, to see that its ...
0
votes
0answers
13 views

Can convex hull algorithms be further optimized given regular polytopes?

Suppose I have a list of unordered vertex coordinates, which is guaranteed to be some regular (convex) polytope. Does a numerically stable algorithm exists that runs asymptoticly faster than the ...
1
vote
1answer
36 views

How to determine the faces of an array of points?

Is there a way of determining the faces of any polyhedron? I have an array of $3$-dimensional points and no information what polyhedron should come out.
7
votes
0answers
54 views

Is this construction of the “edge polytope” known?

Given a convex polytope $P\subseteq\Bbb R^d$. I am going to construct a new polytope from its edges (I call it the edge polytope) with the following steps: Take the 1-skeleton of $P$. Extract the ...
1
vote
0answers
24 views

Acute set in three-dimensional space

I'm trying to prove the following statement: Prove that every set of more than $8$ points in the three-dimensional space determines at least one obtuse angle. I'm aware that the generalization of ...
1
vote
0answers
45 views

Characterization of the convex hull in terms of dot product

I am doing some work with Newton Polytopes and I need something of this style: Given $v_1,\dots,v_n\in \mathbb{R}^n$ we have $$\text{conv}(v_1,\dots v_n)=\{v\in \mathbb{R}^n\mid \min_{i=1,\...
1
vote
1answer
45 views

Techniques for finding the edges of a 4-dimensional convex hull

I am looking for some techniques in general, but let's do it on a (for me relevent) example. I have a set of $n^2$ points $$p_{i,j}:=\frac1{\sqrt 2} \begin{pmatrix} \cos(2\pi i/n) \\ \sin(2\pi i/n) \\...
3
votes
1answer
65 views

Estimate the volume of Voronoi cell

Let given a ball of radius $\alpha$ centered in point $u$ in $d$-dimensional space. Let given a sample of $n$ uniformly distributed vectors $x_i$ ($i = 1,\dots,n$) inside the ball. For each vector $...
1
vote
0answers
25 views

Volume occupied by data points in $n$ dimensions [closed]

Which algorithms provide the the volume occupied by a set of data points in $n$ dimensions?
0
votes
0answers
35 views

Convex Hulls and maximizing volume

I thought of a function (recreational mathematics) and wonder if there is any existing math about it. Google searching did not turn anything up. Let $n\in \mathbb{N}$ be the dimension, and $x\in \...
3
votes
1answer
61 views

An illustration of convex integration theory: uniform approximation by a function with restricted values of the derivative

I'm reading Vincent Borelli's lectures on Convex Integration Theory and he begins by introducing two small examples. I am a little puzzled by his explanation, and I'm sure it's just something ...
0
votes
0answers
38 views

Minkowski functional of intersection and union of two convex sets

Let $K_1,K_2$ be some convex sets, such that $0\in K_1\cap K_2$, and $M_1,M_2$ be Minkowski functionals of these sets. I have a task to show that: $M_I=\max\left\{M_1,M_2\right\}$ is a Minkowski ...
3
votes
1answer
41 views

Generating borders with convex hull

I have some polylines (streets on a map) take these three, for instance: I need to convert these polylines into polygons. The mapping library I'm using has a built in convex hull function which ...
1
vote
0answers
29 views

Is the dual of a cone can be defined by the dual of the closure of its convex hull?

Let $K$ be a nonempty cone in $\mathbb{R}^n$. We denote the dual of a cone $K$ as $K^*$. Show that $$K^*=(\mathop{\boldsymbol{cl}} \mathop{\boldsymbol{conv}}K)^*$$ How can we describe the closure of ...
5
votes
2answers
73 views

Generalized Convex hull is just ordinary convex hull?

It seems that the definition of convex hull is on a form $\sum a_nx_n$ in which coefficients sum up to 1. It implicitly implies that the combination is countable and discrete. I am interested in more ...
2
votes
0answers
93 views

Distance between a compact closed body and its convex hull

Given any compact closed body $S \subset \mathbb{R}^n$, let $K \subset \mathbb{R}^n$ be its convex hull. Is there any theories regarding the distance between S and K? Also are there any regarding how ...
3
votes
0answers
42 views

Sampling volumes of the spectrahedron

Consider the following set (spectrahedron/spectraheplex) $$\mathcal A = \{ W : W \succeq 0, \mbox{tr}(W)=1 \}$$ Consider an approximating set $$\mathcal B = \mbox{co} \{ u_i u_i^T : \|u_i\|_2 = 1, ...
0
votes
1answer
23 views

How to get the edges of a duoprism?

Let $P_1$ and $P_2$ be two polygons, and $V_1$, $V_2$, their respective sets of vertices. Then the set of vertices of the 4-dimensional duoprism $D$ formed by the Cartesian product of $P_1$ and $P_2$ ...
0
votes
0answers
27 views

Probability to find a point onto a surface of convex hull

Is it possible to calculate a probability to meet a point from a set of spatially uniformly distributed points onto its convex hull surface? Say bounding shape is 3D shpere, or 3D cube, or 2D circle (...
2
votes
1answer
47 views

Is the convex hull of closed cones closed?

We say $K$ is a cone if $K + K \subseteq K$ and $[0,\infty) K \subseteq K$. Let $K_i$, $i \leq m$ be closed cones. Is conv$(\cup_{i=1}^{m}K_i)$ closed?
2
votes
1answer
97 views

Is it true that the convex hull of a finite union compact convex sets compact?

Currently I am studying Behrend's $M$-structure and Banach-Stone Theorem. He introduced the following notation. Notation: Consider a Banach space $X.$ Fix $x\in X$ and $r\geq 0.$ Consider the set $...
1
vote
2answers
32 views

Is it true that $\text{co}(A) = \{\lambda a + (1-\lambda)b: a,b\in A\}?$

Let $A$ be a set. We define convex hull of $A$ to be $$\text{co}(A) = \bigg\{ \sum_{i=1}^n\lambda_ia_i: 0\leq \lambda_i\leq 1 , \sum_{i=1}^n\lambda_i=1, a_i\in A \text{ for all }1\leq i\leq n \bigg\}...
0
votes
1answer
70 views

Extreme points of a convex hull on the $n$-sphere

Let $$\Sigma = \left\{ (x_1,\dots, x_n) \in \mathbb{R}^n : \sum_{i=1}^n x_i^2 = 1 \right\}$$ and let $S$ be a finite subset of $\Sigma$ and let $C$ be the convex hull of $S$. Show that any point of $S$...
2
votes
0answers
41 views

Optimizing over union of convex polyhedra

Suppose I have a set of non-empty polyhedra $P_1, \dots, P_n$ , and I wish to optimize a linear function, $c^\top x$, over their union. Is the optimal point of the convex hull of the vertices of the ...
1
vote
4answers
42 views

Non-Convex body built from union of $N$ convex bodies

Given any compact, closed non-convex body $K \subset \mathbb{R}^n$ (containing NO holes!), is there a set of $N$ compact convex closed bodies, $\left\lbrace C_i \right\rbrace_{i=1}^N$ (where for every ...
0
votes
1answer
34 views

Is the biconjugate of a convex function always greater than the original function?

I see in many sources that the biconjugate of a convex proper function is always less than the original function: $$f(x) \ge f^{**}(x)$$ But, when I try to prove this to myself,I get twisted up ...
0
votes
1answer
95 views

How to show $\partial f(x) =\{\nabla f(x) \}$ for a convex function?

I want to show that if $f:\mathbb{E}\rightarrow\mathbb{R}$ is convex, and differentiable at $x$, then $\partial f(x) = \{ \nabla f(x) \} $ . I understand that for a convex function, we have the ...
1
vote
1answer
127 views

How is the subdifferential of the $l_2$ norm at $x=0$ the polar of the unit ball?

I was reviewing subdifferentials, and my professor writes on the board that the subdifferential of the $l_2$ norm at $x=0$ is the polar of the unit ball? I tried to work through this myself: Let $\...
0
votes
2answers
22 views

Closed-form expression for intersection of convex hulls of two finite sets of points

Consider an optimization problem where the decision variables are two finite subsets of $\mathbb{R}^n$ each containing $k$ elements: $$ X = [x_1, x_2, \dots, x_k],\ \ Y = [y_1, y_2, \dots, y_k] $$ We ...
0
votes
1answer
65 views

Show that if z is an extreme point of X = co{$x_1,…,x_k$} then z = $x_i$ for some i

A question on a quiz that I couldn't figure out: Let X = co{$x_1, x_2,..., x_k$} where $x_i$ ∈ $\mathbb{R^n}$, $i = 1,2,...,k$. (Note: co{$x_1,...,x_k$} stands for convex hull of {$x_1,...,x_k$}) (a) ...
0
votes
1answer
72 views

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?
1
vote
2answers
56 views

looking for finding the shape of a 3D polytope in $\mathbb{R^{6}}$

does any body have information about below polytope? Suppose we have 6 points in $\mathbb{R^{6}}$: $(1,1,1,0,0,0),(0,1,1,1,0,0),(0,0,1,1,1,0),(0,0,0,1,1,1),(1,0,0,0,1,1),(1,1,0,0,0,1)$ what is ...
1
vote
1answer
182 views

Convex hulls and convex combinations

Why is it possible to represent every point contained in a convex hull as a convex combination of the points that generate the convex hull? I am studying convex hulls for linear programming. I have ...
0
votes
1answer
20 views

situation of simplex in the same layer with the same barycenter

a layer in $R^{k}$ is sum of entries of a integer point. for example $(1,5,3)$ lie on the layer $1+5+3=9$. suppose we have a simplex whose vertices are permuted an integer point. for example a ...
0
votes
1answer
24 views

Can a conic-hull be not trivial and bounded?

Consider $X\subseteq\mathbb{R}^n$ The conic-hull of $X$ is cone$(X)=\{\lambda_1x_1+...+\lambda_nx_n\ :\ \lambda_i\geq0\ ,\ x_i\in X\}$ Can that set ever be not just $\{0\}$ and be bounded?
0
votes
0answers
34 views

Ways to find non trivial combination of zero from linearly dependent vectors

For a set of m vectors in $\mathbb{R}^n$ with $m>n$ is there an algorithm that finds the coefficients $\{\lambda_i\}$ not all zero such that $\lambda_1v_1+...+ \lambda_mv_m=0$? If there is a ...
0
votes
0answers
23 views

How to tranform the quasilinear constraint into convex or affine constraint?

I have the following problem: $\max_{z_{i,j,v}} \sum_{i}\sum_{j}\sum_{v} z_{i,j,v}$ $s.t. \sum_{i}\sum_{j} z_{i,j,v} = \max_{i,j} z_{i,j,v}$ $z_{i,j,v}\in[0,1]$ I can prove the constraint is ...