## Abstract

Using a divide, prune, and conquer approach based on geometric partitioning, we obtain: (1) an output sensitive algorithm for computing a weighted Voronoi diagram in R^{4} (the projection of certain polyhedra in R^{5}) that runs in time O((n + f)log^{3} f) where n is the number of sites and f is the number of output cells; and (2) a deterministic parallel algorithm in the EREW PRAM model for computing an algebraic planar Voronoi diagram (in which bisectors between sites are simple curves consisting of a constant number of algebraic pieces of constant degree) that runs in time O(log^{2} n) using optimal O(n log n) work. The first result implies an algorithm for the problems of computing the convex hull of a point set and the intersection of a set of halfspaces in R^{5}, and computing the Euclidean Voronoi diagram in R^{4}. The second result implies both sequential and parallel work-optimal deterministic algorithms for a number of Voronoi diagram problems (including line segments in the plane), and other non-Voronoi diagram problems that can fit in the framework (including the intersection of equal radius balls in R^{3} and some lower envelope problems in R^{3}).

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

Pages | 166-175 |

Number of pages | 10 |

DOIs | |

State | Published - 1996 |

Externally published | Yes |

Event | Proceedings of the 1996 12th Annual Symposium on Computational Geometry - Philadelphia, PA, USA Duration: May 24 1996 → May 26 1996 |

### Other

Other | Proceedings of the 1996 12th Annual Symposium on Computational Geometry |
---|---|

City | Philadelphia, PA, USA |

Period | 5/24/96 → 5/26/96 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics