3
$\begingroup$

I've been recently studying Monte-Carlo and other randomized methods for a lot of applications, and one that popped into my mind was making an (approximate) convex hull by examining random points, and try to get them inside the convex hull. I would like to know if there are algorithms for convex hulls that can improve the $O(n \log n)$ bound of comparison based algorithms, and the $O(n\cdot h)$ bound for Jarvis march and related to $O(n)$, either by building an approximate convex hull in $O(n)$ (with or without some approximation criteria) or by building an exact convex hull in expected linear time.

$\endgroup$
  • $\begingroup$ Perhaps this is better suited to cstheory. $\endgroup$ – Yuval Filmus May 21 '13 at 22:55
  • $\begingroup$ Did you try to google it? $\endgroup$ – Yuval Filmus May 21 '13 at 23:02
3
$\begingroup$

Two linear time approximation algorithms in the two-dimensional case are due to Bentely, Preparata and Faust and Stojmenović and Soisalon-Soininen.

A fast exact algorithm which works in expected linear time is due to Bentley, Clarkson and Levine. The paper is quite old, so maybe there are newer developments.

$\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.