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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Perhaps this is better suited to cstheory. $\endgroup$– Yuval FilmusMay 21, 2013 at 22:55
-
$\begingroup$ Did you try to google it? $\endgroup$– Yuval FilmusMay 21, 2013 at 23:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
answered May 21, 2013 at 23:02