1
$\begingroup$

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 all $O(n^3)$ triangles do an inclusion test for every point not yet discarded to see if they lie inside the triangle. If a point lies inside the current triangle discard it.

They mention that this can be improved to $O(n^2)$, but I fail to see how? The only $O(n^2)$ i can think of would be something like: Start at a point $P$ with maximum $y$-coordinate. Compute the angle to all other points in $P$ and choose the next point to be the point furthest to the left. Continue like so until you get to where you started, however this seems almost entirely unrelated to the triangle approach.

EDIT: I am aware of Jarvis march, Graham scan, Marriage before conquest etc, but my question is how specifically this idea of pruning points from triangles can yield a $O(n^2)$ algorithm for finding the convex hull

$\endgroup$
2
  • $\begingroup$ There are many convex hull algorithms that take $\Theta(n^2)$ time or better. en.wikipedia.org/wiki/Convex_hull_algorithms I'm guessing this isn't what you're asking, since it's so easy to find. What, specifically, is your question? $\endgroup$
    – jbapple
    Feb 13 at 1:37
  • $\begingroup$ My question is how specifically this idea of pruning points from triangles can yield a $O(n^2)$ algorithm for finding the convex hull. $\endgroup$
    – sn3jd3r
    Feb 13 at 1:38

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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, add it to $H$.

After we have visited all points, $H$ will be the convex hull of $P$. Since we can test whether a point lies in a convex hull in $O(|H|)$, the algorithm runs in $O(n^2)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.