非表示:
キーワード:
-
要旨:
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.
