An optimal parallel algorithm for detecting weak visibility of a simple polygon

ABSTRACT

The problem of detecting the weak visibility of an n-vertex simple polygon P is that of finding whether or not P is weakly visible from one of its edges and (if it is) identifying every edge from which P is weakly visible. In this paper, we present an optimal parallel algorithm for solving this problem. Our algorithm runs in O(log n) time using O(n/log n) processors in the CREW-PRAM computational model, and is very different from the sequential algorithms for this problem. This algorithm also enables us to optimally solve, in parallel, several other problems on weakly visible polygons.

REFERENCES

• 1: M. J. Atallah and M. T. Goodrich. "Parallel algorithms for some functions of two convex polygons," Algor~thmica, 3 (1988), pp. 535-548.
• 2: D. Avis ~nd G. T. Toussaint. "An optimal algorithm for determining the visibility polygon from an edge," IEEE Trans. Comput., C-30 (12) (1981), pp. 910-914.
• 3: B. K. Bhattacharya, A. Mukhopadhyay, and G. Toussaint. "A linear time algorithm for computing the shortest line segment from which a polygon is weakly externally visible," Proc. WADS, 1991, Ottawa, Canada, pp. 412-424.
• 4: 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]
• 5: D. Z. Chert, "Efficient geometric algorithms in the EREW-PRAM," Proc. ~8-th Annual Allerton Conf. Gommun., Contr., and Comput., 1990, pp. 818-827.
• 6: Y.T. Ching, 1VI. T. Ko, and H. Y. Tu. "On the cruising guard problems," TechnicM Report, 1989, Institute of Information Science, Academia Sinica, Taipei, Taiwan.
• 7: R. Cole , M. T. Goodrich, Optimal parallel algorithms for polygon and point-set problems, Proceedings of the fourth annual symposium on Computational geometry, p.201-210, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73414]
• 8: 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]
• 9: 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]
• 10: Michael T. Goodrich, Planar separators and parallel polygon triangulation (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.507-516, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129762]
• 11: 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]
• 12: L. Guibas, J. Hershberger, D. Leven, M. Sharir. and R. Tarjan. "Linear time algorithms for visibility and shortest paths problems inside triangulated simple polygons," Algorithmica, 2 (1987), pp. 209-233.
• 13: S. K. Ghosh, A. Maheshwari, S. P. Pal, S. Saluja, and C. E. V. Madhavan. "Characterizing weak visibility polygons and related problems," Tech. Rep., No. IISc- CSA-90-1, 1990, Dept. Comput. Sci. and Auto., Indian Institute of Science.
• 14: Paul J. Heffernan , Joseph S. B. Mitchell, Structured visibility profiles with applications to problems in simple polygons (extended abstract), Proceedings of the sixth annual symposium on Computational geometry, p.53-62, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98536]
• 15: Y. Ke. "Detecting the weak visibility of a simple polygon and related problems," Manuscript, Dept. of Cornput. Sci., The Johns Hopkins University, 1988.
• 16: C. P. Kruskal, L. Rudolph and M. Snir. "The power of parallel prefix," IEEE Trans. Comput., C-34 (1985), pp. 965-968.
• 17: 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]
• 18: D. T. Lee and A. Lin. "Computing the visibility polygon from an edge," Tech. Rep., Northwestern Univ., 1984.
• 19: 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]
• 20: M. H. Overmars and J. van Leeuwen. "Maintenance of configurations in the plane," J. Comput. and Syst. Scz., 23 (1981), pp. 166-204.
• 21: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 22: J.-R. Sack , S. Suri, An Optimal Algorithm for Detecting Weak Visibility of a Polygon, IEEE Transactions on Computers, v.39 n.10, p.1213-1219, October 1990 [doi>10.1109/12.59852]
• 23: G T Toussaint, A linear-time algorithm for solving the strong hidden-line problem in a simple polygon, Pattern Recognition Letters, v.4 n.6, p.449-451, Dec. 1986 [doi>10.1016/0167-8655(86)90043-7]
• 24: C. K. Yap. "Parallel triangulation of a polygon in two calls to the trapezoidM map," Algor~thm~ca, 3 (1988), pp. 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.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Verification