A 3-space partition and its applications

ABSTRACT

Let S be a set of n points in three-dimensional space. It is shown that one can always find three planes that divide S into eight open regions, of which no seven together contain more than &agr; n points where &agr; is a constant < 1. This result gives rise to a data structure, what we call an octant-tree, for representing any point set in 3-space. Efficient solutions to various data retrieval problems are readily available with this structure. For example, using octant-trees, one can answer in sublinear time T (n) @@@@O(n0.98) 1) half-space queries: find all points of S that lie to one side of a plane P; 2) polytope queries: find all points that lie inside (outside) a polytope; and 3) circular queries in E2: given a planar set S, find all points that lie within (without) a circle of radius r and center c for any r and c. An octant-tree for n points occupies O(n) space and can be constructed with O(n4) preprocessing time.

REFERENCES

• 1: J. L. Bentley and H. A. Mauer, "A note on Euclidean near neighbor searching in the plane," Information Processing Letters 8 (1979), 133-136.
• 2: J. L. Bentley and D. F. Stanat, "Analysis of range searches in quad trees," Information Processing Letters 3 (1975), 170-173.
• 3: B. Chazelle, "An improved algorithm for the fixed-radius neighbort problem," to appear in Information Processing Letters.
• 4: D. L. Dobkin and R. J. Lipton, "Multidimensional searching problems," SIAM J, on Computing 5 (1976), 181-186.
• 5: R. A. Finkel and J. L. Bentley, "Quad trees: a data structure for retrieval on composite keys," Acta Informatica 4 (1974), 1-9.
• 6: M. L. Fredman, "Lower bounds on the complexity of some optimal data structures," SIAM J. on Computing 10 (1981), 1-10.
• 7: M. L. Fredman, "The inherent complexity of dynamic data structures which accomodate range queries," Proc. 21st Annual IEEE Symposium on Foundations of Computer Science (1980), 191-200.
• 8: M. L. Fredman and D. J. Volper, "Query time versus redundancy trade-offs for range queries," Journal of Computer and System Sciences 23 (1981), 355-365.
• 9: Leo J. Guibas and Jorge Stolfi, "Primitives for the manipulation of general subdivisions and the computation of Voronoi Diagrams," this proceeding.
• 10: G. S. Leuker, "A data structure for orthogonal range queries," Proc. 19th Annual IEEE Symposium on Foundation of Computer Science (1978), 28-34.
• 11: Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
• 12: D. E. Willard, "Polygon retrieval," SIAM J. on Computing 11 (1982), 149-165.
• 13: Andrew C. Yao, Space-time tradeoff for answering range queries (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.128-136, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802185]
• 14: I. M. Yaglom and V. G. Boltyanskii, "Convex Figures," Holt, Rinehart and Winston, Translation (1961).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning

Additional 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

General Terms:
Theory