On showing lower bounds for external-memory computational geometry problems
Lars Arge, Peter Miltersen · DIMACS series in discrete mathematics and theoretical computer science · 1999
. In this paper we consider lower bounds for external-memory computational geometry problems. We find that it is not quite clear which model of computation to use when considering such problems. As an attempt of providing a model, we define the external memory Turing machine model, and we derive lower bounds for a number of problems, including the element distinctness problem, in this model. For these lower bounds we make the standard assumption that records are indivisible. Waiving the indivisibility assumption we show how to beat the lower bound for element distinctness. As an alternative model, we briefly discuss an external-memory version of the algebraic computation tree. 1. Introduction The Input/Output (or just I/O) communication between fast internal memory and slower external storage is the bottleneck in many large-scale computations. The significance of this bottleneck is increasing as internal computation gets faster, and as parallel computation gains popularity. Currently,...