Solving Geometric Problems in Space-Conscious Models
Yu Chen · 2009
I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii When dealing with massive data sets, standard algorithms may easily “run out of memory”. In this thesis, we design efficient algorithms in space-conscious mod-els. 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 program-ming. 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.