Range searching with efficient hierarchical cuttings

ABSTRACT

We present an improved space/query time tradeoff for the general simplex range searching problem, matching known lower bounds up to small polylogarithmic factors. In particular, we construct a linear-space simplex range searching data structure with O(n1–1/d) query time, which is optimal for d=2 and probably also for d>2. Further we show that multilevel range searching data structures can be built with only a polylogarithmic overhead in space and query time per level (the previous solutions require at least a small fixed power of n). We show that Hopcroft's problem (detecting an incidence among n lines and n points) can be solved in time n4/32O(log n). In all these algorithms, we apply Chazelle's results on computing optimal cuttings.

REFERENCES

• Aga90: Pankaj K. Agarwal, Partitioning arrangements of lines, part I: an efficient deterministic algorithm, Discrete & Computational Geometry, v.5 n.5, p.449-483, 1990 [doi>10.1007/BF02187805]
• AS91: P.K. Agarwal and M. Sharir. Applications of a new space partitioning scheme. In Proc. 2. Workshop on Algorithms and Data Structures, 1991.
• CF90: B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10(3):229-249, 1990.
• Cha89: B. Chazelle. Lower bounds on the complexity of polytope range searching. J. Amer. Math. Soc, 2(4):637-666, 1989.
• Cha91: B. Chazelle. Cutting hyperplanes for divide-andconquer. Tech. report CS-TR-335-91, Princeton University, 1991. Preliminary version: Proc. 0~2. IEEE Symposium on Foundations of Computer Science, October 1991.
• CSW90: Bernard Chazelle , Micha Sharir , Emo Welzl, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Proceedings of the sixth annual symposium on Computational geometry, p.23-33, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98532]
• CW89: B. Chazelle , E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete & Computational Geometry, v.4 n.5, p.467-489, 1989 [doi>10.1007/BF02187743]
• DE87: David P. Dobkin , Herbert Edelsbrunner, Space searching for intersecting objects, Journal of Algorithms, v.8 n.5, p.348-361, Sept. 1987 [doi>10.1016/0196-6774(87)90015-0]
• Ede87: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EGH+89: H. Edelsbrunner , L. Guibas , J. Hershberger , R. Seidel , M. Sharir , J. Snoeyink , E. Welzl, Implicitly representing arrangements of lines or segments, Discrete & Computational Geometry, v.4 n.5, p.433-466, 1989 [doi>10.1007/BF02187742]
• Mat91a: Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
• Mat91b: Jiří Matoušek, Cutting hyperplane arrangements, Discrete & Computational Geometry, v.6 n.5, p.385-406, 1991 [doi>10.1007/BF02574697]
• Mat91c: Jiří Matoušek, Efficient partition trees, Proceedings of the seventh annual symposium on Computational geometry, p.1-9, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109649]
• Mat91d: J. Matou~ek. Spanning trees with low crossing number. Informatzque Th4orique et applications, 6(25):103-123, 1991.
• OSS90: M. H. Overmars , H. Schipper , M. Sharir, Storing line segments in partition trees, BIT, v.30 n.3, p.385-403, 1990 [doi>10.1007/BF01931656]
• PS85: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary 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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory