Geometric partitioning made easier, even in parallel

ABSTRACT

We present a simple approach for constructing geometric partitions in a way that is easy to apply to new problems. We avoid the use of VC-dimension arguments, and, instead, base our arguments on a notion we call the scaffold dimension, which subsumes the VC-dimension and is simpler to apply. We show how to easily construct (1/r)-nets and (1/r)-approximations for range spaces with bounded scaffold dimension, which immediately implies simple algorithms for constructing (1/r)-cuttings (by straight-forward recursive subdivision methods). More significant than simply being a conceptual simplification of previous approaches, however, is that our methods lead to asymptotically faster and more-efficient EREW PRAM parallel algorithms for a number of computational geometry problems, including the development of the first optimal-work NC algorithm for the well-known 3-dimensional convex hull problem, which solves an open problem of Amato and Preparata. Interestingly, our approach also yields a faster sequential algorithm for the distance selection problem, by the parametric searching paradigm, which solves an open problem posed by Agarwal, Aronov, Sharir, and Suri, and reiterated by Dickerson and Drysdale.

REFERENCES

• 1: K P Agarwal, Geometric Partitioning and Its Applications, Duke University, Durham, NC, 1991
• 2: Pankaj K. Agarwal , Boris Aronov , Micha Sharir , Subhash Suri, Selecting distances in the plane, Proceedings of the sixth annual symposium on Computational geometry, p.321-331, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98597]
• 3: Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States
• 4: N. Alon, J.H. Spencer, and P. ErdSs, The Probabilislic Method, Wiley-Interscience (New York: 1992).
• 5: N.M. Amato and F.P. Preparata, "The Parallel 3D Convex Hull Problem Revisited~" Int. J. of Compulational Geometry ~ Appl., 2(2), 1992, 163-173.
• 6: D. Angluin and L.G. Valiant, "Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings," J.C.$.S., 18, 1979, 155-193.
• 7: Bonnie Berger , John Rompel , Peter W. Shor, Efficient NC algorithms for set cover with applications to learning and geometry, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.454-477, December 1994, Research Triangle Park, North Carolina, United States
• 8: Bernard Chazelle, An optimal convex hull algorithm and new results on cuttings (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.29-38, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185345]
• 9: B. Chazelle and J. Friedman, "A deterministic view of random sampling and its use in geometry,'' Combinatorica, 10(3), 1990, 229-249.
• 10: Bernard Chazelle , Jiří Matoušek, Derandomizing an output-sensitive convex hull algorithm in three dimensions, Computational Geometry: Theory and Applications, v.5 n.1, p.27-32, March 1995 [doi>10.1016/0925-7721(94)00018-Q]
• 11: Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
• 12: Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir, Diameter, width, closest line pair, and parametric searching, Proceedings of the eighth annual symposium on Computational geometry, p.120-129, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142702]
• 13: H. Chernoff, "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations," Annals of Math. Star., 23, 1952, 493-507.
• 14: Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
• 15: 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]
• 16: Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
• 17: Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
• 18: R. Cole and M.T. Goodrich, "Optimal Parallel Algorithms for Point-Set and Polygon Problems,'' Algorithmica, 7, 1992, 3-23.
• 19: Richard Cole , Jeffrey S. Salowe , W. L. Steiger , Endre Szemerédi, An optimal-time algorithm for slope selection, SIAM Journal on Computing, v.18 n.4, p.792-810, Aug. 1989 [doi>10.1137/0218055]
• 20: 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]
• 21: Richard Cole , Ofer Zajicek, An optimal parallel algorithm for building a data structure for planar point location, Journal of Parallel and Distributed Computing, v.8 n.3, p.280-285, Mar. 1990 [doi>10.1016/0743-7315(90)90103-V]
• 22: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 23: N. Dadoun , D. G. Kirkpatrick, Parallel construction of subdivision hierarchies, Journal of Computer and System Sciences, v.39 n.2, p.153-165, Oct. 1989 [doi>10.1016/0022-0000(89)90042-1]
• 24: Matthew T. Dickerson , R. L. Scot Drysdale, Enumerating k distances for n points in the plane, Proceedings of the seventh annual symposium on Computational geometry, p.234-238, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109674]
• 25: P.W. Dymon and S.A. Cook, "Hardware Complexity and Parallel Comp.," Proc. 21st IEEE Syrup. on Found. of Uomp. Sci., 1980, 360-372.
• 26: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 27: M.T. Goodrich, "Constructing Arrangements Optimally in Parallel," Disc. fj Uomp. Geom., to appear.
• 28: Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
• 29: D. Haussler and E. Welzl, "Epsilon-nets and simplex range queries," Disc. ~ Comp. Geom., 2, 1987, 127-151.
• 30: Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• 31: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 32: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 33: M. Luby, "Removing randomness in parallel computation without a processor penalty," Proc. 29th IEEE Syrup. on Found. Comp. $ci., 1988, 162-173.
• 34: Jiří Matoušek, Cutting hyperplane arrangements, Discrete & Computational Geometry, v.6 n.5, p.385-406, 1991 [doi>10.1007/BF02574697]
• 35: Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
• 36: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
• 37: Jiří Matoušek , Emo Welzl , Lorenz Wernisch, Discrepancy and &egr; approximations for bounded VC-dimension, Proceedings of the 32nd annual symposium on Foundations of computer science, p.424-430, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185401]
• 38: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• 39: Rajeev Motwani , Joseph Seffi Naor , Moni Naor, The probabilistic method yields deterministic parallel algorithms, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.478-516, December 1994, Research Triangle Park, North Carolina, United States
• 40: John H. Reif , Sandeep Sen, Optimal parallel randomized algorithms for three-dimensional convex hulls and related problems, SIAM Journal on Computing, v.21 n.3, p.466-485, June 1992 [doi>10.1137/0221031]
• 41: John Taylor Rompel , Frank Thomson Leighton, Techniques for computing with low-independence randomness, 1990
• 42: Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding bounds for applications with limited independence, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.331-340, January 25-27, 1993, Austin, Texas, United States
• 43: N. Sauer, "On the density of families of sets," J. of Uombin. Theory Set. A, 13, 1972, 145-147.
• 44: V.N. Vapnik and A.Y. Chervonenkis, "On the uniform convergence of relative frequencies of events to their probabilities," Theory Probab. Appl., 16, 1971,264-280.
• 45: C.K. Yap, "Parallel Triangulation of a Polygon in Two Calls to the Trapezoidal Map," Algorithmica, 3, 1988, 279-288.

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.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Verification