A Parallel Algorithm for the Construction of Voronoi Diagrams

Memoirs of the Faculty of Engineering, Yamaguchi University Volume 39 Issue 1 Page 225-233

published_at 1988-10

KJ00000156724.pdf

[fulltext] 738 KB

Title

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

A Parallel Algorithm for the Construction of Voronoi Diagrams

Creators Abe Tatsurou

Creators Inoue Katsushi

Creators Takanami Itsuo

Creators Taniguchi Hiroshi

Source Identifiers

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.

Subjects

電気電子工学 ( Other)

Languages jpn

Resource Type departmental bulletin paper

Publishers 山口大学工学部

Date Issued 1988-10

File Version Version of Record

Access Rights open access

Relations

[ISSN]0372-7661

[NCID]AN00244228

Schools 工学部