Accession Number:

ADA230380

Title:

Results in Computational Geometry: Geometric Embeddings and Query- Retrieval Problems

Descriptive Note:

Technical rept.

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

• Hansen, Mark D.

Report Date:

1990-11-01

Pagination or Media Count:

95.0

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.

Descriptors:

• *OPTIMIZATION
• GRAPHS
• PROBABILITY
• PARALLEL PROCESSING
• TIME
• SEPARATORS
• SEARCHING
• GEOMETRY
• EMBEDDING
• FILTERS
• COMPACTING
• COMPUTATIONS
• PLANAR STRUCTURES

Subject Categories:

• Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE