Optimal parallel algorithms for polygon and point-set problems

ABSTRACT

In this paper we give parallel algorithms for a number of problems defined on polygons and point sets. All of our algorithms have optimal T(n) * P(n) products, where T(n) is the time complexity and P(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. In addition, our algorithms provide parallel analogues to well known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently that point-set problems, and that one can solve nearest-neighbor problems without explicitly constructing a Voronoi diagram.

REFERENCES

• 1: A. Aggarwal, B. Chazelh, L. Guiba~, C. 0'Ddnlaing, and C. Yap, "Parallel Computational Geometry," manuscript, 1987 (a preliminary version appeared in Proc. lg5th IEEE Syrnp. on Found. of Comp. Sci., 1985, 468-477).
• 2: M.J. Atallah, R. Cole, and M.T. Goodrich, "Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms," Proc. Ig8th IEEE Syrup. on Found. of Comp. Sci., 1987, 151-160.
• 3: Mikhail J. Atallah , Michael T. Goodrich, Efficient parallel solutions to some geometric problems, Journal of Parallel and Distributed Computing, v.3 n.4, p.492-507, December 1, 1986 [doi>10.1016/0743-7315(86)90011-0]
• 4: M.J. Atallah and M.T. Goodrich, "Parallel Algorithms for Some Functions of Two Convex Polygons," to appear Algorithmica.
• 5: Jon Louis Bentley , Michael Ian Shamos, Divide-and-conquer in multidimensional space, Proceedings of the eighth annual ACM symposium on Theory of computing, p.220-230, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803652]
• 6: Gianfranco Bilardi , Alexandru Nicolau, Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared Memory Machines, Cornell University, Ithaca, NY, 1986
• 7: Anita Liu Chow, Parallel algorithms for geometric problems, 1980
• 8: R. Cole, "Parallel Merge Sort," Proc. ~Tth IEEE Syrup. on Found. of Comp. Sci., 1986, 511-516.
• 9: Michael Truman Goodrich , Mikhail J. Atallah, Efficient parallel techniques for computational geometry, 1987
• 10: M. T. Goodrich, Finding the convex hull of a sorted point set in parallel, Information Processing Letters, v.26 n.4, p.173-179, Dec. 4, 1987 [doi>10.1016/0020-0190(87)90002-0]
• 11: L. Guibas, L. Ramshaw, and J. Stolfi, "A Kinetic Framework for Computational Geometry," Proc. tgtth IEEE Syrup. on Found. of Comp. Sci., 1983, 100-111.
• 12: C.P. Kruskal, L. Rudolph, and M. Snir, "The Power of Parallel Prefix,~ Proc. 1985 IEEE Int. Conf. on Parallel Processing, 180-185.
• 13: Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
• 14: D.T. Lee and F.P. Preparata, "The All Nearest- Neighbor Problem for Convex Polygons,~ Info. Proc. Letters, Vol. 7, No. 4, June 1978, 189-192.
• 15: D. T. Lee , F. P. Preparata, An Optimal Algorithm for Finding the Kernel of a Polygon, Journal of the ACM (JACM), v.26 n.3, p.415-421, july 1979 [doi>10.1145/322139.322142]
• 16: F.P. Preparata and D.E. Muller, "Finding the Intersection of n Half-spaces in Time O(n log n)," Theoretical Comp. Sci., Vol. 8, 1979, 45-55.
• 17: Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
• 18: G.T. Toussaint, ~Solving Geometric Problems with Rotating Calipers," Proc. IEEE MELE- CON '83, Athens, Greece, May 1983.
• 19: H. Wagener, ~Optimally Parallel Algorithms for Convex Hull Determination," unpublished manuscript, September 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:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.2 DISCRETE MATHEMATICS
      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; Curve, surface, solid, and object representations

General Terms:
Algorithms, Design, Measurement, Performance, Theory