Optimal parallel algorithm for visibility of a simple polygon from a point

ABSTRACT

We present a parallel algorithm for computing the visible portion of a simple polygonal chain with n vertices from a point in the plane. The algorithm runs in &Ogr;(log n) time using &Ogr;(n/ log n) processors in the CREW-PRAM computational model, and hence is asymptomatically optimal.

REFERENCES

• ACG: Atallah, M., Cole, R., and Goodrich, M. "Cascading divide-and-conquer: a technique for designing parallel algorithm." Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 151-160.
• AHU: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• C: Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
• CD: B. Chazelle , D. P. Dobkin, Intersection of convex objects in two and three dimensions, Journal of the ACM (JACM), v.34 n.1, p.1-27, Jan. 1987 [doi>10.1145/7531.24036]
• DS: Dean, J. A., and Sack, J. R. "Efficient hiddenline elimination by capturing winding information." Proc. &Jrd Annual Allerton Conference on Communication, Control, and Computing, 1985, pp. 496-505.
• EA: El-Gindy, H., and Avis, D. "A linear algorithm for computing the visibility polygon from a point." J. of Algorithms Z (1981)) 186- 197.
• G: 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]
• HS: Hall, D. W., and Spencer, G. Elementary Topology. Wiley, New York, 1955.
• KRS: Kruskal, C. P., Rudolph, L., and Snir, M. "The power of parallel prefix." IEEE Trans. on Computers C-34 (1985), 965-968.
• L: Lee, D. T. "Visibility of a simple polygon." Computer Vision, Graphics, and Image Processing 82 (1983), 207-221.
• LF: 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]
• P: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• Wa: Wagener, H. "Optimally parallel algorithms for convex hull determination." Unpublished manuscript, Sept. 1985.
• We: Welzl, E. "Constructing the visibility graph for n line segments in O(na) time." Inform. Proc. Lett. 20 (1985), 167-171.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  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.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Theory