| Lower Bounds for External Algebraic Decision Trees * (2008) | |||||||||||||
Abstract | |||||||||||||
| Abstract We propose a natural extension of algebraic decision trees to the external-memory setting, where the cost of disk operations overwhelms CPU time, and prove a tight lower bound of \Omega (n logm n) on the complexity of both sorting and element uniqueness in this model of computation. We also prove a \Omega (min{n logm n, N}) lower bound for both problems in a less restrictive model, which requires only that the worstcase internal-memory computation time is finite. Standard reductions immediately generalize these lower bounds to a large number of fundamental computational geometry problems. 1 Introduction Lower bounds for computational geometry problems arefrequently stated in the algebraic decision tree model defined by Steele and Yao [15]. Examples includeconvex hulls, Voronoi diagrams, Euclidean minimum spanning trees, closest and farthest pairs, line segmentintersections, and batched planar point location. Tight \Omega (N lg N) lower bounds in the algebraic decision treemodel have been known for these problems for two decades; these lower bounds were all proved by reduc-tions from sorting or element uniqueness [7, 14, 15]. On the other hand, geometric algorithms are usuallydesigned around a core of low-degree polynomial primitives, such as triangle orientation tests and in-circletests, which are treated as black boxes. Algebraic decision trees describe these algorithms perfectly. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||