Computing many faces in arrangements of lines and segments

ABSTRACT

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized O(nlogn) expected time algorithm for computing n cells in an arrangement of n lines.

REFERENCES

• 1: Pankaj K. Agarwal, Partitioning arrangements of lines, part II: applications, Discrete & Computational Geometry, v.5 n.6, p.533-573, Sep. 1990 [doi>10.1007/BF02187809]
• 2: B. Aronov, H. Edelsbrunner, L. Guibas and M. Sharir, Improved bounds on the complexity of many faces in arrangements of segments, Combinatorica, 12 (1992), 261-274.
• 3: Mark de Berg , Katrin Dobrindt , Otfried Schwarzkopf, On lazy randomized incremental construction, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.105-114, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195113]
• 4: R. Canham, A theorem on arrangements of lines in the plane, Israel J. Math. 7 (1969), 393-397.
• 5: Bernard Chazelle , Herbert Edelsbrunner , Michelangelo Grigni , Leonidas Guibas , John Hershberger , Micha Sharir , Jack Snoeyink, Ray shooting in polygons using Geodesic triangulations, Proceedings of the 18th international colloquium on Automata, languages and programming, p.661-673, June 1991, Madrid, Spain
• 6: Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir , Jack Snoeyink, Computing a face in an arrangement of line segments and related problems, SIAM Journal on Computing, v.22 n.6, p.1286-1302, Dec. 1993 [doi>10.1137/0222077]
• 7: B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry, Combinatorica 10 (1990), 229-249.
• 8: K. Clarkson, Computing a single face in an arrangement of segments, 1990, manuscript.
• 9: Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
• 10: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 11: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 12: Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, The complexity and construction of many faces in arrangements of lines and of segments, Discrete & Computational Geometry, v.5 n.2, p.161-196, 1990 [doi>10.1007/BF02187784]
• 13: H Edelsbrunner , E Welzl, On the maximal number of edges of many faces in an arrangement, Journal of Combinatorial Theory Series A, v.41 n.2, p.159-166, March 1986 [doi>10.1016/0097-3165(86)90078-6]
• 14: L. Guibas and M. Sharir, Combinatorial and algorithms of arrangements, in New Trends in Discrete and Computational Geometry (J. Pach, ed.), Springer-Verlag, New York-Berlin-Heidelberg, 1993, 9-36.
• 15: John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.54-63, January 25-27, 1993, Austin, Texas, United States
• 16: D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Discrete Comput. Geom. 2 (1987), 127-151.
• 17: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 18: K. Mulmuley, A fast planar partition algorithm, I, Journal of Symbolic Computation, v.10 n.3-4, p.253-280, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80064-8]
• 19: Kentan Mulmuley, A fast planar partition algorithm, II, Journal of the ACM (JACM), v.38 n.1, p.74-103, Jan. 1991 [doi>10.1145/102782.102785]
• 20: E. Szemer~di and W. Trotter Jr., Extremal problems in discrete geometry, Combinatorica 3 (1983), 381-392.

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.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory