A deterministic algorithm for partitioning arrangements of lines and its application

ABSTRACT

In this paper we consider the following problem: Given a set ℒ of n lines in the plane, partition the plane into &Ogr;(r2) triangles so that no triangle intersects more than &Ogr;(n/r) lines of ℒ. We present a deterministic algorithm for this problem with &Ogr;(nr log n log&ohgr; r) running time, where &ohgr; is a constant < 3.3. Our algorithm is faster than Matousk's recent algorithm [Ma] for large values of r. In the second part of the paper, we apply this algorithm to several problems involving lines or segments in the plane, and obtain deterministic algorithms which are faster than any previously known algorithms. For example we give an &Ogr;(n2/3m2/3 log n log&ohgr;/3 m/√n + (m + n) log n) algorithm to compute all incidences between m points and n lines. Other problems include computing many faces in an arrangement of lines or segments, counting segment intersections, red-blue intersection detection, simplex range queries and computing stabbing trees with low stabbing number.

REFERENCES

• Aga: P. K. Agarwal, Partitioning arrangements of lines: I. An efficient deterministic algorithm, manuscript, 1989.
• Agb: P. K. Agarwal, Partitioning arrangements of lines: II. Applications, manuscript, 1989.
• Age: P. K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, Proceedings of the fifth annual symposium on Computational geometry, p.315-325, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73868]
• AS: P. Agarwal , M. Sharir, Red-Blue intersection detection algorithms, with applications to motion planning and collision detection, Proceedings of the fourth annual symposium on Computational geometry, p.70-80, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73401]
• AKS: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• AEGS: B. Aronov, H. Edelsbrunner , L. Guibas , M. Sharir, Improved bounds on the complexity of many faces in arrangements of segments, manuscript, 1988.
• Ch: 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]
• Cha: B. Chazelle, Polytope range searching and integral geometry, Proceedings 28 th Annual IEEE Symp osium on Foundations of Compuler Science, 1987, pp. l-10.
• Chb: B. Chazelle, Tight bounds on the stabbing number of trees in Euclidean plane, Technical Report CS-T&155-58, Dept. Computer Science, Princeton University, May 1988.
• Chc: B. Chazelle, personal communication, 1988.
• CE: B. Chazelle and H. Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Proceedings 2Qth Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 590-600.
• CF: B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry, Proceedings 2gfh Annual IEEE Symposium on Foundations of Compuler Science, 1988, pp. 539-549.
• CW: B. Chazelle and E. Welzl, Range searching and VC- dimension: A characterization of efficiency, manuscript, 1988.
• Co: Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
• Cla: K. Clarkson, New applications of random sampling in computational geometry, Discrete and Computalional Geome- Iry, 2 (1987), pp. 195-222.
• Clb: 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]
• CEG*: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir and E. Welzl, Combinatorial complexity for arrangements of curves and surfaces, Proceedings 2Sth Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 568 579.
• CS: K. L. Clarkson , P. W. Shor, Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental, Proceedings of the fourth annual symposium on Computational geometry, p.12-17, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73395]
• CTV: K. L. Clarkson , R. E. Tarjan , C. J. Van Wyk, A fast Las Vegas algorithm for triangulating a simple polygon, Proceedings of the fourth annual symposium on Computational geometry, p.18-22, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73396]
• Co: Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
• CSSS: Richard Cole , Jeffrey S. Salowe , William L. Steiger , Endre Szemerédi, Optimal Slope Selection, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.133-146, July 11-15, 1988
• Ed: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EGH*: H. Edelsbrunner , L. J. Guibas , J. Hershberger , R. Seidel , M. Sharir, Implicitly representing arrangements of lines or segments, Proceedings of the fourth annual symposium on Computational geometry, p.56-69, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73400]
• EGS: H. Edelsbrunner , L. J. Guibas , M. Sharir, The complexity of many faces in arrangements of lines of segments, Proceedings of the fourth annual symposium on Computational geometry, p.44-55, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73399]
• EGSt: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• EOS: H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
• EW: H. Edelsbrunner and E. Welzl, Constructing belts in twodimensional arrangements with applications, SIAM J. Computing, 15 (1986), 271-284.
• GOS: L. Guibas, M. Overmars and M. Sharir, Intersecting line segments, ray shootings and other applications of geometric partitioning techniques, Technical Report RUU-CS-8s 26, Dept. Computer Science, University of Utrecht, August 1988.
• HW: D. Haussler and E. Welzl, e-nets and simplex range queries, Discrete and Computational Geometry, 2 (1987), pp. 127- 151.
• MS: H. Mairson and J. Stolfi, Reporting and counting intersections between two sets of line segments, NATO ASI Series, F40, Theoretical Foundations of Computer Graphihcs and CAD, ed. R. Earnshaw, Springer Verlag, Berlin, 1988, pp. 307-325.
• Ma: J. MatouBek, Construction of c-nets, Proceedinga St" Annual Symposium on Computational Geometry, 1989.
• Mat: J. Matotiek, Constructing spanning trees with low crossing numbers, manuscript, 1989.
• Me: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• Mu: K. Muhnuley, A fast planar partition algorithm, Proceedings 2Qth Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 580-589.
• PS: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• STa: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• ST: E. SzemerCdi and W. netter, Extremal problems in discrete geometry, Combinalorica, 3 (1983), pp. 381-392.
• wea: Emo Welzl, More on k-sets of finite sets in the plane, Discrete & Computational Geometry, v.1 n.1, p.95-100, 1986 [doi>10.1007/BF02187686]
• Web: E. Welzl, Partition trees for triangle counting and other range searching problems, Proceedings of the fourth annual symposium on Computational geometry, p.23-33, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73397]
• Wo: G. Woeginger, Epsilon-nets for half planes, Technical Report B-88-02, Dept. of Mathematics, Free University Berlin, March 1988.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Theory