When dealing with massive data sets, standard algorithms may
easily ``run out of memory''. In this thesis, we design efficient
algorithms in space-conscious models. In particular, in-place
algorithms, multi-pass algorithms, read-only algorithms, and
stream-sort algorithms are studied, and the focus is on
fundamental geometric problems, such as 2D convex hulls, 3D convex
hulls, Voronoi diagrams and nearest neighbor queries, Klee's
measure problem, and low-dimensional linear programming.
In-place algorithms only use O(1) extra space besides the input
array. We present a data structure for 2D nearest neighbor queries
and algorithms for Klee's measure problem in this model.
Algorithms in the multi-pass model only make read-only sequential
access to the input, and use sublinear working space and small
(usually a constant) number of passes on the input. We present
algorithms and lower bounds for many problems, including
low-dimensional linear programming and convex hulls, in this
model.
Algorithms in the read-only model only make read-only random
access to the input array, and use sublinear working space. We
present algorithms for Klee's measure problem and 2D convex hulls
in this model.
Algorithms in the stream-sort model use sorting as a primitive
operation. Each pass can either sort the data or make sequential
access to the data. As in the multi-pass model, these algorithms
can only use sublinear working space and a small (usually a
constant) number of passes on the data. We present algorithms for
constructing convex hulls and polygon triangulation in this model.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/4257 |
| Date | January 2009 |
| Creators | Chen, Yu |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0038 seconds