Questions tagged [convex-hull]
The convex-hull tag has no usage guidance.
10
questions with no upvoted or accepted answers
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
32 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
405 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
15 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
39 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)$?
