On the bit complexity of minimum link paths
Simon Kahan, Jack Scott Snoeyink · 1996
All of the linear-time algorithms that have been developed for minimum-link paths use the real RAM model of computation.If one considers bit complexity, however, merely representing a minimum-link path may require a superquadratic 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 links 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 @(log N). 1 stance in which representing path vertices with rational