Papers
The Double Order Scaled Approximation (DOSA), rev. 1
This is a companion paper proving scaled integer edge weights can be used as in Thorup’s algorithm
for SSSP to retrieve shortest paths in two-dimensional obstacle maps in grid-space. The proof extends to
n-dimensional spaces over the integers. Before getting started, we need to cover some ground covered in my
paper (pending publication; see below) regarding digital curvature and pathfinding.
Fast, Exact Digital Curvature Detection
My article submitted to Computational Geometry: Theory and Applications titled “Fast Exact Convex and Concave Curvature in Digital Images with an Application in Path-finding [Pre-print PDF] (coauthored with my adviser, Dr. Winncy Du) is now pending publication.
This article describes in good detail the algorithm I wrote a couple months ago when I discovered a simple method for finding digitally convex end-points in TASPA. Do not hesitate to comment with questions; it would be good to know if I and those who’ve proof read missed something.
Thanks go to Kate, Alex, Dr. Taylor, and Dr. Teoh for their support.
Oct-22-2009 Addendum — Runtime of all-pairs shortest paths on integer edge weights using Thorup’s algorithm is written in the caption to Figure 6 as O(n^2) and should be O(n^2 + nm).