Back to search

University of Waterloo

Solving Geometric Problems in Space-Conscious Models

Abstract

dc:description.abstract

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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chen, Yu

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/4257

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chen, Yu. Solving Geometric Problems in Space-Conscious Models. University of Waterloo, 2009. http://hdl.handle.net/10012/4257