Parallel voronoi diagram in L1 (L∞) metric on a mesh-connected computer

✍ Scribed by Chang-Sung Jeong

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 672 KB
• Volume: 17
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(05)80109-7

✦ Synopsis

Jeong, C.S., Parallel Voronoi diagram in L 1 (L~) metric on a mesh-connected computer, Parallel Computing 17 (1991) 241-252 In this paper, we consider the problem of constructing a Voronoi diagram in L~(L.o ) metric for a set of n points in the Cartesian plane on a mesh-connected computer. An o(vrn) parallel algorithm on a v~xvtn mesh-connected computer is given for solving that problem. This is the first solution on a Vr~ x Vt~ MCC to achieve an asymptotically optimal 0(vrn) running time for Ll(Loo ) metric.