An optimal algorithm for intersecting line segments in the plane

ABSTRACT

The main contribution of this work is an O(n log n + k)-time algorithm for computing all k intersections among n line segments in the plane. This time complexity is easily shown to be optimal. Within the same asymptotic cost, our algorithm can also construct the subdivision of the plane defined by the segments and compute which segment (if any) lies right above (or below) each intersection and each endpoint. The algorithm has been implemented and performs very well. The storage requirement is on the order of n + k in the worst case, but it is considerably lower in practice. To analyze the complexity of the algorithm, an amortization argument based on a new combinatorial theorem on line arrangements is used.

REFERENCES

• 1: BAUMGART, B. G. A polyhedron representation for computer vision. In Proceedings of the 1975 National Computer Conference. AFIPS Conference Proceedings, vol. 44. AFIPS Press, Reston, Va., 1975, pp. 589-596.
• 2: Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
• 3: BENTLEY, J. L., AND OTTMANN, T. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. C-28 (1979), 643-647.
• 4: BENTLEY, J. L., AND WOOD, D. An optimal worst-case algorithm for reporting intersections of rectangles. IEEE Trans. Comput. C-29 (1980), 571-577.
• 5: BRowN, K.Q. Comments on "Algorithms for reporting and counting geometric intersections." IEEE Trans. Comput. C-30 (1981), 147-148.
• 6: Bernard Chazelle, Reporting and counting segment intersections, Journal of Computer and System Sciences, v.32 n.2, p.156-182, April 1986 [doi>10.1016/0022-0000(86)90025-5]
• 7: Bernard Chazelle, Functional approach to data structures and its use in multidimensional searching, SIAM Journal on Computing, v.17 n.3, p.427-462, June 1988 [doi>10.1137/0217026]
• 8: K. L. Clarkson, Applications of random sampling in computational geometry, II, Proceedings of the fourth annual symposium on Computational geometry, p.1-11, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73394]
• 9: DOBKIN. D. P., AND LIPTON, R. Multidimensional searching problems. SIAM J. Comput. 5 (1976), 181-186.
• 10: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 11: H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
• 12: H. Edelsbrunner , E. P. Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, Proceedings of the fourth annual symposium on Computational geometry, p.118-133, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73406]
• 13: FREDMAN, M. On the information theoretic lower bound. Theoret. Comput. Sci. 1 (1976), 355-361.
• 14: GumAs, L. J.. AND SEDC, F.WTCK, R. A dichromatic framework for balanced tree~. In Proeoodings of the 19th Annual IEEE Symposium on Foundations of Computer Science, IEEE, New York, i978, pp. 8-21.
• 15: L Guibas , R Seidel, Computing convolutions by reciprocal search, Proceedings of the second annual symposium on Computational geometry, p.90-99, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10525]
• 16: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 17: Kurt Hoffmann , Kurt Mehlhorn , Pierre Rosenstiehl , Robert E Tarjan, Sorting Jordan sequences in linear time using level-linked search trees, Information and Control, v.68 n.1-3, p.170-184, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80033-X]
• 18: MAIRSON, H. G., AND STOLFI, J. Reporting and counting intersections between two sets of hnc segments. In Proceedings of the NA TO Advanced Study, Institute on Theoretical Foundations of the Computational Graphics and CAD (I1 Clocco, Castelvecchio Pascoll, Italy). Sprmger-Verlag, Ncw York, 1987.
• 19: MULMULEY, K. A fast planar partition algorithm, I. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1988, pp. 580-589.
• 20: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 21: 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]
• 22: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 23: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 24: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

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

General Terms:
Algorithms, Theory