TY - GEN

T1 - Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three

AU - Chan, Timothy M.Y.

AU - Snoeyink, Jack

AU - Yap, Chee Keng

N1 - Funding Information:
*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.

PY - 1995/1/22

Y1 - 1995/1/22

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0039173487&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0039173487&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0039173487

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 282

EP - 291

BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

PB - Association for Computing Machinery

T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

Y2 - 22 January 1995 through 24 January 1995

ER -