A C Yao
F F Yao
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.
- BM.J. L. Bentley and J. A. Mauer, 'A note on Euclidean near neighbor searching,~ Information Processing Letters 8 (1979), 133-136.Google Scholar
- Ch.B. Chazelle, "Fast searching in a real algebraic mainfold with applications to g(,onietric comI)lexity," Pro(:e(,(lings of Collquium o,l Trees in Algebra and Progralnming, CAAP'85, Berlin, West Germany, Lecture Notes in Computer Science Springer Verlag, Mar(:h 1985. Google ScholarDigital Library
- 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.Google Scholar
- Co.R. Cole, "Partitioning point sets in 4-dimensions," Technical Report no. 142, Department of Computer Science, New York University, November 1984.Google Scholar
- CSY.R. Cole, M. Sharir, and C. K. Yap, 'On k-hulls and related problems," Proceedings of 16th Annual ACM Symposium on Theory of Computing, 1984. Google ScholarDigital Library
- 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.Google Scholar
- DL.D.P. Dobkin and R. J. Lipton,, Multidimensional searching problems," SIAM J. on Computing 5 (1076), 181-186.Google Scholar
- F.M. Fredman, "Lower bounds on the, complexity of some optimal data structlires,' SIAM J. on Computing 10 (1981), 1-10.Google Scholar
- 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.Google ScholarDigital Library
- T.A. Tarski, 'A decision method for elementary algebra and geometry," University of California Press, (1951). (2nd ed. rev. )Google Scholar
- W.D. E. Willard, 'Polygon retrieval," SIAM J. on Computing 11 (198Z), 149-165.Google Scholar
- Y1.A. C. Yao, "On Constructing mininmm spanning trees in k-dimensional spaces and related problems," SIAM J. on Computing Ii (1982), 721-735.Google ScholarCross Ref
- Y2.F. F. Yao, 'A 3-space partition and its applicalio~ls." Prc)- ceedings of 15th Annual ACM Symposium on Theory of Computing, April 1983, 258-263. Google ScholarDigital Library
Index Terms
- A general approach to d-dimensional geometric queries
Recommendations
Computing general geometric structures on surfaces using Ricci flow
Systematically generalizing planar geometric algorithms to manifold domains is of fundamental importance in computer aided design field. This paper proposes a novel theoretic framework, geometric structure, to conquer this problem. In order to discover ...
Multi-dimensional Queries in DHT-Based Peer-to-Peer Systems
SKG '09: Proceedings of the 2009 Fifth International Conference on Semantics, Knowledge and GridSupporting relational query processing in P2P data management systems needs multi-dimensional exact match queries processing and multi-dimensional range queries processing. The paper proposes a method for using a DHT-based P2P system to support multi-...
Comments