Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental

ABSTRACT

We give a simple algorithmic technique for building geometric structures. The technique is randomized and incremental. As an application, we give an algorithm of this kind for computing the intersection of a set of halfspaces in three dimensions. (This intersection problem is linear-time equivalent to the computation of the convex hull of a point set.) The algorithm requires &Ogr;(n log n) expected time, where the expectation is over the random behavior of the algorithm. A similar algorithm can be used to determine the intersection of a set of unit balls in E3, the problem of spherical intersection. This problem arises in the computation of the diameter of a point set in E3. For a set S of n points, the diameter of S is the greatest distance between two points in S. We give a randomized reduction from the problem of determining the diameter to the problem of computing spherical intersections, resulting in a Las Vegas algorithm for the diameter requiring &Ogr;(n log n) expected time. The best algorithms previously known for this problem have worst-case time bounds no better than &Ogr;(n √n log n) [Agg].

REFERENCES

• Agg: A. Aggarwal. personal communication.
• Che86: L.P. Chew. Building Voronoi diagrams for convex polygons in linear expected time. unpublished manuscript, 1986.
• Cla88: 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]
• Ede87: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EKS83: H. Edelsbrunner, D. G. Kirkpatrick, and R. Seidel. On the shape of a set of points in the plane. IEEE Trans. Inform. Theory, IT-29:551-559, 1983.
• EOS86: 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]
• Hep56: A. Heppes. Beweis einer Vermutung von A. V~zsonyi. Acta Math. Acad. Sci. Hungar., 7:463-466, 1956.
• PH77: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• PS85: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985

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:
  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.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning
      I.4.7 Feature Measurement
          Subjects: Projections
      I.4.8 Scene Analysis
          Subjects: Stereo

General Terms:
Algorithms, Performance, Theory