TY - CONF
T1 - Efficiently approximating the minimum-volume bounding box of a point set in three dimensions
AU - Barequet, Gill
AU - Har-Peled, Sariel
N1 - Funding Information:
1Work on this paper was done while the author was affiliated with the Center for Geometric Computing, Department of Computer Science, Johns Hopkins University, Baltimore, MD 21218, and was supported by the U.S. Army Research Office under Grant DAAH04-96-1-0013.
Funding Information:
2Work of the second author has been supported by a grant from the U.S.–Israeli Binational Science Foundation.
PY - 1999
Y1 - 1999
N2 - We present an efficient O(n+1/ε4.5) time algorithm for computing an (1+ε)-approximation of the minimum-volume bounding box of n points in R3. We also present a simpler algorithm (for the same purpose) whose running time is O(n log n+n/ε3). We give some experimental results with implementations of various variants of the second algorithm.
AB - We present an efficient O(n+1/ε4.5) time algorithm for computing an (1+ε)-approximation of the minimum-volume bounding box of n points in R3. We also present a simpler algorithm (for the same purpose) whose running time is O(n log n+n/ε3). We give some experimental results with implementations of various variants of the second algorithm.
UR - http://www.scopus.com/inward/record.url?scp=0032795121&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032795121&partnerID=8YFLogxK
M3 - Paper
AN - SCOPUS:0032795121
SP - 82
EP - 91
T2 - Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
Y2 - 17 January 1999 through 19 January 1999
ER -