Accession Number:

ADA210830

Title:

Three Methods for Range Queries in Computational Geometry

Descriptive Note:

Technical rept.

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

• Kipnis, Shlomo

Report Date:

1989-03-01

Pagination or Media Count:

23.0

Abstract:

This paper surveys a variety of recent results addressing the problem of range queries in computational geometry. The major contribution of this paper is in identifying three general methods for range queries in computational geometry and in classifying many of the recent results into one or more of these approaches. The three methods discussed in this paper are random sampling, search-tree tables, and space-partition trees. This survey assumes some familiarity with basic computational geometry concepts and techniques.

Descriptors:

• *GEOMETRY
• *COMPUTATIONS
• SAMPLING
• INTERROGATION
• METHODOLOGY
• SURVEYS

Subject Categories:

• Statistics and Probability
• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE