# Item

ITEM ACTIONSEXPORT

Released

Report

#### The largest hyper-rectangle in a three dimensional orthogonal polyhedron

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-92-123.pdf

(Any fulltext), 12MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Krithivasan, K., Vanisree, R., & Datta, A.(1992). *The largest
hyper-rectangle in a three dimensional orthogonal polyhedron* (MPI-I-92-123). Saarbrücken: Max-Planck-Institut für
Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B6F9-4

##### Abstract

Given a three dimensional orthogonal
polyhedron P, we present a simple and
efficient algorithm for finding the three
dimensional orthogonal hyper-rectangle R
of maximum volume, such that R is completely
contained in P. Our algorithm finds out the
three dimensional hyper-rectangle of
maximum volume by using space sweep
technique and enumerating all possible
such rectangles. The presented algorithm
runs in O(($n^2$+K)logn) time using O(n)
space, where n is the number of vertices of
the given polyhedron P and K is the number
of reported three dimensional orthogonal
hyper-rectangles for a problem instance,
which is O($n^3$) in the worst case.