Questions tagged [convex-hull]
The convex-hull tag has no usage guidance.
42
questions
5
votes
2
answers
94
views
The optimal complexity of intersecting a line with a convex hull of a set of points in 2d
The problem: in 2d, given a line and an unordered set of $N$ points with real coordinates, find the intersection between the line and the convex hull of the points.
Clearly, one can explicitly ...
- 83
1
vote
2
answers
67
views
Computing convex hull by triangle point inclusion
In my computational geometry book they present the following $O(n^4)$ algorithm for computing the convex hull of a pointset $P \subset \mathbb{R}^2$ assuming general position on the points in $P$: For ...
- 190
1
vote
1
answer
47
views
Shamos algorithm , cannot understand the Area part
I wanted to find shortest time algorithm for finding the diameter of a convex hull, so I found Shamos algorithm on wikipedia:
...
- 163
1
vote
1
answer
35
views
How can vector angle comparison between lattice points be done without using floating-points? (Convex Hull)
Let's say I have a point $(x_0, y_0)$, and some other points $(x_1, y_1), (x_2, y_2) ... (x_n, y_n)$, such that all of them are lattice points; all have integer coordinates. Let's further assume that ...
- 425
0
votes
0
answers
23
views
After removing a point in the convex hull, can the remaining points construct a convex hull?
With any convex hull of n points, after delete a point from that hull, can the remaining n-1 points still construct a new convex hull? How can we prove that?
3
votes
1
answer
245
views
Difference between convex hull algorithms
I was wondering what are the main differences in terms of efficiency of convex hull algorithms?
Brute force algorithm is inefficient due to iterating over every three vertices in our set and its time ...
- 225
1
vote
1
answer
552
views
Upper and lower tangent line to convex hull from a point
Is it possible to find an upper and lower tangent line to a convex hull in $log(n)$ time where $n$ is number of points on a convex hull? I have just done it in linear time where I checked for upper ...
- 225
2
votes
1
answer
155
views
Efficient algorithm to compute the diameter of a convex set?
Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set?
It is possible to do it efficiently for a set of points, but imagine that the ...
- 23
1
vote
1
answer
157
views
minimum number of points a convex hull must have
Quick question:
Say for example there are 10 colinear points. my question is does a convex hull have to be a convex polygon? or can it be a line as well according to the formal definition of the ...
- 201
0
votes
0
answers
15
views
minimum moves to be made to get out of convex hull
Given a convex hull in $XY$ plane. and we have $n$ points sitting inside it. In one move we can move all the points to right by $1$ or move all the points to up by $1$. what are the minimum number of ...
-1
votes
2
answers
140
views
Concentric convex hulls
Given N points in a 2D plane, if we start at a given point and start including points in a set ordered by their distance from the starting point. After including every point, we check if there is a ...
- 1
0
votes
0
answers
47
views
Why are basic feasible solutions the same as vertices geometrically?
The first line on the Wikipedia page for basic feasible solutions reads, ...
- 1
0
votes
1
answer
48
views
Finidng edges of convexhull from rectangles
Green Boxes = rectangles
red dots = edge points
red lines = to be generated from convex hull algorithm
I have a problem with creating the convex hull algorithm.
I want to select or collect all the ...
- 1
4
votes
0
answers
51
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 ...
- 12.4k
3
votes
0
answers
49
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 ...
- 131
4
votes
0
answers
58
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, ...
- 41
6
votes
2
answers
2k
views
If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?
Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time.
Now I am learning that a convex optimization problem can ...
- 583
2
votes
1
answer
69
views
Determine image of hypercube under linear map
Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
- 131
1
vote
0
answers
74
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\...
- 111
3
votes
2
answers
895
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 ...
- 31
3
votes
1
answer
385
views
Is binary-search really required in Chan's convex hull algorithm?
I have a little doubt about Chan's algorithm.
From Wikipedia's description we see that the second phase of an algorithm works with $K = \mathrm{ceil}(\frac{n}{m})$ subsets $Q_i$. The goal of the ...
- 247
2
votes
1
answer
636
views
Minimum distance between two convex hulls maximized
I want to implement a program that splits a set $S$ of $n$ points in the plane into two sets such that the distance of the convex hulls of the two sets is maximized.
It should be done in $O(n^3)$.
I ...
- 121
3
votes
1
answer
136
views
Why is the graph inside Graham Scan always planar
One of the ways to prove that Graham Scan constructs convex hull in linear time is using planarity of the graph obtained by running the algorithm. This graph is always planar, so according to Euler's ...
- 151
0
votes
0
answers
18
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)$?
- 129
2
votes
1
answer
82
views
Lower bound for point set triangulation
How can I show that the lower bound for getting a triangulation from a point set in the plane is $\Omega(n \log n)$?
I know that the lower bound for finding the convex hull for a point set is also $\...
- 23
1
vote
1
answer
260
views
How to prove that non-antipodal vertices cannot be a diameter of a convex polygon?
I am learning Shamos's rotating calipers algorithm for finding the diameter of a convex polygon in his Ph.D. thesis; Page 78.
It reads
Consult Figure 3.23 and notice that parallel lines of support ...
- 9,219
1
vote
1
answer
161
views
Convex hull of fixed size
I have heard that the quickhull algorithm can be modified if the size of the convex hull (the number of points it consists of) is known beforehand, in which case it will run in linear time. What ...
- 167
6
votes
1
answer
561
views
How to find the supremum over all the "good" (interior) polytopes for a given set of 3D points?
Let $S \subset \mathbf{R}^3$ be a set of points in 3D and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.
We consider a convex polytope $P$ good / interior if:
$P$ is wholly contained ...
- 239
1
vote
0
answers
204
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 ...
- 4,537
2
votes
1
answer
1k
views
The use of binary search when determining whether a point lies inside a given convex hull
In an answer to the problem of determining whether or not a point lies inside a given convex hull, a thesis is mentioned, which says :
For repeated queries with preprocessing allowed, we develop a ...
1
vote
1
answer
87
views
How to convert two conflicting objective functions into a single objective function
I have two objective functions say f1 where I have to minimize (X+Y) and another function f2 where I have to maximize (A-B). The two functions are conflicting.
I need to convert them into a ...
- 113
2
votes
1
answer
175
views
Internal tangent intersection of two point sets in linear time
I need to find the intersection of the internal tangents of two point sets $V_a, V_b$ in $\mathbb{R}^2$, defined via their convex hulls. We can assume that the sets are disjoint and linearly separable,...
- 370
1
vote
0
answers
744
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 ...
- 169
4
votes
1
answer
1k
views
Convex-hull of a star shaped polygon in O(n)
I'm trying to develop an algorithm to find a convex hull of a star shaped polygon in $O(n)$ time. The specific problem, which is also described here, is as follows:
A polygon $P$ is star-shaped if ...
user20691
5
votes
1
answer
207
views
Optimization over convex combinations in a circle
Consider the following situation: given a triangle $ABC$ inscribed in a circle, define $f$ as the product
$$f(P) = d(P, A) \; d(P,B) \; d(P,C)$$
where $P$ is a point on the circle and $d$ are ...
- 51
6
votes
0
answers
103
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 ...
- 61
-1
votes
1
answer
199
views
Convex Hull Problem proof [closed]
In a given set of points, Prove that the two farthest points are the vertices of the convex hull,
How can i get the accurate proof, so that the question can be explained in the class
3
votes
1
answer
436
views
Convex hull algorithm in $O(\min(mn, n\log n))$
I am looking for an algorithm to compute the convex hull of a set of $n$ points $P$. The hull should contains $m$ points. This algorithm should work in time $O(\min(mn,n \log n))$.
My first guess was ...
- 269
1
vote
0
answers
52
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 ...
- 11
2
votes
1
answer
233
views
About the Max-Cut SDP
The Max-Cut optimization problem on a graph $G=(V,E)$ can be written as the question of wanting to maximize the function $\frac{1}{4} \sum_{(i,j) \in E } (x_i -x_j)^2$ under the constraint $x_i^2 = 1, ...
- 493
3
votes
1
answer
94
views
How to use convex hull for this problem
Problem:
You are to collect a total of $N$ litres of red and $M$ litres of blue liquid. For doing job $i$ for time $t$, you get $a_i t$ litres of red and $b_i t$ litres of blue liquid. $t$ need not ...
- 1,239
0
votes
1
answer
388
views
Understanding a few intricacies related to two naive algorithms to compute the convex hull of a set of points
I already understood how the well-known algorithms like Graham's scan, Quickhull, etc. work, but I have difficulties in understanding 2 naive algorithms to compute the convex hull:
Let $S= \{p_1, \...
- 421