Lower bounds proofs via Voronoi diagrams

It is shown that the large class of geometric problems satisfying an ¦[(n log n) time bound with respect to input size n decomposes into several subclasses of distinct algorithmic behaviour when considering higher dimensional spaces. With respect to the dimension d there are at least two levels of distinct complexity, on the one hand problems having a solution in at most O(n log n+dn) time, on the other hand problems satisfying an ¦[(dn log n) lower bound. This fact is shown by deriving new combinatorial bounds for several computation problems in multidimensional computational geometry.