Data Graph Formulation as the Minimum-Weight Maximum-Entropy Problem

Consider a point-set coming from an object which was sampled using a digital sensor (depth range, camera, etc). We are interested in finding a graph that would represent that point-set according to some properties. Such a representation would allow us to match two objects (graphs) by exploiting topological properties instead of solely relying on geometrical properties. The Delaunay triangulation is a common out off-the-shelf strategy to triangulate a point-set and it is used by many researchers as the standard way to create the so called data-graph and despite its positive properties, there are also some drawbacks. We are interested in generating a graph with the following properties: the graph is (i) as unique as possible, (ii) and as discriminative as possible regarding the degree distribution. We pose a combinatorial optimization problem (Min-Weight Max-Entropy Problem) to build such a graph by minimizing the total weight cost of the edges and at the same time maximizing the entropy of the degree distribution. Our optimization approach is based on Dynamic Programming (DP) and yields a polynomial time algorithm.