# 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
Filter by
Sorted by
Tagged with
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
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
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 ...
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
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
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
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
188 views

• 183
123 views

• 11.7k
1 vote
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
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
55 views

• 43
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?
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
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
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 ...