• DocumentCode
    1298257
  • Title

    An optimal algorithm for detecting weak visibility of a polygon

  • Author

    Sack, JÖrg-rÜdiger ; Suri, Subhash

  • Author_Institution
    Sch. of Comput. Sci., Carleton Univ., Ottawa, Ont., Canada
  • Volume
    39
  • Issue
    10
  • fYear
    1990
  • fDate
    10/1/1990 12:00:00 AM
  • Firstpage
    1213
  • Lastpage
    1219
  • Abstract
    Notation and a theorem are presented which, using a result of B. Chazelle and L.J. Guibas (1985), enable the authors to design an O (n log n) algorithm for reporting all visibility edges of a given n-vertex polygon. Improving on this bound to O(n) is presently focused upon. This problem is solved for polygons with at least one given visibility edge. It is assumed that both endpoints of this edge are convex vertices. Subsequently, it is shown how to drop this restriction. The general case of detecting weak edge visibility of an arbitrary simple polygon is dealt with
  • Keywords
    computational complexity; computational geometry; convex vertices; endpoints; n-vertex polygon; optimal algorithm; visibility detection; visibility edges; weak edge visibility; Application software; Computational complexity; Computational geometry; Computer graphics; Helium; Image processing; Image segmentation; Kernel; Process control; Robot control;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/12.59852
  • Filename
    59852
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1298257