Bezdek, Andras On optimal route planning evading cubes in the three space. (English) Zbl 1015.90079 Beitr. Algebra Geom. 40, No. 1, 79-87 (1999). 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”. Reviewer: Johann Linhart (Salzburg) Cited in 1 Document MSC: 90C35 Programming involving graphs or networks 52A15 Convex sets in \(3\) dimensions (including convex surfaces) 52A40 Inequalities and extremum problems involving convexity in convex geometry Keywords:route planning; navigation; shortest paths; obstacles PDFBibTeX XMLCite \textit{A. Bezdek}, Beitr. Algebra Geom. 40, No. 1, 79--87 (1999; Zbl 1015.90079) Full Text: EuDML EMIS