Efficiently approximating the minimum-volume bounding box of a point set in three dimensions

Gill Barequet, Sariel Har-Peled

Research output: Contribution to conferencePaper

Abstract

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.

Original languageEnglish (US)
Pages82-91
Number of pages10
StatePublished - Jan 1 1999
Externally publishedYes
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

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

    Barequet, G., & Har-Peled, S. (1999). Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. 82-91. Paper presented at Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, .