×

On optimal route planning evading cubes in the three space. (English) Zbl 1015.90079

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”.

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
PDFBibTeX XMLCite
Full Text: EuDML EMIS