Optimal parallel algorithms for triangulated simple polygons

ABSTRACT

We provide optimal parallel solutions to several shortest path and visibility problems set in triangulated simple polygons. Let P be a triangulated simple polygon with n vertices, preprocessed to support shortest path queries. We can find the shortest path tree from any point inside P in O(log n) time using O(n/log n) processors. In the same bounds, we can preprocess P for shooting queries (a query can be answered in O(log n0 time by a uniprocessor). Given a set S of m points inside P, we can find an implicit representation of the relative convex hull of S in O(log(nm)) time with O(k/log(nm)) processors. All of these algorithms are deterministic and use the CREW PRAM model.

REFERENCES

• 1: Mikhail J. Atallah , Hubert Wagener , Danny Z. Chen, An optimal parallel algorithm for the visibility of a simple polygon from a point, Journal of the ACM (JACM), v.38 n.3, p.515-532, July 1991 [doi>10.1145/116825.116827]
• 2: M. J. Atallah , R. Cole , M. T. Goodrich, Cascading divide-and-conquer: a technique for designing parallel algorithms, SIAM Journal on Computing, v.18 n.3, p.499-532, June 1989 [doi>10.1137/0218035]
• 3: M.J. Atallah and M. T. Goodrich. Parallel algorithms for some functions of two convex polygons. In Proceedings of the 24th Annual Allerton Conference on Communication, Control, and Computing, pages 758-767, 1986.
• 4: D. Avis and G. T. Toussaint. An optimal algorithm for determining the visibility of a polygon from an edge. IEEE Trans. Comput., C-30:910-914, 1981.
• 5: B. BhaUacharya and G. Toussaint. A linear algorithm for determining translation separability of two simple polygons. Technical Report SOCS-86.1, School of Computer Science, McGill University, Montreal, 1986.
• 6: V. Chandru, S. K. Ghosh, A. Maheshwari, V. T. Rajan, and S. Saluja. A/'~-algorithms for minimum link path and related problems. Theoretical Computer Science Report CS-90/3, Tam Institute of Fundamental Research, Homi Bhabha Road, Bombay 400 005, April 1991.
• 7: B. Chazelle. A theorem on polygon cutting with applications. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pages 339-349. IEEE, 1982.
• 8: Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
• 9: Bernard Chazelle , Herbert Edelsbrunner , Michelangelo Grigni , Leonidas Guibas , John Hershberger , Micha Sharir , Jack Snoeyink, Ray shooting in polygons using Geodesic triangulations, Proceedings of the 18th international colloquium on Automata, languages and programming, p.661-673, June 1991, Madrid, Spain
• 10: B. Chazelle , L. J. Guibas, Visibility and intersection problems in plane geometry, Discrete & Computational Geometry, v.4 n.6, p.551-581, Sep. 1989 [doi>10.1007/BF02187747]
• 11: B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1'133-162, 1986.
• 12: Kenneth L. Clarkson , Richard Cole , Robert E. Tarjan, Randomized parallel algorithms for trapezoidal diagrams, Proceedings of the seventh annual symposium on Computational geometry, p.152-161, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109665]
• 13: Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
• 14: R. Cole and U. Vishkin. The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time. Algorithmica, 3:329-346, 1988.
• 15: David P. Dobkin , David G. Kirkpatrick, Fast Detection of Polyhedral Intersections, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.154-165, July 12-16, 1982
• 16: Michael T. Goodrich , Steven B. Shauck , Sumanta Guha, Parallel methods for visibility and shortest path problems in simple polygons (preliminary version), Proceedings of the sixth annual symposium on Computational geometry, p.73-82, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98539]
• 17: S. Guha. Parallel computation of internal and external farthest neighbors in simple polygons. Manuscript, EECS Department, University of Michigan, Ann Arbor, MI 48109-2122, 1991.
• 18: L. J. Guibas , J. Hershberger, Optimal shortest path queries in a simple polygon, Journal of Computer and System Sciences, v.39 n.2, p.126-152, Oct. 1989 [doi>10.1016/0022-0000(89)90041-X]
• 19: L. Guibas, J. Hershberger, D. Leven, M. Shark, and R. Tarjan. Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209-233, 1987.
• 20: L. Guibas, J'. Hershberger, and J. Snoeyink. Compact interval trees: A data structure for convex hulls. Int. J. Comp. Geometry & Appl., 1(1):1-22, 1991.
• 21: John Hershberger, A new data structure for shortest path queries in a simple polygon, Information Processing Letters, v.38 n.5, p.231-235, June 14, 1991 [doi>10.1016/0020-0190(91)90064-O]
• 22: J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. In Proceedings of the 2nd Workshop on A l gorithms and Data Structures, pages 331-342. Springer-Verlag, 1991. Lecture Notes in Computer Science 519.
• 23: C. P. Kruskal, L. Rudolph, and M. Snir. The power of parallel prefix. In Douglas DeGroot, editor, Proceedings of the IEEE International Conference on Parallel Processing, pages 180-185, 1985.
• 24: D. T. Lee and F. P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14(3):393--410, 1984.
• 25: M. A. Peshkin and A. C. Sanderson. Reachable grasps on a polygon: The convex rope algorithm. Technical Report CMU-RI-TR-85-6, Carnegie-Mellon University, 1985. To appear in IEEE Transactions on Robotics and Automation.
• 26: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 27: S. Rajasekaran , J. H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM Journal on Computing, v.18 n.3, p.594-607, June 1989 [doi>10.1137/0218041]
• 28: B. Schieber , U. Vishkin, On finding lowest common ancestors: simplification and parallelization (extended summary), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
• 29: R. Seidel. A simple and fast incrementalrandomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Manuscript, Computer Science Department, UC Berkeley, 1990.
• 30: Y. Shiloach and U. Vishlcin. Finding the maximum, merging, and sorting in a parallel computation model. J. Alg., 2(1):88- 102, 1981.
• 31: S. Suri, Computing geodesic furthest neighbors in simple polygons, Journal of Computer and System Sciences, v.39 n.2, p.220-235, Oct. 1989 [doi>10.1016/0022-0000(89)90045-7]
• 32: R. Tamassia , J. S. Vitter, Optimal parallel algorithms for transitive closure and point location in planar structures, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.399-408, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72978]
• 33: R. E. Tarjan and U. Vishkin. An efficient parallel biconnectivity algorithm. SIAM J. Cornput., 14(4):862-874, 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.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.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Verification