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: