I have come across this term Riemannian graph especially after looking into a paper Surface reconstruction from unorganized points by Hoppe et al. (See Section 3.3 - Consistent Tangent Plane Orientation.)

See also this slide from Princeton University.

It says that the construction of the Riemannian graph is done by adding edges between k-neighbouring vertices to the Euclidean Minimimum Spanning Tree (EMST).

My questions are the following:

  1. What is the exact definition of Riemannian graph?
  2. Why it is required to build the graph from the EMST as, after all, the Riemannian graph when built directly from the k-neighbours will still contain the EMST, right?


After reading more carefully, it seems that the Riemannian graph does not contain all the $k-$neighbouring edges if

the following line as in the paper

we add the $\mathrm{edge}(i,j)$ if either $o_i$ is in the $k-$neighborhood of $o_j$, or $o_j$ is in the $k-$neighborhood of $o_i$

means that

we do not add an $\mathrm{edge}(i,j)$ if both $o_i$ is in the $k-$neighbourhood of $o_j$ and $o_j$ is in the $k-$neighbourhood of $o_i$.

Could anyone confirm the above statement?


1 Answer 1


The full paper is available here: http://hhoppe.com/recon.pdf

After browsing it, I believe the answers to your questions are as follows:

  1. There is no particular definition of the Riemannian graph. It is a graph which broadly connects points that are close together, and it is weighted with a non-Euclidean distance function. Perhaps it reminded the authors of the metric tensor of a Riemannian manifold, possibly explaining the name, but in any case its primary purpose is just to extract from it the minimum spanning tree.

  2. This question seems to harbor two separate misconceptions: a) that the Riemannian graph necessarily contains the EMST (related to the comment in the update), and b) that there is no reason to construct the graph if it already contains the EMST.

a) It is not true that a $k$-NN graph always contains the minimum spanning tree, even for large $k$. Consider a point set consisting of two equally-large clusters of points separated by a large gap. The minimum spanning tree must cross this gap somewhere, but that edge is not contained in the $k$-NN graph for any $k$ less than half the number of vertices (and that is an extremely large value of $k$ for most applications).

However, the Riemannian graph is explicitly built as a supergraph of the EMST, by adding edges (it's the superposition of the EMST and the $k$-NN graph). So by definition it always contains the EMST. And no, the speculation in your update is wrong — the "or" is not to be construed as an exclusive or. You are probably just grasping at straws because you haven't understood the resolution of b), that the final spanning tree is not supposed to resemble the EMST.

b) There is a very good reason to shift to the Riemannian graph from the EMST: it has a very different (highly non-Euclidean) distance function, therefore its MST (with respect to that distance) is deliberately different from the EMST. The EMST favors points that are physically closest to each other, but as mentioned in the paper, a flattened, pointy shape like a cat's ear contains points that are close together yet have very different orientations. In the presence of noise this will result in some flipped normal vectors.

By contrast, the Riemannian graph strikes a crude sort of balance between physical proximity and compatibility of normals. So the intention is that the algorithm would be more likely to, starting from the front of the cat's ear, traverse down to the smoother parts of the cat, and then come up along the back side of the ear, resulting in consistent normal directions.

  • $\begingroup$ Correct! I was stuck with my implicit assumption that a spanning tree (and may be, the EMST) is always contained in the $k-$neighbour graph which is indeed false. $\endgroup$
    – ffslq
    Jan 17, 2017 at 8:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .