Regular grid graphs and complexes can be used to approximate geometric
surface functionals. Standard combinatorial algorithms for max-flow/min-cut problems
such as augmenting paths, push-relabel, pseudo-flow, and parametric max-flow techniques
can efficiently compute (in low-order polynomial time) global optima solutions for
the corresponding approximations of geometric problems widely used in computer vision,
graphics, and medical imaging. We review a range of applications
and discuss some computational issues (what geometric functionals can be approximated on graphs,
metrication errors, global optimization vs. local optimization, running-time and memory
efficiency).
Copyright. All Rights Reserved.