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$.
40
questions
8
votes
1
answer
149
views
Convex hulls of compact sets in a 2-manifold
Let $(\mathbb{R}^2,g)$ be a complete Riemannian manifold. Let $K\subset \mathbb{R}^2$ be a compact, connected set, and let $\text{conv}(K)$ be its convex hull, i.e., the intersection of all ...
- 381
14
votes
7
answers
2k
views
Finite set of non-collinear points on plane with every point having ≥ 3 equidistant neighbors? [closed]
Does there exist a finite set of points on the Euclidean plane, such that:
No 3 points are collinear, and
Every one of the points has (at least) three other points in the set at the same distance ...
- 169
0
votes
0
answers
49
views
Given m vectors in n dimension where m>>>n, how do you find the vectors that define the largest convex hull constructed with the vectors?
Say there are m vectors in n dimensional space (m>>>n).
There exists a largest convex hull defined by a subset of those vectors.
My goal is to describe the space that is strictly inside the ...
2
votes
1
answer
83
views
Commutation of linear maps and extreme points
Let $X,Y$ be real vector spaces, $T: X\to Y$ be a linear map, and fix a nonempty $S\subseteq X$ (we do not assume that $S$ is neither convex nor compact (indeed, right now we do not assume any ...
- 1,422
6
votes
1
answer
162
views
Convex hull of a variety in real space
I am a physicist currently working on a question posed as part of an algebraic geometric description of a physical set:
I did not find a question that is closely related to what I am searching for yet,...
- 71
0
votes
1
answer
96
views
How hard is a linear programming with a bounded constraint?
Background: I am reading Greg Kuperberg's answer to the question Deciding membership in a convex hull. I am thinking about the complexity of ''Deciding membership in a convex hull''.
Restate the ...
1
vote
1
answer
519
views
Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]
Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
- 11
2
votes
2
answers
188
views
Minimum Euclidean squared norm in the convex hull of points with rational coordinates
This is probably known, but I have not located a reference.
Let $P$ be the convex hull of $k$ points in $\mathbb R^n$ with rational coordinates. Consider the Euclidean square norm function $F:P\to\...
- 4,606
8
votes
1
answer
913
views
Two questions on the permutohedron
The $n$-dimensional permutohedron $P_n$ is the polytope given by the convex hull of all the possible permutations of the vector $(1,2,\dots,n+1)\in\mathbb{R}^{n+1}$. So it has $(n+1)!$ vertexes.
I ...
user82886
2
votes
0
answers
59
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, ...
- 183
2
votes
1
answer
123
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 $...
- 417
5
votes
1
answer
414
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: ...
- 1,266
2
votes
1
answer
142
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 (...
- 23
0
votes
0
answers
30
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 ...
- 11.7k
1
vote
0
answers
49
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 ...
- 11
4
votes
2
answers
666
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, ...
- 49
2
votes
1
answer
212
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 ...
- 51
16
votes
1
answer
523
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,...
- 213
1
vote
0
answers
40
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 $...
- 11.7k
1
vote
0
answers
80
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 ...
- 607
2
votes
0
answers
95
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 ...
- 412
1
vote
0
answers
55
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 $...
- 151
2
votes
2
answers
250
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, ...
- 3,959
11
votes
2
answers
463
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( ...
- 1,971
6
votes
2
answers
147
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, ...
- 61
0
votes
1
answer
247
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 ...
- 121
1
vote
0
answers
84
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 ...
- 867
1
vote
0
answers
177
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/...
- 11
6
votes
1
answer
2k
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 ...
- 61
6
votes
0
answers
109
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 ...
- 607
3
votes
1
answer
198
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)\...
- 43
25
votes
2
answers
651
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 ...
- 4,426
10
votes
4
answers
853
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 ...
- 101
16
votes
3
answers
4k
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 ...
- 146k
4
votes
3
answers
2k
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}...
- 245
4
votes
3
answers
1k
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\...
- 43
2
votes
2
answers
667
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?
- 25
12
votes
2
answers
2k
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?
...
- 403
18
votes
3
answers
2k
views
Deciding membership in a convex hull
Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.
This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
- 637
27
votes
7
answers
5k
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 ...
- 40.5k