  Voronoi diagrams are a fundamental geometric data structure for obtaining
proximity relations. We consider collections of axis-aligned orthogonal
polyhedra in two and three-dimensional space under the max-norm, which is a
particularly useful scenario in certain application domains. We construct the
exact Voronoi diagram inside an orthogonal polyhedron with holes defined by
such polyhedra. Our approach avoids creating full-dimensional elements on the
Voronoi diagram and yields a skeletal representation of the input object. We
introduce a complete algorithm in 2D and 3D that follows the subdivision
paradigm relying on a bounding-volume hierarchy; this is an original approach
to the problem. The complexity is adaptive and comparable to that of previous
methods. Under a mild assumption it is $O(n / \Delta + 1 / \Delta^2)$ in 2D or
$O(n\alpha^2 / \Delta^2 +1 / \Delta^3)$ in 3D, where $n$ is the number of
sites, namely edges or facets resp., $\Delta$ is the maximum cell size for the
subdivision to stop, and $\alpha$ bounds vertex cardinality per facet. We also
provide a numerically stable, open-source implementation in Julia, illustrating
the practical nature of our algorithm.
