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 ...
Vincenzo's user avatar
  • 3,302
4 votes
Accepted

Convex hull algorithm in $O(\min(mn, n\log n))$

The simplest solution is to run two algorithms in parallel, one which runs in time $O(mn)$, and one which runs in time $O(n\log n)$. When one of the algorithms outputs a solution, you stop the other ...
Yuval Filmus's user avatar
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 $\...
Gregor Michalicek's user avatar
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 ...
Tassle's user avatar
  • 2,522
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.'s user avatar
  • 159k
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 ...
Johan Löfberg's user avatar
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: $$ \...
Steven's user avatar
  • 29.5k
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 ...
John L.'s user avatar
  • 39k
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 ...
OmG's user avatar
  • 3,572
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.'s user avatar
  • 159k
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 ...
phipsgabler's user avatar
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_{...
S. Pek's user avatar
  • 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.'s user avatar
  • 159k
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, ...
hqztrue's user avatar
  • 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)$...
HEKTO's user avatar
  • 3,088
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, ...
Discrete lizard's user avatar
  • 8,248
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-...
Inuyasha Yagami's user avatar
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 ...
ratchet freak's user avatar
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 ...
Inuyasha Yagami's user avatar
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.
Inuyasha Yagami's user avatar
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 ...
Oscar Cunningham's user avatar
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.'s user avatar
  • 159k
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 ...
Nikos Kazazakis's user avatar
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.'s user avatar
  • 159k
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 ...
Alex Lin's user avatar
  • 106
1 vote
Accepted

How to prove that non-antipodal vertices cannot be a diameter of a convex polygon?

I find it easier to prove the equivalent statement 'any pair $A,B$ such that the segment between them is a diameter of $P$ must be anti-podal': If the segment $s$ between $A,B$ is a diameter, ...
Discrete lizard's user avatar
  • 8,248

Only top scored, non community-wiki answers of a minimum length are eligible