Computing the convex hull in the Euclidean plane in linear expected time
Jünger, Michael and Borgwardt, Karl H. and Gaffke, Norbert and Reinelt, Gerhard
Computing the convex hull in the Euclidean plane in linear expected time.
Published in: Applied geometry and discrete mathematics : the Victor Klee Festschrift., Series in discrete mathematics and theoretical computer science. 4 American Math. Soc. 1991, pp. 91-108.
There are many algorithms for computing the convex hull of a set of n points in the Euclidean plane in worst case time O(n*ln(n)). It is also known that O(n) average time behavior can be achieved under the assumption that the n points are independently and uniformly distributed over the unit square or the unit disk. We will show how any O(n*ln(n)) worst case time algorithm for the convex hull can be converted into an O(n) average time algorithm under this assumption. Also, it turns out that O(n) average time is still obtained if algorithms of higher worst case time complexity are used. Finally, we will give a computational comparison of our method with other linear expected time algorithms for problems instances in the unit square.
|Item Type:||Collection Item|
|Citations:||6 (Google Scholar) ||
|Uncontrolled Keywords:||convex hull algorithms expected runtime|
|Divisions:||Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger|
|Depositing User:||Prof. Dr. Michael Jünger|
|Date Deposited:||27 Jun 2003 00:00|
|Last Modified:||19 Jan 2012 12:05|