Questions tagged [convex-hull]

The tag has no usage guidance.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
93 views

$3$-dimensional convex hull using only a desired number of planes

I would like to find the convex polytope with the smallest volume that envelops (contains) all the points of a given 3D point cloud and that can be constructed from only $k$ planes. This is similar to ...
4
votes
0answers
31 views

Minimal set of inequalities including good points but excluding bad points

Suppose I have a collection of good convex sets and bad convex sets in $\mathbb{R}^d$ (where $d$ can be big). Each convex set is defined by a series of closed ranges in each dimension $d$ - a ...
4
votes
0answers
43 views

Convex hull in a discrete space

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
1answer
401 views

3D gift wrapping algorithm: how to find the first face in the convex hull?

I am implementing the gift wrapping algorithm to find the convex hull of a set of points in the 3D space. However, all the articles I have read seem to omit the description of the first step of the ...
1
vote
0answers
14 views

Distance from high dimensional convex hull to target point T

I have a set S of high dimensional points in Euclidean space, with convex hull H (not known); and some target point T in that space not in or on H. Rather than worry about calculating both H and the ...
1
vote
0answers
38 views

Game Theory: Using a convex hull algorithm to map out Pareto outcomes

I have started studying the Pareto efficiency notion in Game theory. The definition I am familiar with is this: Strategy profile $\mathbf{s}$ Pareto dominates strategy $\mathbf{s}'$ if for all $i\in\...
1
vote
0answers
136 views

Nested Convex Hulls Algorithm

The convex hull of a point set is a well understood problem and nice optimal solutions are known in the case of a finite point set and a simple polygon. For a convex polygon, the hull is the polygon ...
1
vote
0answers
541 views

Finding the Convex Layers of a given set of points

Definition of convex layers can be found at wikipedia. I was trying to understand this algorithm , which works in O(n log n) time, which is optimal. In the paper, the author has described two ...
1
vote
0answers
40 views

Does Optimal Substructure implies Convexity and vice versa?

In undergraduate CS, Dynamic Programming problems are often related to Overlapping Optimal Substructure (https://en.wikipedia.org/wiki/Optimal_substructure). Dynamic Programming is also often used in ...
0
votes
0answers
13 views

Convex Hull for known output size in O(n)

Given a set $S$ of $n$ planar points, we know that the $|CH(S)| = 17$. How can I create an algorithm that computes $CH(S)$ in $O(n)$ time? Why is it really $O(n)$?