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

Timothy M.Y. Chan; Jack Snoeyink; Chee Keng Yap

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

Timothy M.Y. Chan, Jack Snoeyink, Chee Keng Yap

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In this paper, we give an algorithm for output-sensitn construction of an f-face polytope that is defined by halfspaces in E⁴. Our algorithm runs in O((n + /)log² ) 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 E³ 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 E².

Original language	English (US)
Title of host publication	Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Publisher	Association for Computing Machinery
Pages	282-291
Number of pages	10
ISBN (Electronic)	0898713498
State	Published - Jan 22 1995
Event	6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 - San Francisco, United States Duration: Jan 22 1995 → Jan 24 1995

Publication series

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

Other

Other	6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Country/Territory	United States
City	San Francisco
Period	1/22/95 → 1/24/95

ASJC Scopus subject areas

Software
General Mathematics

Cite this

Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three. / Chan, Timothy M.Y.; Snoeyink, Jack; Yap, Chee Keng.
Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Association for Computing Machinery, 1995. p. 282-291 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chan, TMY, Snoeyink, J & Yap, CK 1995, Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three. in Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 282-291, 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995, San Francisco, United States, 1/22/95.

@inproceedings{149ed339e6e047b0948d89fe6c1f1d2d,

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 = "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. Copyright: Copyright 2018 Elsevier B.V., All rights reserved.; 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",

}

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. Copyright: Copyright 2018 Elsevier B.V., All rights reserved.

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 -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this