A general approach to d-dimensional geometric queries

ABSTRACT

It is shown that any bounded region in Ed can be divided into 2d subregions of equal volume in such a way that no hyperplane in Ed can intersect all 2d of the subregions. This theorem provides the basis of a data structure scheme for organizing n points in d dimensions. Under this scheme, a broad class of geometric queries in d dimensions, including many common problems in range search and optimization, can be solved in linear storage space and sublinear time.

REFERENCES

• BM: J. L. Bentley and J. A. Mauer, 'A note on Euclidean near neighbor searching,~ Information Processing Letters 8 (1979), 133-136.
• Ch: B Chazelle, Fast searching in a real algebraic manifold with applications to geometric complexity, Proc. of the international joint conference on theory and practice of software development (TAPSOFT) Berlin, March 25-29, 1985 on Mathematical foundations of software development, Vol. 1: Colloquium on trees in algebra and programming (CAAP'85), p.145-156, April 1985, Berlin, Germany
• CSY: R. Chazelle, L. Giibas, and D. T. Lee, "The power of geo metric duality." Proceedings of 24th Anmlal IEEE Symposium on Fmmdations of Computer Science, 1983.
• Co: R. Cole, "Partitioning point sets in 4-dimensions," Technical Report no. 142, Department of Computer Science, New York University, November 1984.
• CSY: Richard Cole , Micha Sharir , Chee K. Yap, On k-hulls and related problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.154-166, December 1984 [doi>10.1145/800057.808677]
• DE: D. P. Dobkin and Edelsbnmner, "Space searching for interse(:ting obj~ts,' Proceedings of 25th Ammal {EEE Symposium on Foundations of Computer Science, 1984.
• DL: D.P. Dobkin and R. J. Lipton,, Multidimensional searching problems," SIAM J. on Computing 5 (1076), 181-186.
• F: M. Fredman, "Lower bounds on the, complexity of some optimal data structlires,' SIAM J. on Computing 10 (1981), 1-10.
• SS: J.T. Schwartz and M. Sharir, ,On the piano movers' problem: II. General techbniques for computing topological properties of real algebraic manifolds," Advances in Applied Mathematics 4 (1983), 298-351.
• T: A. Tarski, 'A decision method for elementary algebra and geometry," University of California Press, (1951). (2nd ed. rev. )
• W: D. E. Willard, 'Polygon retrieval," SIAM J. on Computing 11 (198Z), 149-165.
• Y1: A. C. Yao, "On Constructing mininmm spanning trees in k-dimensional spaces and related problems," SIAM J. on Computing Ii (1982), 721-735.
• Y2: F. Frances Yao, A 3-space partition and its applications, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.258-263, December 1983 [doi>10.1145/800061.808755]

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Theory, Verification