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

0
votes
0answers
5 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
1answer
32 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 ...
-2
votes
3answers
62 views

convex combination of complex numbers [closed]

let $0<p_k<1$ $k=1,...,n$ such that $\sum_k p_k=1$ I'm trying to find $\varphi_1,\varphi_2,...,\varphi_n$ so that $$\sum_k p_ke^{i\varphi_k}=0$$
1
vote
1answer
21 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
135 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
23 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 ...
3
votes
1answer
33 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
44 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
15 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
40 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
34 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
11 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
36 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
47 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
9 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
18 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
17 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
32 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
86 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
18 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
27 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
52 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
77 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
76 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
37 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
58 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
50 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
47 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
81 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
28 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 \...
4
votes
1answer
78 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
43 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
44 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
30 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
79 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
108 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
44 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
24 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
33 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
57 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
117 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
80 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
43 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 ...