Results in Computational Geometry: Geometric Embeddings and Query- Retrieval Problems
Mark D. Hansen · 1990
Abstract : Many fundamental questions in computational geometry arise from the consideration of distributions of points in euclidean space. This thesis explores two important ares of computational geometry in this setting: geometric embeddings and query-retrieval problems. Each area is addressed in a separate part of the thesis. Part I examines the geometric embedding problem for many of the graphs which are important in the study of parallel computation. Part II of this thesis examines query-retrieval problems concerning distributions of points in euclidean space. In this part, we describe a new technique for solving a variety of query-retrieval problems in optimal time with optimal or near optimal space. Our compaction technique incorporates planar separators, filtering search, and the probabilistic method for discrepancy problems.