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.

Abstract

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.

Actions:

Full text not available from this repository.

Export as:	HTML CitationASCII CitationOpenURL ContextObjectEndNoteBibTeXMPEG-21 DIDLEP3 XMLJSONAtomReference ManagerSimple MetadataRefer
Editorial actions:	View Item (Login required)