A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	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

2006 International Conference on Parallel Processing (ICPP'06)

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

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

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.