### Technical Report No. 63, December 1994 - Abstract

**Amitava Datta, Kamala Krithivasan, Thomas Ottmann:**

*An Optimal Algorithm for One-separation of a Set of Isothetic Polygons, With Extensions to Higher Dimensions*

We consider the problem of separating a collection of isothetic polygons in
the plane by translating one polygon at a time to infinity. The directions
of translation are the four isothetic (parallel to the axes) directions,
but a particular polygon can be translated only in one of these four directions.
Our algorithm detects whether a scene is separable in this sense and computes
a translational ordering of the polygons. The time and space complexities of
our algorithm is *O(n*log n)* and *O(n)* respectively, where *n* is the total
number of vertices of the polygons in the scene. Our algorithm is optimal
with respect
to both time and space. The best previous algorithm in the plane for
this problem had complexities of *O(n*log^2(n))* time and
*O(n*log n)* space.
We also present extensions of our algorithm to higher dimensions. The time
and space complexities of our algorithm in three dimensions are
*O(n*sqrt(n)*log n)* and *O(n*sqrt(n)*log n)*
respectively. In a dimension
*d >= 4*, the time and space complexities are *O(d*n^{d/2}*log n)* and
*O(d*n^{d/2}*log n)*, respectively. The time complexities of our algorithm
in a dimension *d > 2* improve the previous best complexities for this
problem
by a factor of *O(log^2(n))*.

report63.ps.gz