# Tag Info

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
Accepted

• 201
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.
• 164k
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
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

### 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

### 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

### 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 ...
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 ...
• 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 ...
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 ...
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 ...
• 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