Algorithms for Grey-Weighted Distance Computations
This work offers incremental improvements for researchers and practitioners needing efficient distance computations in interactive applications with large datasets.
The paper compared popular algorithms for computing grey-weighted distance transforms to provide practical guidelines, finding that label-setting algorithms performed best across all scenarios and identifying optimal priority queues based on memory constraints.
With the increasing size of datasets and demand for real time response for interactive applications, improving runtime for algorithms with excessive computational requirements has become increasingly important. Many different algorithms combining efficient priority queues with various helper structures have been proposed for computing grey-weighted distance transforms. Here we compare the performance of popular competitive algorithms in different scenarios to form practical guidelines easy to adopt. The label-setting category of algorithms is shown to be the best choice for all scenarios. The hierarchical heap with a pointer array to keep track of nodes on the heap is shown to be the best choice as priority queue. However, if memory is a critical issue, then the best choice is the Dial priority queue for integer valued costs and the Untidy priority queue for real valued costs.