A Parallel Algorithm for the Construction of Voronoi Diagrams

Voronoi diagram 構成のための並列アルゴリズム

A Parallel Algorithm for the Construction of Voronoi Diagrams

Creators Abe Tatsurou

Creators Inoue Katsushi

Creators Takanami Itsuo

Creators Taniguchi Hiroshi

This paper presents a new algorithm for the construction of Voronoi diagrams on a shared memory parallel computer, where both concurrent reads and concurrent writes are allowed, but all the processors that simultaneously try to write in the same memory cell must write the same value. The algorithm is a parallel version of the sequential algorithm (for the construction of Voronoi diagrams) of Shamos and Hoey. The algorithm, for n input points, runs in O ((log)^3n) time with only n processors.

[ISSN]0372-7661

[NCID]AN00244228