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

Gill Barequet, Sariel Har-Peled

Research output: Contribution to journalArticlepeer-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 ℝ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.

Original languageEnglish (US)
Pages (from-to)91-109
Number of pages19
JournalJournal of Algorithms
Volume38
Issue number1
DOIs
StatePublished - Jan 2001
Externally publishedYes

Keywords

  • Approximation
  • Bounding box

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions'. Together they form a unique fingerprint.

Cite this