An O(n log^2 h) time algorithm for the three-dimensional convex hull problem

H. Edelsbrunner, W. Shi, SIAM Journal on Computing 20 (1991) 259–269.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
Abstract
An algorithm is presented that constructs the convex hull of a set of n points in three dimensions in worst-case time O(n log2h) and storage O(n), where h is the number of extreme points. This is an improvement of the O(nh) time gift-wrapping algorithm and, for certain values of h, of the O(n log n) time divide-and-conquer algorithm.
Publishing Year
Date Published
1991-04-01
Journal Title
SIAM Journal on Computing
Volume
20
Issue
2
Page
259 - 269
IST-REx-ID

Cite this

Edelsbrunner H, Shi W. An O(n log^2 h) time algorithm for the three-dimensional convex hull problem. SIAM Journal on Computing. 1991;20(2):259-269. doi:10.1137/0220016
Edelsbrunner, H., & Shi, W. (1991). An O(n log^2 h) time algorithm for the three-dimensional convex hull problem. SIAM Journal on Computing, 20(2), 259–269. https://doi.org/10.1137/0220016
Edelsbrunner, Herbert, and Weiping Shi. “An O(n Log^2 h) Time Algorithm for the Three-Dimensional Convex Hull Problem.” SIAM Journal on Computing 20, no. 2 (1991): 259–69. https://doi.org/10.1137/0220016 .
H. Edelsbrunner and W. Shi, “An O(n log^2 h) time algorithm for the three-dimensional convex hull problem,” SIAM Journal on Computing, vol. 20, no. 2, pp. 259–269, 1991.
Edelsbrunner H, Shi W. 1991. An O(n log^2 h) time algorithm for the three-dimensional convex hull problem. SIAM Journal on Computing. 20(2), 259–269.
Edelsbrunner, Herbert, and Weiping Shi. “An O(n Log^2 h) Time Algorithm for the Three-Dimensional Convex Hull Problem.” SIAM Journal on Computing, vol. 20, no. 2, SIAM, 1991, pp. 259–69, doi:10.1137/0220016 .

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar