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

Gill Barequet; Sariel Har-Peled

doi:10.1006/jagm.2000.1127

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

Research output: Contribution to journal › Article › peer-review

Abstract

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 ℝ³. We also present a simpler algorithm whose running time is O(n log n + n/ε³). We give some experimental results with implementations of various variants of the second algorithm.

Original language	English (US)
Pages (from-to)	91-109
Number of pages	19
Journal	Journal of Algorithms
Volume	38
Issue number	1
DOIs	https://doi.org/10.1006/jagm.2000.1127
State	Published - Jan 2001
Externally published	Yes

Keywords

Approximation
Bounding box

ASJC Scopus subject areas

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Online availability

10.1006/jagm.2000.1127

Library availability

Discover UIUC Full Text

Cite this

@article{bd3698c7e33c4d189debf3d14eaa81d0,

title = "Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions",

abstract = "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.",

keywords = "Approximation, Bounding box",

author = "Gill Barequet and Sariel Har-Peled",

note = "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.",

year = "2001",

month = jan,

doi = "10.1006/jagm.2000.1127",

language = "English (US)",

volume = "38",

pages = "91--109",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

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 - 2001/1

Y1 - 2001/1

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

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

KW - Approximation

KW - Bounding box

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

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

U2 - 10.1006/jagm.2000.1127

DO - 10.1006/jagm.2000.1127

M3 - Article

AN - SCOPUS:0002755657

SN - 0196-6774

VL - 38

SP - 91

EP - 109

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this