**Beiträge zur Algebra und Geometrie / Contributions to Algebra and GeometryVol. 40, No. 1, pp. 79-87 (1999)
**

#
On Optimal Route Planning Evading Cubes in the Three Space

##
Andras Bezdek

Mathematical Institute of the Hungarian Academy of Sciences, Budapest, and Department of Mathematics, Auburn University, AL, USA e-mail: bezdean@mallard.duc.auburn.edu

**Abstract:** Let $\cal P$ be a finite arrangement of non-overlapping open cubes with side-lengths not exceeding $1$ in the $3$-dimensional Euclidean space. Let $S$ and $T$ be two points lying outside the open cubes. Assume one needs to find a short path emanating from $S$ and terminating at $T$ avoiding the cubes of $\cal P$ under the restriction that the cubes are not known prior to the search. In fact the positions and the side-lengths of the cubes become known to the searcher as the cubes are contacted. We give an algorithm to construct a path of length less than ${3\over 2}d+3\sqrt3\log d+5$, where $d>3\sqrt3$ denotes the distance between $S$ and $T$.

**Classification (MSC91):** 51N05

**Full text of the article:**

[Previous Article] [Next Article] [Contents of this Number]