Skip to main content
SpringerLink
Log in

Visibility of disjoint polygons

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n 2) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n 2) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n 2) time, improving earlierO(n 2 logn) results.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. T. Asano, An efficient algorithms for finding the visibility polygons for a polygonal region with holes.Transaction of IECE of Japan, Vol. E-68 (1985), pp. 557–559.

    Google Scholar 

  2. K. Q. Brown, Geometric transforms for fast geometric algorithms. Ph.D. thesis, Department of Computer Science, Carnegie-Mellon University, 1980.

  3. B. Chazelle, Filtering search: a new approach to query-answering.Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson, 1983, pp. 122–132.

  4. B. Chazelle, L. J. Guibas and D. T. Lee, The power of geometric duality.Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson, 1983, pp. 217–225; also,BIT, Vol. 25 (1985), pp. 76–90.

  5. H. Edelsbrunner, J. O'Rourke and R. Seidel, Constructing arrangements of lines and hyperplanes with applications.Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson, 1983, pp. 83–91.

  6. H. Edelsbrunner, M. H. Overmars and D. Wood, Graphics in flatland: a case study. InAdvances in Computing Research (F. P. Preparata, ed.), Vol. 1, JAI Press Inc., 1983, pp. 35–59.

  7. H. El Gindy and D. Avis, A linear algorithm for computing the visibility polygon from a point.Journal of Algorithms, Vol. 2 (1981), pp. 186–197.

    Article  MATH  MathSciNet  Google Scholar 

  8. H. A. El Gindy and G. T. Toussaint, Efficient algorithms for inserting and deleting edges from triangulations. Manuscript, School of Computer Science, McGill University, 1984.

  9. H. N. Gabow and R. E. Tarjan, A linear-time algorithm for a special case of disjoint set union.Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, 1983, pp. 246–251; also,Journal of Computer and System Sciences, Vol. 30 (1985), pp. 209–221.

  10. M. R. Garey, D. S. Johnson, F. P. Preparata and R. E. Tarjan, Triangulating a simple polygon.Information Processing Letters, Vol. 7, No. 4 (1978), pp. 175–179.

    Article  MATH  MathSciNet  Google Scholar 

  11. D. Harel, A linear time algorithm for the lowest common ancestors problem.Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science, Syracuse, N.Y., 1980, pp. 308–319.

  12. D. T. Lee, Proximity and reachability in the plane. Ph.D. dissertation, University of Illinois at Urbana-Champaign, 1978.

  13. D. T. Lee, Visibility of a simple polygon.Computer Vision, Graphics, and Image Processing, Vol. 22 (1983), pp. 207–221.

    Article  MATH  Google Scholar 

  14. D. T. Lee and F. P. Preparata, Euclidean shortest paths in the presence of rectilinear barriers,Networks, Vol. 14 (1984), pp. 393–410.

    Article  MATH  MathSciNet  Google Scholar 

  15. T. Lozano-Perez and M. A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles.Comm. ACM, Vol. 22 (1979), pp. 560–570.

    Article  Google Scholar 

  16. M. Sharir and A. Schoorr, On shortest paths in polyhedral spaces.Proceedings of the 16th Annual ACM Symposium on Theory of Computing, Washington, D.C., 1984, pp. 144–153.

  17. E. Welzl, Constructing the visibility graph forn line segments inO(n 2) time.Information Processing Letters, Vol. 20 (1985), pp. 167–171.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Science and Technology, Sophia University, 102, Tokyo, Japan

    Takao Asano

  2. Osaka Electro-Communication University, Neyagawa, 572, Osaka, Japan

    Tetsuo Asano

  3. Computer Science Department, Stanford University, 94305, Stanford, California, USA

    Leonidas Guibas & John Hershberger

  4. DEC Systems Research Center, 94301, Palo Alto, California, USA

    Leonidas Guibas

  5. Department of Mathematical Engineering and Instrumentation Physics, Faculty of Engineering, University of Tokyo, 113, Tokyo, Japan

    Hiroshi Imai

Authors
  1. Takao Asano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tetsuo Asano
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Leonidas Guibas
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. John Hershberger
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Hiroshi Imai
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by D. T. Lee.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Asano, T., Asano, T., Guibas, L. et al. Visibility of disjoint polygons. Algorithmica 1, 49–63 (1986). https://doi.org/10.1007/BF01840436

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01840436

Key words

Search

Navigation