A note on the expected time required to construct the outer layer
The expected time E(T) of the standard divide-and-conquer algorithm for finding the outer layer of a set of points in the plane depends upon the distribution of the points. Under the mild assumption that the points are independent random vectors and have a common bounded density with compact support, it is shown that \(E(T)=O(n)\).
scientific article; zbMATH DE number 3913676