An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram (Q2367127)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram |
scientific article |
Statements
An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram (English)
0 references
23 August 1993
0 references
The paper presents a work-optimal \(O(\log^ 2 n)\) time algorithm for computing the Voronoi diagram of \(n\) points in the \(L_ 1\) (or: Manhattan) metric, using \(O(n/\log n)\) many processors and exclusive read/write only. Such an algorithm was known before for the Euclidean metric in the concurrent read/exclusive write model. The favourable properties of the \(L_ 1\) metric allow two linearly separated Voronoi diagrams to be merged in \(O(\log n)\) time in the EREW model, using \(O(n/\log n)\) many processors, by reduction to list ranking and prefix computation.
0 references
computational geometry
0 references
Manhattan metric
0 references
parallel algorithms
0 references
Voronoi diagrams
0 references
