• DocumentCode
    2503978
  • Title

    A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams

  • Author

    Dehne, Frank ; Maheshwari, Anil ; Taylor, Ryan

  • Author_Institution
    Sch. of Comput. Sci., Carleton Univ., Ottawa, Ont.
  • fYear
    2006
  • fDate
    14-18 Aug. 2006
  • Firstpage
    497
  • Lastpage
    504
  • Abstract
    We present the first parallel algorithm for building a Hausdorff Voronoi diagram (HVD). Our algorithm is targeted towards cluster computing architectures and computes the Hausdorff Voronoi diagram for non-crossing objects in time O((n log4 n)/p) for input size n and p processors. In addition, our parallel algorithm also implies a new sequential HVD algorithm that constructs HVDs for non-crossing objects in time O(n log4 n). This improves on previous sequential results and solves an open problem posed by Papadopoulou and Lee (2004)
  • Keywords
    computational complexity; computational geometry; parallel algorithms; workstation clusters; Hausdorff Voronoi diagrams; cluster computing architectures; coarse grained parallel algorithm; computational complexity; Buildings; Circuit faults; Clustering algorithms; Computational geometry; Computer architecture; Computer science; Impurities; Manufacturing processes; Parallel algorithms; Very large scale integration;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Processing, 2006. ICPP 2006. International Conference on
  • Conference_Location
    Columbus, OH
  • ISSN
    0190-3918
  • Print_ISBN
    0-7695-2636-5
  • Type

    conf

  • DOI
    10.1109/ICPP.2006.5
  • Filename
    1690654
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2503978