On the bit complexity of minimum link paths: Superquadratic algorithms forproblem solvable in linear time

All of the linear-time algorithms that have been developed for minimum-link paths use the real RAM model of computation. Lf one considers bit complexi ty, however, merely representing a minimum-link path may require a superqua dratic number of bits. This paper considers bounds on the number of Links ( segments) needed by limited-precision approximations of minimum-link paths: When vertices are restricted to "first-derived" points, the number of link s can increase by a constant factor; when they are restricted to points of an N x N grid, the number of links can increase by Theta (log N). (C) 1999 Published by Elsevier Science B.V. All rights reserved.