### 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 R^{3}. 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 language | English (US) |
---|---|

Pages | 82-91 |

Number of pages | 10 |

State | Published - Jan 1 1999 |

Externally published | Yes |

Event | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999 |

### Other

Other | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

City | Baltimore, MD, USA |

Period | 1/17/99 → 1/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, .