Intersecting is easier than sorting

ABSTRACT

This paper settles a long-standing open question of computational geometry: Is it possible to compute all k intersections between n arbitrary line segments in time linear in k? We answer this question affirmatively by presenting the first algorithm with a running time of the form O(k + f(n)), where f is a subquadratic function of n. The function f we achieve is actually quasi-linear in n, which makes our algorithm the most efficient to date for each value of k. To obtain this result we must turn away from traditional, sweep-line-based schemes. Instead, we introduce a new hierarchical strategy for dealing with segments without ever reducing the dimensionality of the problem. This framework is used to solve other related problems. In particular, we are able to present the first subquadratic algorithm for counting intersections (as opposed to reporting each of them explicitly), and we give the first optimal algorithm for computing the intersections of a line arrangement with a query segment. Using duality arguments we also present an improved algorithm for a point enclosure problem.

REFERENCES

• 1: Bentley, J.L., Ottmann, T. Algorithms for reporting and counting geometric intersections, IEEE Trans. Comp. C-28, 9, pp.643-647, Sept. 1979.
• 2: Bentley, J.L., Wood, D. An optimal worst-case algorithm for reporting intersections of rectangles, IEEE Trans. Comp. C-29, pp. 571-577, 1980.
• 3: Brown, K.Q. Comments on "Algorithms for Reporting and Counting Geometric Intersections", IEEE Trans. Comp., C-30, pp. 147-148, 1981.
• 4: Chaselle, B., Guibas, L., Lee, D.T. The power of duality, Proc. 24th FOCS Symp., 1983.
• 5: Edelsbrunner, H., Guibas, L., Stolfi, J. Optimal point location in a monotone subdivision, to appear.
• 6: Edelsbrunner, H., Welzl, E. Halfplanar range search in linear space and O(n0.695) query time, Tech. Univ. Graz, IIG Rep. 111, 1983.
• 7: Guibas, L., Ramshaw, L., Stolfi, J. A kinetic framework for computational geometry, Proc. 24th Annual FOCS, pp. 100-111, 1983.
• 8: Leo J. Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.221-234, December 1983 [doi>10.1145/800061.808751]
• 9: Kirkpatrick, D.G. Optimal search in planar subdivisions, SIAM J. on Comp., Vol. 12, No. 1, pp. 28-35, Feb. 1983.
• 10: Mairson, H.G., Stolfi, J. Reporting and counting line segment intersections, Unpublished Manuscript.
• 11: Muller, D.E., Preparata, F.P. Finding the intersection of two convez polyhedra, Theoret. Comput. Sci., 7(1978), pp. 217-236.
• 12: J. Nievergelt , F. P. Preparata, Plane-sweep algorithms for intersecting geometric figures, Communications of the ACM, v.25 n.10, p.739-747, Oct 1982 [doi>10.1145/358656.358681]
• 13: Shamos, M.I., Hoey, D.J. Geometric intersection problems, Proc. 17th Annual IEEE Symp. on Foundations of Computer Science, pp.208-215, 1976.

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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems

General Terms:
Algorithms, Theory