What's the relationship between 1D, 2D dynamic programming and Livewire?

What's the relationship between 1D, 2D dynamic programming and Livewire?

by Yiyuan Fang -
Number of replies: 1

Hello, 

I am wondering what's the relationship between 1D Dynamic Programming and 2D dynamic programming  (dijkstra's algorithm of shortest path), and live wire? My current understanding is that live wire can be implemented using either 1D or Dijkstra's. 1D has a time complexity of O(NQ^2)? Is this correct? 

In what situation should I use 1D to implement Live Wire, and in what situation should I use dijkstra's? Is it because it's faster? 

Thank you! 

In reply to Yiyuan Fang

Re: What's the relationship between 1D, 2D dynamic programming and Livewire?

by Andrey Davydov -

Here are we mention several terms:
LiveWire - name of the tool for interactive delineation, the whole topic in those slides is about LiveWire if you wish. Dynamic Programming - the very common approach to solve optimization problems when the data has some sequential structure, as in our case.
Dijkstra algorithm -one of the most efficient methods to find the shortest path in the graph. 

While in lecture it is explained in top-down strategy, from very common to practical, let me explain from the end.
We want to solve Live Wire problem: user gives two pixels, we need to find the "best" path. We define what is best for us: it is the path along the pixels with the highest gradient (it represents the contour). So we reduced our practical Live Wire problem to a shortest-path-search problem, which can be solved efficiently with Dijkstra. In turn, Dijkstra algorithm's core is dynamic programming: finding the best path using additional pixel using the best path without this pixel.