To appear in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005.

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Ω( on the complexity of both sorting and element uniqueness in this model of computation. We also prove an Ω(min{nlog_{m}n)nlog_{m}n,N}) lower bound for both problems in a less restrictive model, which requires only that the worst-case internal-memory computation time is finite. Standard reductions immediately generalize these lower bounds to a large number of fundamental computational geometry problems.Note:The main result in the actual SODA paper is slightly stronger than in the earlier submitted version.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 20 Oct 2004