Determining sector visibility of a polygon

ABSTRACT

We consider a generalization of notions of external visibility of simple polygons, namely weak external visibility, weak external visibility from a line and monotonicity, that we call sector visibility. Informally, sector visibility addresses the question of external visibility along rays (or sight lines) whose angles are restricted to a sector (wedge) of specified width &sgr;. This provides an interesting measure of the degree of external visibility of a polygon. Our framework also permits a unification and extension of a number of previously unrelated results. Finally, our results uncover a curious complexity discontinuity in this family of problems; algorithms are &THgr;(n) when &sgr; ≤ &pgr; or &sgr; = 2&pgr;, but require &OHgr;(n log n) time (at least), when &pgr; < &sgr; < 2&pgr;.

REFERENCES

• AB: Mikhail Atallah , Chanderjit Bajaj, Efficient algorithms for common transversals, Information Processing Letters, v.25 n.2, p.87-91, 6 May 1987 [doi>10.1016/0020-0190(87)90226-2]
• AW1: D. Avis , R. Wenger, Algorithms for line transversals in space, Proceedings of the third annual symposium on Computational geometry, p.300-307, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41990]
• AW2: David Avis , Rephael Wenger, Polyhedral line transversals in space, Discrete & Computational Geometry, v.3 n.3, p.257-265, Jan., 1988 [doi>10.1007/BF02187911]
• AT: Avis, A. and Touasaint, G.T., "An optimal algorithm for determining the visibility of a polygon from an edge," IEEE Transactions on Computers, Vol. C-30, No. 12, December 1981, pp. 910-914.
• BL: Bajaj, C. and Li, M., "On the duality of intersection and closest points," Proc. Mat Allerton Conference, 1983, pp. 459-461.
• B-O: Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
• Ed: Edelsbrunner, H., "Finding transversals for sets of simple geometric figures,", Theoretical Computer Science, Vol. 35, 1985, pp. 5549.
• EOW: Edelsbrunner, H., Overmarks, M.H., and Wood, D., "Graphics in flatland: a case study," Tech. Report F79, Technical University of Gras, 1981.
• E1: Hossam Ahmed Elgindy, Hierarchical decomposition of polygons with applications, 1985
• EMPRWW: Edelsbrunner, H., Maurer, H.A., Preparata; F.P., Rosenberg, A.L., Welsl, E. and Wood, D., "Stabbing line segments,", BIT, Vol. 22, 1982, pp. 274-281.
• ET: ElGindy, H. and Toussaint, G.T., "Efficient algorithms for inserting and deleting edges from triangulations," Proc. Intl. Conf. on Foundations of Data Organization, Kyoto, Japan, May 1985.
• Gr: Grunbaum, B., "On common transversals," Arch. Math., Vol. 9, 1958, pp. 465469.
• HV: Horn, A. and Valentine, F.A., "Some propertiea of L-sets in the plane," Duke Mathematics Journal, Vol. 16, 1949, pp. 131-140.
• Ke: Ke, Y., "Detecting the weak visibility of a simple polygon and related problems," The Johns Hopkins University, manuscript, March 1988.
• Le: Lewis, T., "Two counterexamples concerning transversals for convex subsets of the plane," Geometriae Dedicata, Vol. 9, 1980, pp. 461.465.
• MA: McCallum, D. and Avis, D., "A linear time algorithm for finding the convex hull of a simple polygon," Information Processing Letters, Vol. 8, pp. 201-205.
• MT: Mansouri, M. and Toussaint, G.T., "On the reachability of a ladder in two convex polygons," Ptoc. 18th IFIP Conf. on Syatem Model& and Optimization, Tokyo, Japan, August 1987.
• O'R: Joseph O'Rourke, An on-line algorithm for fitting straight lines between data ranges, Communications of the ACM, v.24 n.9, p.574-578, Sept. 1981 [doi>10.1145/358746.358758]
• Re: M. Reichling, On the detection of a common intersection of k convex objects in the plane, Information Processing Letters, v.29 n.1, p.25-29, Sept. 15, 1988 [doi>10.1016/0020-0190(88)90127-5]
• RS: Rosenfeld, B.A. and Sergeeva, N.D., Stereographic Projection, Mir Publishers, Moscow, 1977.
• SS: Sack, J.-R. and Suri, S., "An optimal algorithm for detecting weak visibility of a polygon," Tech. Report SCS-TR114, Carleton University, Ottawa, Canada, Dec. 1986.
• ST: Shermer, T. and Touasaint, G.T., "Characterirations of convex and star-shaped polygons," in Snapshots of Computational and Discrete Geometry, G. Toussaint, editor, Tech. Report SOCS-88.11, School of Computer Science, McGill University, June 1988.
• TA: Toussaint, G.T. and Avis, D., "On a convex hull algorithm for polygons and its application to triangulation problems," Pattern Recognition, Vol. 15, No. 1, 19892, pp. 23- 29.
• To: Toussaint, G.T., "Complexity, convexity, and unimodality," International Journal of Computer and Information Sciences, Vol. 13, No. 3, June 1984, pp. 197-217.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms

General Terms:
Algorithms, Theory