On optimal route planning evading cubes in the three space (Q1591716)

Consider a finite set of non-overlapping open cubes with side-lengths \(\leq 1\) in Euclidean \(3\)-space, and let \(S\) and \(T\) be two points lying outside the cubes. The author studies the problem of finding a short path from \(S\) to \(T\) avoiding the cubes under the restriction that the cubes are not known prior to the search. He presents an algorithm to construct such a path of length less than \(\frac{3}{2}d+3\sqrt{3}\log d+5\), where \(d>3\sqrt{3}\) denotes the distance between \(S\) and \(T\). The factor \(\frac{3}{2}\) is best possible. The algorithm uses the strategy ``evade a cube and go straight towards the target''.