An optimal convex hull algorithm in any fixed dimension (Q1312190)

This very interesting paper gives a solution to an outstanding problem in computational geometry. The author presents an deterministic algorithm for computing the convex hull of \(n\) points in any fixed dimension \(d\) in \(O(n \log n+n^{\lfloor d/2 \rfloor}) \) time. This algorithm is optimal in the worst case, but it is not output-sensitive. It is an open problem to bring down the complexity for this problem to the lower bound of \(\Omega (h+n \log h)\), where \(h\) is the facial complexity of the hull. The solution of the paper is based on a derandomizing-technique developed by the author. The counterpart of the algorithm given here is a probabilistic incremental method given in a known Las Vegas algorithm with optimal expected time. The result of the paper seems to be the first example of a successfully derandomized Las Vegas incremental algorithm. The base is a deterministic version of a Monte Carlo integration method, which seems to be useful for other problems also. A by-product of the result is an algorithm for computing the Voronoi diagram of \(n\) points in \(d\)-space in the same optimal time. Besides this results the author introduces the following ideas: 1. A scheme for producing ``random-looking''-permutations. 2. An elementary error analysis to cope with faulty calculations in the Raghavan-Spencer method.