Solving Geometric Problems in Space-Conscious Models

Algorithms;Data Structures;Computational Geometry;Computer Science

Chen, Yu

University of Waterloo

关键词: Algorithms;    Data Structures;    Computational Geometry;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/4257/1/uw-ethesis.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

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.