# Questions tagged [convex-hulls]

The convex hull of a set $X$ of points in a Euclidean space is the smallest convex set that contains $X$.

31
questions

**2**

votes

**0**answers

51 views

### Convex hull of prefix sum of $n$ ordered random points

Suppose we have $n$ ordered realizations of a random variable uniformly distributed over the unit cube $P = (p_1, p_2, \cdots, p_n), p_i \in [0,1]^d $. And we obtain the prefix sum $S = (p_1, p_1+p_2, ...

**2**

votes

**1**answer

85 views

### Polytope with most faces

Fix $m,n \in \mathbb{N}$ with $m \ge n+1$. Take $m$ points in general position in $\mathbb{R}^n$ and let $P$ be their convex hull. What is the maximal number of (external, codimension-one) faces that $...

**5**

votes

**1**answer

191 views

### How to apply Hahn-Banach to the convex hull?

I am trying to understand the proof of Lemma 4.1.2 in Michel Talagrand's publication from 1995 on concentration inequalities (see below for the precise question statement):
A bit of context: ...

**0**

votes

**0**answers

13 views

### Defining planar geometric shape hulls via graph connectivity

A fundamental problem in Computational Geometry is to generalize convex hulls to simple polygons that partition a given finite set $\boldsymbol{P}$ into two sets $\boldsymbol{C}$ of corners and $\...

**2**

votes

**1**answer

112 views

### Number of orthants intersected by a convex hull

I'm trying to figure out the following problem:
Let $x_1,\ldots,x_k\in\mathbb{R}^n$ be some points for some $k<n$. Let $\mbox{conv} (x_1,\ldots,x_k)$ be their convex hull. I'm looking for a tight (...

**0**

votes

**0**answers

28 views

### Counterexample to a generalization of planar convex hulls

I am looking for a counter example to the following conjecture:
for every finite compact region $\mathcal{R}\subset\mathbb{R}^2$ that is defined by a rectifiable Jordan curve
and every fixed and ...

**1**

vote

**0**answers

48 views

### How does one translate from convex hull to a set of facets (inequalities)? [duplicate]

Suppose I have defined a convex set as the convex hull of a set of points. (I know that all these points are "extremal points" of the convex set.) I know want to translate this description of the ...

**4**

votes

**2**answers

421 views

### Convex hull in a discrete space [closed]

I know some algorithms which compute the convex hull in a continuous space.
Are there efficient algorithms to compute it in a discrete domain?
For example in 3D discrete space, given the blue points, ...

**2**

votes

**1**answer

136 views

### Algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane

I am trying to find an algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane, with a total of $n$ vertices. Let $h$ denote the number of vertices on ...

**16**

votes

**1**answer

359 views

### Convex hull of all rank-$1$ $\{-1, 1\}$-matrices?

Consider the set $\mathbb{R}^{m \times n}$ of $m \times n$ matrices. I am particularly interested in properties of polytope $P$ defined as a convex hull of all $\{-1,1\}$ matrices of rank $1$, that is,...

**1**

vote

**0**answers

34 views

### Algorithm for Calculating Spheric Convex Hulls of Finite Pointsets

Let the Spheric Convex Hull ($\mathrm{CH}_S$) denote the intersection of all closed spheres that contain a compact $\Sigma\subset\mathbb{R}^n$ and on their boundary at least $n+1$ distinct points of $...

**1**

vote

**0**answers

63 views

### Compute the edge-skeleton of a polytope given by its vertices

Let $P$ be a polytope given by a vertex description, i.e., $P=conv(\{x_1,\ldots,x_m\})\subset\mathbb{R}^n$.
Is there an efficient (i.e., not relying on Linear Programming) algorithm to compute the ...

**2**

votes

**0**answers

90 views

### Convex hull of piece-wise linear functions

Let $K>1$ be a positive integer. Consider a function class $$\mathcal{F}_K:=\Big\{\max_{1\leq k\leq K} a_k^\top x + b_k:\ ||a_k||\leq 1, |b_k|\leq 1, \forall 1\leq k\leq K \Big\}$$ on some compact ...

**1**

vote

**0**answers

52 views

### Are the sets whose convex hull surface admits multiple representations a shy set of sets?

Consider a compact subset $A$ of $R^n$. Let me call $A$ special if any point $x$ that is on the boundary of $\textsf{conv.hull}(A)$ admits a unique representation as a convex combination of points in $...

**2**

votes

**2**answers

221 views

### How to show that the origin is not in the convex hull, in this problem?

I am given $3$ points $(x_i,y_i,z_i) \in \mathbb{R}^3\setminus \{\mathbf{0} \}$, for $i=1,2,3$, satisfying the following two polynomial equations (the first equation is actually not the intended one, ...

**11**

votes

**2**answers

397 views

### Convex hull of the Stiefel manifold with non-negativity constraints

Consider the Stiefel manifold
$$\mathrm{St}(n,k) :=\{X \in \mathbb{R}^{n\times k} : X^TX = I_k\},$$
where $I_k$ is the $k$-dimensional identity matrix. It is well known that
$$\mathrm{conv} \left( ...

**6**

votes

**2**answers

143 views

### Inequality on permutation polytope

Let $a = (a_1, \cdots, a_n), b = (b_1, \cdots, b_n), c = (c_1, \cdots, c_n) \in \mathbb{R}^n$ with $a_1 \geq \cdots \geq a_n, b_1 \geq \cdots \geq b_n, 0 < c_1 \leq \cdots \leq c_n$.
In addition, ...

**0**

votes

**1**answer

159 views

### Finding the minimum-area parallelogram containing all vertices of a cuboid projected to a plane

Description edited after comments:
Let's say I have a 3d cuboid that I projected onto a 2d plane. Now I want to find the minimum-area parallelogram that contains all those projected vertices. How do ...

**1**

vote

**0**answers

74 views

### quick hull algorithm detail

When using quick hull algorithm to find the polytope for half space intersection, we are required to provide an interior point to the solver qhalf.
In other words, providing
$$Ax \le b$$
is not ...

**1**

vote

**0**answers

144 views

### Facet Enumeration Problem nondegeneracy case

Hello in case of a nondegeneracy case of the Facet Enumeration Problem, there is a polynomial algorithm for the convex hull problem as written here https://www.inf.ethz.ch/personal/fukudak/polyfaq/...

**6**

votes

**1**answer

1k views

### Approximation of convex hull in high dimension

What are efficient methods (polytime) to compute an approximation of the convex hull in high dimension (say, $30000$) for a given set of points?
Edit:
I am looking for an algorithm for getting the ...

**6**

votes

**0**answers

100 views

### Convex hull of all-ones principal submatrices

For a subset $S$ of $\{1,\ldots,n\}$,
let $\mathbf{1}_S\in\{0,1\}^n$ denote the indicator vector of $S$, with a $1$ on the $i$th coordinate iff $i\in S$. Let $\mathcal{X}$ denote the convex-hull of ...

**3**

votes

**1**answer

172 views

### How to show it is contained in a convex hull?

There are $(d+1)f$ points (denote the set of all points as $S$) in $\mathbb{R}^d$, that can be divide into $d+1$ disjoint sets $F_1,...,F_{d+1}$, each set of size $f$. If we have
$$
\mathcal{H}(F_i)\...

**25**

votes

**2**answers

627 views

### Convex hull of total orders

Let $n$ be a positive integer and $\prec$ an arbitray total order on $\{1,\dots,n\}$. I associate to this order a vector $v$ with one coordinate for every pair $(i,j)$ s.t. $1\leq i\neq j \leq n$, by ...

**8**

votes

**4**answers

704 views

### Convex Hull of Path Connected sets

This is a pretty easy question to ask, but haven't seen it anywhere.
Suppose I have some continuous path $X$ in $\mathbb{R}^n$ and I want to get the convex hull of $X$, $\operatorname{co}(X)$.
Is it ...

**15**

votes

**3**answers

3k views

### Convex hull on a Riemannian manifold

Let $M$ be a complete Riemannian 2-manifold.
Define a subset $C$ of $M$ to be convex
if all shortest paths between any two points
$x,y \in C$ are completely contained within $C$.
For a finite set of ...

**4**

votes

**3**answers

1k views

### Minimum norm of convex hull

I am currently stuck at a problem which seems too easy to be stuck at to me...
Summary
Let $H$ be the convex hull of the points $d_1,\ldots, d_n\in \mathbb{R}^d$. How can one compute
\[\min_{x\in H}...

**3**

votes

**3**answers

758 views

### Holomorphically Convex Hull a Subset of the convex hull of

This comes from Hörmander's "An Introduction to Complex Analysis in Several Variables".
We defined the $A(\Omega)$-hull (analytic functions in an open set $\Omega$). $\hat{K}$ of a compact set $K\...

**2**

votes

**2**answers

635 views

### Where to submit a new convex hull algorithm?

Recently, I devised a new convex hull algorithm. Is there any forum where I can submit my work?

**12**

votes

**2**answers

1k views

### Convex hull of $k$ random points

Suppose we have $k$ realizations of a random variable uniformly distributed over the unit cube $[0,1]^n$.
What is the probability that their convex hull has all of the $k$ points as extreme points?
...

**25**

votes

**7**answers

4k views

### Convex hull in CAT(0)

Let $X$ be complete $\mathop{CAT}(0)$-space and $K\subset X$ be a compact subset.
Is it true that convex hull of $K$ is compact?
Comments:
Convex hull of $K$ = intersection of all closed convex sets ...