### Abstract

In this paper we give a parallel algorithm for constructing the Voronoi diagram of a polygonal scene, i.e., a set of line segments in the plane such that no two segments intersect except possibly at their endpoints. Our algorithm runs in O(log^{2}n) time using O(n) processors in the CREW PRAM model.

Original language | English (US) |
---|---|

Pages (from-to) | 128-141 |

Number of pages | 14 |

Journal | Algorithmica |

Volume | 9 |

Issue number | 2 |

DOIs | |

State | Published - Feb 1993 |

### Keywords

- PRAM
- Parallel algorithm
- Voronoi diagram

### ASJC Scopus subject areas

- Computer Science(all)
- Computer Science Applications
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Constructing the Voronoi diagram of a set of line segments in parallel'. Together they form a unique fingerprint.

## Cite this

Goodrich, M. T., Ó'Dúnlaing, C., & Yap, C. K. (1993). Constructing the Voronoi diagram of a set of line segments in parallel.

*Algorithmica*,*9*(2), 128-141. https://doi.org/10.1007/BF01188708