• DocumentCode
    2370164
  • Title

    An O(log N log log N) time RMESH algorithm for the simple polygon visibility problem

  • Author

    Kim, Sung-Ryul ; Park, Kunsoo ; Cho, Yoo-Kun

  • Author_Institution
    Dept. of Comput. Eng., Seoul Nat. Univ., South Korea
  • fYear
    1994
  • fDate
    14-16 Dec 1994
  • Firstpage
    151
  • Lastpage
    158
  • Abstract
    In this paper we consider the simple polygon visibility problem: Given a simple polygon P with N vertices and a point z in the interior of the polygon, find all the boundary points of P that are visible from z. We present an O(logN loglogN) time algorithm that solves the simple polygon visibility problem on a √N×√N RMESH. Previously, the best known algorithm for the problem on a √N×√N RMESH takes O(log2 N) time
  • Keywords
    computational complexity; computational geometry; parallel algorithms; RMESH algorithm; polygon visibility problem; simple polygon; simple polygon visibility; Bandwidth; Computational modeling; Computer science; Parallel algorithms; Parallel architectures; Phase change random access memory; Switches; Very large scale integration;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Architectures, Algorithms and Networks, 1994. (ISPAN), International Symposium on
  • Conference_Location
    Kanazawa
  • Print_ISBN
    0-8186-6507-6
  • Type

    conf

  • DOI
    10.1109/ISPAN.1994.367152
  • Filename
    367152
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2370164