Computer Vision Topics

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.

DOSA, rev. 1

Tags: digital curvature, integers, pathfinding, proof