Applications of random sampling in computational geometry, II

ABSTRACT

Random sampling is used for several new geometric algorithms. The algorithms are “Las Vegas,” and their expected bounds are with respect to the random behavior of the algorithms. One algorithm reports all the intersecting pairs of a set of line segments in the plane, and requires &Ogr;(A + n log n) expected time, where A is the size of the answer, the number of intersecting pairs reported. The algorithm requires &Ogr;(n) space in the worst case. Another algorithm computes the convex hull of a point set in E3 in &Ogr;(n log A) expected time, where n is the number of points and A is the number of points on the surface of the hull. A simple Las Vegas algorithm triangulates simple polygons in &Ogr;(n log log n) expected time. Algorithms for half-space range reporting are also given. In addition, this paper gives asymptotically tight bounds for a combinatorial quantity of interest in discrete and computational geometry, related to halfspace partitions of point sets.

REFERENCES

• AG86: N Alon , E Györi, The number of small semispaces of a finite set of points in the plane, Journal of Combinatorial Theory Series A, v.41 n.1, p.154-157, Jan. 1986 [doi>10.1016/0097-3165(86)90122-6]
• AHW87: N. Alon , D. Haussler , E. Welzl, Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension, Proceedings of the third annual symposium on Computational geometry, p.331-340, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41994]
• CEG+88: K. L. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl. The complexity of many faces in an arrangement of lines in the plane. To appear, 1988.
• Cla85: K Clarkson, A probabilistic algorithm for the post office problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.175-184, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22165]
• Cla87: 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]
• CP86: B. Chazelle , F. P. Preparata, Halfspace range search: an algorithmic application of k-sets, Discrete & Computational Geometry, v.1 n.1, p.83-93, 1986 [doi>10.1007/BF02187685]
• CS88: 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]
• CSY84: Richard Cole , Micha Sharir , Chee K. Yap, On k-hulls and related problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.154-166, December 1984 [doi>10.1145/800057.808677]
• CTVW88: 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]
• Ede: H. Edelsbrunner. Personal communication.
• Ede87: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EM88: 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]
• ES74: P. ErdSs and J. Spencer. Probabilistic Methods in Combinatorics. Academic Press, New York, 1974.
• GP84: J.E. Goodman and R. E. Pollack. On the number of k-subsets of a set of n points in the plane. J. Combin. Theory Ser. A, 36:101-104, 1984.
• HW87: D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete Comp. Geom., 2:127-151, 1987.
• KS86: David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
• TVW88: Robert E. Tarjan , Christopher van Wyk, An O (n log log n)-time algorithm for triangulating a simple polygon, SIAM Journal on Computing, v.17 n.1, p.143-178, Feb. 1988 [doi>10.1137/0217010]
• Wel86: 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]
• Yap88: C. K. Yap, A geometric consistency theorem for a symbolic perturbation scheme, Proceedings of the fourth annual symposium on Computational geometry, p.134-142, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73407]

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

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning

General Terms:
Algorithms, Performance, Theory