@inproceedings{0ef6a22c1ce041b8b427542a459a02b2,
title = "Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three",
abstract = "In this paper, we give an algorithm for output-sensitn construction of an f-face polytope that is defined by halfspaces in E4. Our algorithm runs in O((n + /)log2 ) time and uses 0(n + f) space. This is the first algorithi within a polylogarithmic factor of optimal 0(n logf/ + f) time over the whole range of f. By a standard liftir map, we obtain output-sensitive algorithms for the Voroni diagram or Delaunay triangulation in E3 and for the portic of a Voronoi diagram that is clipped to a convex polytop Our approach also simplifies the {"}ultimate convex hn algorithm{"} of Kirkpatrick and Seidel in E2.",
author = "Chan, {Timothy M.Y.} and Jack Snoeyink and Yap, {Chee Keng}",
note = "*The authors have been supported in part by a Killam Graduate Fellowship, an NSERC Research Grant, a B.C. Advanced Systems Institute Fellowship, and and NSF grants #CCR-87-03458 and #CCR-94-02464.; 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 ; Conference date: 22-01-1995 Through 24-01-1995",
year = "1995",
month = jan,
day = "22",
language = "English (US)",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery",
pages = "282--291",
booktitle = "Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995",
address = "United States",
}