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 (1991) 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.

Full text not available from this repository.
Export as:
Editorial actions: View Item View Item (Login required)
Content information:
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
Related URLs:
Deposit Information:
ZAIK Number: zpr90-094
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 19 Jan 2012 12:05