✦ LIBER ✦

Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions

✍ Scribed by Gill Barequet; Sariel Har-Peled

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 221 KB
Volume: 38
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1127

No coin nor oath required. For personal study only.

✦ Synopsis

We present an efficient O n + 1/ε 4 5 -time algorithm for computing a 1 + ε)approximation of the minimum-volume bounding box of n points in 3 . We also present a simpler algorithm whose running time is O n log n + n/ε 3 . We give some experimental results with implementations of various variants of the second algorithm.