The complexity of many faces in arrangements of lines of segments

ABSTRACT

We show that the total number of edges of m faces of an arrangement of n lines in the plane is &Ogr;(m2/3-&dgr; n2/3+2&dgr; + n), for any &dgr; > 0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of these m faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and, with high probability, its time complexity is within a log2n factor of the above bound. If instead of lines we have an arrangement of n line segments, then the maximum number of edges of m faces is Ogr;(m2/3-&dgr;n2/3+2&dgr; + n&agr;(n)logm), for any &dgr; > 0, where &agr;(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and, with high probability, takes time that is within a log2n factor of the combinatorial bound.

REFERENCES

• Ca: Canham, R. J. A theorem on arrangements of lines in the plane, israel j. Math. 7 (1969), 393-397.
• CD: B. Chazelle , D. P. Dobkin, Intersection of convex objects in two and three dimensions, Journal of the ACM (JACM), v.34 n.1, p.1-27, Jan. 1987 [doi>10.1145/7531.24036]
• Cl: 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]
• CEGSW: Clarkson, K., Edelsbrunner, H., Guibas, L. J., Sharir, M. and Welzl, E. Complexity bounds for arrangements. In preparation.
• CSY: Richard Cole , Micha Sharir , Chee K Yap, On k-hulls and related problems, SIAM Journal on Computing, v.16 n.1, p.61-77, Feb. 1987 [doi>10.1137/0216005]
• Ed: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EGSh: Edelsbrunner, H., Guibas, L. J. and Sharir, M. The complexity of many cells in arrangements of planes and related problems. In preparation.
• ES: Herbert Edelsbrunner , Micha Sharir, The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n - 2, Discrete & Computational Geometry, v.5 n.1, p.35-42, Jan. 1990 [doi>10.1007/BF02187778]
• EW: 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]
• EW2: H Edelsbrunner , E Welzl, Halfplanar range search in linear space and O(n0.695) query time, Information Processing Letters, v.23 n.6, p.289-293, Dec. 3, 1986
• Gr: Grfinbaum, B. Convex Polytopes. John Wiley & Sons, Lon. don, 1967.
• GOS: Guibas, L. J., Overmars, M.H. and Sharir, M. Intersections, connectivity, and related problems for arrangements of line segments. In preparation.
• GSS: L. J. Guibas , M. Sharir , S. Sifrony, On the general motion planning problem with two degrees of freedom, Proceedings of the fourth annual symposium on Computational geometry, p.289-298, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73423]
• HS: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• HW: Haussler, D. and Welzl, E. Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2 (1987), 127-151.
• OR: Joseph O'Rourke, The signature of a plane curve, SIAM Journal on Computing, v.15 n.1, p.34-51, Feb. 1986 [doi>10.1137/0215003]
• PSS: R. Pollack , M. Sharir , S. Sifrony, Separating two simple polygons by a sequence of translations, Discrete & Computational Geometry, v.3 n.2, p.123-136, Jan, 1988 [doi>10.1007/BF02187902]
• PS: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• SML: Schmitt, A., Muller, H. and Leister, W. Ray tracing algorithms - theory and practice. In Theoretical Foundations of Computer Graphics and CAD (R.A. Earnshaw, Ed.), NATO ASI Series, Vol. F40, Springer Verlag, Berlin, 1988, 997-1030.
• ST: Szemerbti, E. and Trotter, W. T. Extremal problems in discrete geometry. Combinatorica 3 (1983), 381-392.
• WS: Ady Wiernik , Micha Sharir, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Discrete & Computational Geometry, v.3 n.1, p.15-47, Jan., 1988 [doi>10.1007/BF02187894]

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:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms; Recurrences and difference equations
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms, Performance, Theory, Verification