Tail estimates for the space complexity of randomized incremental algorithms

ABSTRACT

We give tail estimates for the space complexity of randomized incremental algorithms for line segment intersection in the plane. For n the number of segments, m is the number of intersections, and m ≥ n ln n ln(3) n, there is a constant c such that the probability that the total space cost exceeds c times the expected space cost is e-&OHgr;(m/(n ln n)).

REFERENCES

• 1: J.D. Boissonnat, O. Devillers, R. Schott, M. Teillaud and M. Yvinec, Applications of random sampling to on-line algorithms in computational geometry, Tech. rept., INRIA, 1990.
• 2: Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir , Jack Snoeyink, Computing a face in an arrangement of line segments, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.441-448, January 28-30, 1991, San Francisco, California, United States
• 3: 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]
• 4: 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]
• 5: Leonidas J. Guibas , Donald E. Knuth , Micha Sharir, Randomized incremental construction of Delaunay and Voronoi diagrams, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.414-431, July 1990, Warwick University, England
• 6: L. J. Guibas, On the general motion-planning problem with two degrees of freedom, Discrete & Computational Geometry, v.4 n.5, p.491-521, 1989 [doi>10.1007/BF02187744]
• 7: 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]
• 8: W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Am. Stat. Ass, 58 (1963), 13- 30.
• 9: K. Mehlhorn, A tail estimate for the space complexity of some randomized incremental constructions, unpublished manuscript.
• 10: 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]
• 11: Otfried Schwarzkopf, Dynamic maintenance of geometric structures made easy, Proceedings of the 32nd annual symposium on Foundations of computer science, p.197-206, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185369]
• 12: Raimund Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Computational Geometry: Theory and Applications, v.1 n.1, p.51-64, July 1991 [doi>10.1016/S0925-7721(99)00042-5]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional 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

  G. Mathematics of Computing

General Terms:
Theory, Verification