• DocumentCode
    3487182
  • Title

    Testing a simple polygon for monotonicity optimally in parallel

  • Author

    Chen, Danny Z. ; Guha, Saikat

  • Author_Institution
    Dept. of Comput. Sci. & Eng., Notre Dame Univ., IN, USA
  • fYear
    1993
  • fDate
    13-16 Apr 1993
  • Firstpage
    326
  • Lastpage
    330
  • Abstract
    The authors show that, in parallel, an n-vertex simple polygon can be tested for monotonicity optimally in O(logn ) time using O(n/logn) EREW PRAM processors, and present two different optimal parallel algorithms for solving this problem. Their result leads to an optimal parallel algorithm for triangulating monotone polygons that takes O(log n) time using O(n/logn) EREW PRAM processors
  • Keywords
    computational geometry; parallel algorithms; EREW PRAM; monotonicity optimally; n-vertex simple polygon; optimal parallel algorithms; simple polygon testing; triangulating monotone polygons; Computational geometry; Computer science; Concurrent computing; Machinery; Parallel algorithms; Phase change random access memory; Sequential analysis; Testing;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Processing Symposium, 1993., Proceedings of Seventh International
  • Conference_Location
    Newport, CA
  • Print_ISBN
    0-8186-3442-1
  • Type

    conf

  • DOI
    10.1109/IPPS.1993.262900
  • Filename
    262900
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3487182