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:

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]