A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams

Columbus, Ohio August 14-August 18

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/ICPP.2006.5

2006 International Conference on Para ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Frank Dehne Articles by Anil Maheshwari Articles by Ryan Taylor

	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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.