## Abstract

In this paper, we consider the problem of constructing a Voronoi diagram in L_{1}(L_{∞}) metric for a set of n points in the Cartesian plane on a mesh-connected computer. An O(√n) parallel algorithm on a √n × √n mesh-connected computer is given for solving that problem. This is the first solution on a √n × √n MCC to achieve an asymptotically optimal θ(√n) running time for L_{1}(L_{∞}) metric.

Original language | English |
---|---|

Pages (from-to) | 241-252 |

Number of pages | 12 |

Journal | Parallel Computing |

Volume | 17 |

Issue number | 2-3 |

DOIs | |

Publication status | Published - 1991 Jun |

Externally published | Yes |

### Bibliographical note

Funding Information:* Research supported in part by KOSEF grant.

## Keywords

- Parallel algorithm
- Voronoi diagram
- mesh-connected computer

## ASJC Scopus subject areas

- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Computer Graphics and Computer-Aided Design
- Artificial Intelligence

## Fingerprint

Dive into the research topics of 'Parallel voronoi diagram in L_{1}(L

_{∞}) metric on a mesh-connected computer'. Together they form a unique fingerprint.