Results in Computational Geometry: Geometric Embeddings and Query- Retrieval Problems
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1990
- Accession Number
- ADA230380
Entities
People
- Mark D. Hansen
Organizations
- Massachusetts Institute of Technology