## Abstract

In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position in E^{4}. Our algorithm runs in O((n + f) log^{2} f) time and uses O(n + f) space. This is the first algorithm within a polylogarithmic factor of optimal O(n log f + f) time over the whole range of f. By a standard lifting map, we obtain output-sensitive algorithms for the Voronoi diagram or Delaunay triangulation in E^{3} and for the portion of a Voronoi diagram that is clipped to a convex polytope. Our approach simplifies the "ultimate convex hull algorithm" of Kirkpatrick and Seidel in E^{2} and also leads to improved output-sensitive results on constructing convex hulls in E^{d} for any even constant d > 4.

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

Pages (from-to) | 433-454 |

Number of pages | 22 |

Journal | Discrete and Computational Geometry |

Volume | 18 |

Issue number | 4 |

DOIs | |

State | Published - Dec 1997 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics