When dealing with massive data sets, standard algorithms mayeasily ``run out of memory;;;;. In this thesis, we design efficientalgorithms in space-conscious models. In particular, in-placealgorithms, multi-pass algorithms, read-only algorithms, andstream-sort algorithms are studied, and the focus is onfundamental geometric problems, such as 2D convex hulls, 3D convexhulls, Voronoi diagrams and nearest neighbor queries, Klee;;smeasure problem, and low-dimensional linear programming.In-place algorithms only use O(1) extra space besides the inputarray. We present a data structure for 2D nearest neighbor queriesand algorithms for Klee;;s measure problem in this model.Algorithms in the multi-pass model only make read-only sequentialaccess to the input, and use sublinear working space and small(usually a constant) number of passes on the input. We presentalgorithms and lower bounds for many problems, includinglow-dimensional linear programming and convex hulls, in thismodel.Algorithms in the read-only model only make read-only randomaccess to the input array, and use sublinear working space. Wepresent algorithms for Klee;;s measure problem and 2D convex hullsin this model.Algorithms in the stream-sort model use sorting as a primitiveoperation. Each pass can either sort the data or make sequentialaccess to the data. As in the multi-pass model, these algorithmscan only use sublinear working space and a small (usually aconstant) number of passes on the data. We present algorithms forconstructing convex hulls and polygon triangulation in this model.
【 预 览 】
附件列表
Files
Size
Format
View
Solving Geometric Problems in Space-Conscious Models