6
votes
Accepted
Difference between convex hull algorithms
If $n$ is the number of 2D points, let $h \le n$ be the number of points on the convex hull. Then:
Gift wrapping takes time $\Theta(n h)$, which can be $\Theta(n^2)$ in the worst case. It is ...
- 3,424
4
votes
Accepted
The use of binary search when determining whether a point lies inside a given convex hull
So, the situation is that you have the vertices $\mathbf{v}_i$ of a polygon that defines a convex hull and a point $\mathbf{O}$ inside this polygon. Furthermore you have the vectors connecting $\...
4
votes
Accepted
The optimal complexity of intersecting a line with a convex hull of a set of points in 2d
What you're asking for reduces to finding the so-called bridges of the convex hull across this line, i.e. the two edges of the convex hull which have one vertex on both sides of the line. Kirkpatrick ...
- 2,542
3
votes
Accepted
Why isn't there a computational "Carpenter's Algorithm" for Planar Convex Hull?
Carpenter's algorithm isn't implementable in a computer and makes assumptions that are not realistic in practice, such as that nature works with infinite-precision arithmetic and that you can choose ...
D.W.♦
- 164k
3
votes
Accepted
Efficient algorithm to compute the diameter of a convex set?
I suspect that if the points in your set are expressed as $Ax \le b$ and you're considering the Euclidean distance, then you can solve the following quadratic program with the ellipsoid method:
$$
\...
- 29.6k
3
votes
Accepted
minimum number of points a convex hull must have
The convex hull of 10 collinear points is the line segment between the two extreme points.
No, a convex hull does not have to be convex polygon. A convex hull can be a point, a line segment, a ray, a ...
- 39.1k
3
votes
If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?
A first order approximation is that convex programs are tractable, .i.e., most problems you can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you ...
- 131
3
votes
Accepted
Convex hull of fixed size
It is not true. As you know, we can reduce sorting numbers to finding convex hull (see here). So, we know that size of the convex hull, in this case, is $N$. However, we can't compute convex hull in ...
- 3,582
3
votes
Optimization over convex combinations in a circle
A pragmatic approach is just to use off-the-shelf black-box mathematical optimization algorithms.
In particular, define parameters $\theta_1,\theta_2,\theta_3$, representing the angle from the ...
D.W.♦
- 164k
2
votes
Internal tangent intersection of two point sets in linear time
I found a way to solve the problem in my case -- maybe that only applies to the special conditions found in the paper. There, the two point sets can be assumed to be non-collinear and always separable ...
- 370
2
votes
Convex-hull of a star shaped polygon in O(n)
Graham scan for a convex hull works if you have an ordering of points $a_1,a_2,...a_N$ such that you have a sequence $p_1 < p_2 <...< p_k$ where your convex hull is $a_{p_1}, a_{p_2},...,a_{...
- 201
2
votes
Accepted
Lower bound for point set triangulation
No, that's not a valid argument. You'd have to describe how to find which part of the triangulation is the convex hull, in $o(n \log n)$ time, to make that a valid argument.
D.W.♦
- 164k
2
votes
Accepted
Is binary-search really required in Chan's convex hull algorithm?
I think this is correct... see 2. Chan’s Algorithm p4, Remark.
Remark. Using a more clever search strategy instead of many binary searches one can handle the conquer phase in $O(n)$ time. However, ...
- 126
2
votes
Accepted
Upper and lower tangent line to convex hull from a point
Let's assume that the convex polygon $P$ is defined as an ordered list $(p_0,p_1,...,p_{n-1})$ of points, and for each such point $p \in P$ we are able in $O(1)$ time to find a previous point $Prev(p)$...
- 3,098
2
votes
Computing convex hull by triangle point inclusion
The following algorithm may be what they mean:
Initialize $H\leftarrow \emptyset$.
For each point $p\in P$, test if $p$ lies inside the convex hull of $H$. If it does not lie inside the convex hull, ...
- 8,323
2
votes
What is the optimal algorithm for merging an arbitrary number of convex hulls?
the result will not be linear.
Doing the merge between partial result and the next hull will be $O(x_{i-1}+m_i)$ where $x_{i-1}$ is the amount of points in the partial result.
So doing the merge ...
- 4,646
2
votes
How can vector angle comparison between lattice points be done without using floating-points? (Convex Hull)
In computational geometry, we often sort the points clockwise or anti-clockwise.
For example, in Graham's scan, the algorithm sorts the points with respect to $(x_0,y_0)$ in clockwise or anti-...
- 6,237
1
vote
Accepted
The updated convex hull algorithms in 2023?
The algorithm by Chazelle in the linked paper, for general dimension, is optimal in terms of worst case asymptotic complexity. So in terms of theoretical results for finding exact solutions, this ...
- 8,323
1
vote
Accepted
Collinear convex hull
The problem is to find the outer boundary of the union of the squares. We state two claims that help design an $O(n)$ algorithm, where $n$ are the number of given squares.
Let $S_1,\dotsc,S_n$ be the ...
- 6,237
1
vote
What is the optimal algorithm for merging an arbitrary number of convex hulls?
What is the most efficient way to merge convex hulls?
It depends and we can't really now before hand. Let me first illustrate why there is no general recipe for this.
If we add two of those convex ...
- 143
1
vote
Accepted
Computing convex hull by triangle point inclusion
The authors could also mean Quick hull algorithm. It is based on discarding the points that lie inside a triangle. A naive implementation of the algorithm runs in $O(n^2)$ time.
- 6,237
1
vote
Finidng edges of convexhull from rectangles
If you have $n$ rectangles, take the convex hull of the $4n$ points given by the corners of those rectangles. This gives you exactly what you want, and you can use any standard algorithm for ...
D.W.♦
- 164k
1
vote
If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?
There are special cases of convex problems that can be solved in polynomial time, e.g. a convex QP defined over a simplex. In general, however, convex programming is NP-hard. However, NP-hard by no ...
- 121
1
vote
Accepted
Determine image of hypercube under linear map
I eventually found an answer. The image of a hypercube in $\Bbb R^3$ under a linear map is called a zonohedron. They can be calculated efficiently, for example using the algorithm in An Efficient ...
- 131
1
vote
Minimum distance between two convex hulls maximized
Given a pair of points $A,B$, you can split the the data into the points that are to the left of the line $AB$ (or on the line) vs the points that are strictly to the right of $AB$. Then you can ...
D.W.♦
- 164k
1
vote
Accepted
Why is the graph inside Graham Scan always planar
The edges examined never intersect because all points are first sorted in terms of angle from the starting point, and then traversed counterclockwise sequentially. By examining edges to each point ...
- 106
Only top scored, non community-wiki answers of a minimum length are eligible