loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2006 International Conference on Parallel Processing (ICPP'06)
A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams
Columbus, Ohio
August 14-August 18
ISBN: 0-7695-2636-5
ASCII Text
x 
 
Frank Dehne, Anil Maheshwari, Ryan Taylor, "A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams," Parallel Processing, International Conference on, pp. 497-504, 2006 International Conference on Parallel Processing (ICPP'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/ICPP.2006.5,
author = {Frank Dehne and Anil Maheshwari and Ryan Taylor},
title = {A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams},
journal ={Parallel Processing, International Conference on},
volume = {0},
year = {2006},
issn = {0190-3918},
pages = {497-504},
doi = {http://doi.ieeecomputersociety.org/10.1109/ICPP.2006.5},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel Processing, International Conference on
TI - A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams
SN - 0190-3918
SP497
EP504
A1 - Frank Dehne,
A1 - Anil Maheshwari,
A1 - Ryan Taylor,
PY - 2006
KW - null
VL - 0
JA - Parallel Processing, International Conference on
ER -
 
Frank Dehne, Carleton University, Canada
Anil Maheshwari, Carleton University, Canada
Ryan Taylor, Carleton University, Canada
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 log^4 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 noncrossing objects in time O(n log^4 n). This improves on previous sequential results and solves an open problem posed by Papadopoulou and Lee [18].

Citation:
Frank Dehne, Anil Maheshwari, Ryan Taylor, "A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams," icpp, pp.497-504, 2006 International Conference on Parallel Processing (ICPP'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.