# 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$.

43 questions
Filter by
Sorted by
Tagged with
46 views

### Volume of all Voronoi cells in n-dimensional bounded space

How can one find the volume of all Voronoi cells (bounded and unbounded) in an $n$-dimensional bounded space? For instance, consider an $N$-dimensional space (hypercube) with bounds on each dimension ...
• 131
1 vote
90 views

### If $|P|<\infty$ and $C=P\cap\partial(\textrm{Conv}(P))$, then $P\subset\textrm{Conv}(C)$?

That is, if $P$ is a finite set, and $C$ is the set of points in $P$ which lie on the boundary of the convex hull of $P$, then is $P$ contained in the convex hull of $C$? It seems true intuitively. In ...
1 vote
64 views

### On known links between convexity and fuzzy logic

The following are thoughts I had during a joint work with P. Olver on maps from spheres to the convex hull of finitely many points in some finite-dimensional vector space. I do not wish to discuss the ...
• 4,971
202 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
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
55 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 ...
104 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,451
216 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
117 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
853 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
252 views

• 183
160 views

• 12.6k
1 vote
83 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
114 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
59 views

• 43
679 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?
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? ...
• 413
3k 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 ...
• 657
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 ...