Triangulated Graphs of Cortical Surfaces
In this page we summarize the application of dynamic programming to triangulated graph representations of cortical surfaces.
Dynamic programming on the triangulated graph relies on the fact that curves passing through a point on the graph must pass through one of its neighbors. This allows the refining of the state space (where the state space is defined as N(k) with N being the positions of the nodes of the graph) at each step, thereby reducing complexity.
The goal is to compute the optimal shortest path between the specified initial states s and the final state t. Assuming that the optimal path has no more than k nodes.
Basic Theorem
If the optimal path goes through cell (a,b), then the optimal path is the combination of the optimal path from cell (1,1) to cell (N,M).
Thus:
- Not the optimal path to cell (a,b) is relevant, but the cost associated with the optimal path up to (a,b).
- The cost of the optimal path up to cell (a,b) can be computed as the minimum of the sum of all its possible predecessors with accumulated local distortion.
By applying these principles recursively, the dynamic programming problem can be reduced to a problem with linear complexity O(N^2).
