| Multi-Pass Geometric Algorithms \Lambda (2006) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract We propose the study of exact geometric algorithms that require limited storage and make only a small number of passes over the input. Fundamental problems such as low-dimensional linear programming and convex hulls are considered. 1 Introduction The multi-pass model. Streaming algorithms that make a single pass over the input and work with a small amount of space have grown in popularity [31], because of the ability of such algorithms to handle massive data sets. Since only one pass over the input is required, data elements may arrive one at a time and the entire data set never needs to be physically stored. Study of geometric algorithms in the data-stream model has already begun to take place in several recent papers (e.g., [3, 10, 37]). In this paper, we examine a more powerful multi-pass model, where algorithms are allowed to make multiple passes over the input. The input remains unchanged after each pass, and depending on the problem, the answer may be sent to a write-only output stream. The goal is to minimize the amount of working space (measured in words, in this paper), while keeping the number of passes small. As usual, we would like to bound the total running time as well (which includes the cost of scanning and is at least the input size times the number of passes); for this purpose, we assume unit-cost random access for the working space (but not the input, of course). | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||