Parallel methods for visibility and shortest path problems in simple polygons (preliminary version)

ABSTRACT

In this paper we give efficient parallel algorithms for solving a number of visibility and shortest path problems for simple polygons. Our algorithms all run in &Ogr;(log n) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygon P, which we call the stratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility of P from an edge, constructing the visibility graph of the vertices of P (using an output-sensitive number of processors), constructing the shortest path tree from a vertex of P, and determining all-farthest neighbors for the vertices in P. The computational model we use is the CREW PRAM.

REFERENCES

• 1: A. Aggarwal and J.K. Park, "Parallel searching in Multidimensional Monotone Arrays," manuscript, 1989.
• 2: Richard J. Anderson , Gary L. Miller, Deterministic Parallel List Ranking, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.81-90, June 28-July 01, 1988
• 3: M. J. Atallah , D. Z. Chen, Optimal parallel algorithm for visibility of a simple polygon from a point, Proceedings of the fifth annual symposium on Computational geometry, p.114-123, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73846]
• 4: 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]
• 5: D. Avis and G.T. Toussaint, "An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge," IEEE Trans. on Computers, C-30, 1981, 910-914.
• 6: Gianfranco Bilardi , Alexandru Nicolau, Adaptive bitonic sorting: an optimal parallel algorithm for shared-memory machines, SIAM Journal on Computing, v.18 n.2, p.216-228, April 1989 [doi>10.1137/0218014]
• 7: B. Chazelle, "A theorem on polygon cutting with applications," Proc. 2o~rd FOCS, 1982, 339-349.
• 8: Bernard Chaselle, Intersecting is easier than sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.125-134, December 1984 [doi>10.1145/800057.808674]
• 9: B. Chazelle, "Efficient Polygon Triangulation," Report CS-TR-249-90, Princeton University, February 1990.
• 10: B. Chazelle and L.J. Guibas, "Fractional Cascading: I. A Data Structuring Technique," Algorithmica, 1(2), 1986, 133-162.
• 11: B. Chazelle and L.J. Guibas, "Visibility and Intersection Problems in Plane Geometry," Report CS- TR-167-88, Princeton Univ., 1988.
• 12: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 13: H. Edelsbrunner, H.A. Maurer, F.P. Preparata, A.L. Rosenberg, E. Welzl, and D. Wood, "Stabbing Line Segments," BIT, 22, 1982, 274-281.
• 14: H. EIGindy and D. Avis, "A Linear Algorithm for Computing the Visibility Polygon from a Point," J. of Algorithms, 2, 1981, 186-197.
• 15: E1Gindy, H., and Goodrich, M.T., "Parallel Algorithms for Shortest Path Problems in Polygons," The Visual Computer, 3(6), 1988, 371-378.
• 16: M.R. Garey, D.S. Johnson, F.P. Preparata, and R.E. Tarjan, "Triangulating a Simple Polygon," Info. Proc. Let., 7{4}, 1978, 175-179.
• 17: M. T. Goodrich, Triangulating a polygon in parallel, Journal of Algorithms, v.10 n.3, p.327-351, September 1989 [doi>10.1016/0196-6774(89)90032-1]
• 18: M. T. Goodrich, Intersecting line segments in parallel with an output-sensitive number of processors, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.127-137, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72950]
• 19: 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]
• 20: L Guibas , J Hershberger , D Leven , M Sharir , R Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons, Proceedings of the second annual symposium on Computational geometry, p.1-13, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10516]
• 21: L.J. Guibas, L. Ramshaw, J. Stolfi, "A Kinetic Framework for Computational Geometry," Proc. ~th FOCS, 1983, 100-111.
• 22: J. Hershberger, "Finding the Visibility Graph of a Simple Polygon in Time Proportional to its Size," Algorithmica, 4, 1989, 141-155.
• 23: Kruskal, C.P., Rudolph, L., and Snir, M., "The Power of Parallel Prefix," lg85 Int. Conf. on Par. Proc., 180-185.
• 24: 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]
• 25: D.T. Lee and F.P. Preparata, "Euclidean Shortest Paths in the Presence of Rectilinear Barriers," Networks, 14, 1984, 393-410.
• 26: D.E. Muller and F.P. Preparata, "Finding the Intersection of Two Convex Polyhedra," T.C.S., 7(2), 1978, 217-236.
• 27: M.H. Overmars, and J. Van L~uwen, "Maintenance of Configurations in the Plane," J.C.S.S., 23, 1981, 166-204.
• 28: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 29: C. Rfib, "Parallel Line Segment Intersection Reporting," manuscript, 1989.
• 30: J. Stolfi, Oriented projective geometry, Proceedings of the third annual symposium on Computational geometry, p.76-85, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41966]
• 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 C.J. Van Wyk, "An O(n log log n) Time Algorithm for Triangulating Simple Polygons," Report CS-TR-052-86, Princeton University, 1986.
• 34: C.K. Yap, "Parallel Triangulation of a Polygon in Two Calls to the Trapezoidal Map," manuscript, 1987.

INDEX TERMS

Primary 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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  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: Path and circuit problems

General Terms:
Algorithms