A minimal surface criterion and its linearized version (Dirichlet criterion) for graph partitioning
Updated 7 Nov 2016

View License

We consider a geometric approach to graph partitioning based on the graph Beltrami energy, a discrete version of a functional that appears in classical minimal surface problems. More specifically, the optimality criterion is given by the sum of the minimal Beltrami energies of the partition components. We adapt primal-dual convex optimization methods to solve for the minimal Beltrami energy for each component of a given partition. A rearrangement algorithm is proposed to find the graph partition to minimize a relaxed version of the objective.
We also provide efficient code to solve the much faster, linearized minimal surface criterion instead (Dirichlet energy).

The toolbox includes a simple five-moons test data set (dbmoon.mat) and example code to reproduce the five-moons example.

The code is immediately based on the following two papers (to referred to as documentation and to be cited as reference):

[1] Dominique Zosso, Braxton Osting, "A minimal surface criterion for graph partitioning", Inverse Problems and Imaging 10(4):1149-1180, 2016.

and its linearized, faster version :

[2] Dominique Zosso, Braxton Osting, Stanley J. Osher, "A Dirichlet Energy Criterion for Graph-Based Image Segmentation", 2015 IEEE ICDM Workshop.

Cite As

Dominique Zosso (2024). MinimalSurfacePartitioning (, MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2016a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes