Questions tagged [convex-hull]

The tag has no usage guidance.

8 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
92 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 ...
2
votes
1answer
329 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
31 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
124 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
37 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
25 views

Do isomorphic polytopes have same extension complexity?

Is there a simple proof of the fact that isomorphic polytopes have similar extension complexity?
0
votes
0answers
12 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)$?
0
votes
0answers
484 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 ...