We can also store the vertex to vertex connectivity matrix $M$ and use matrix multiplication to find all the neighbors of a given vertex that are $N$ away form the matrix $M^{N}$.
If you are amazingly ambitious, you can diagonalize $M$ once (This might be a bit hard when $M$ is large) and from then onwards compute $M^{N}$ with only 2 matrix multiplication operations and $V$ exponentiation operations, where $V$ is the number of vertices in the mesh.
dvernet
I don't see why finding neighbors would be $\mathcal{O}(1)$. For a given edge row in the Vertex <-> Edge matrix, don't we have to iterate over $\mathcal{O}(V)$ entries in the matrix to see which vertices are at either end of an edge (and are thus neighbors)?
BryceSummers
If we use a sophisticated scheme such as sparse matrices, we will only need to store the two vertex indexes associated with each edge.
In fact, a sparse matrix for Vertex - Edge degenerates into a list of edge pairs.
A spares matrix for edge-face degenerates into a list of face triplets.
We can also store the vertex to vertex connectivity matrix $M$ and use matrix multiplication to find all the neighbors of a given vertex that are $N$ away form the matrix $M^{N}$.
If you are amazingly ambitious, you can diagonalize $M$ once (This might be a bit hard when $M$ is large) and from then onwards compute $M^{N}$ with only 2 matrix multiplication operations and $V$ exponentiation operations, where $V$ is the number of vertices in the mesh.
I don't see why finding neighbors would be $\mathcal{O}(1)$. For a given edge row in the Vertex <-> Edge matrix, don't we have to iterate over $\mathcal{O}(V)$ entries in the matrix to see which vertices are at either end of an edge (and are thus neighbors)?
If we use a sophisticated scheme such as sparse matrices, we will only need to store the two vertex indexes associated with each edge.
In fact, a sparse matrix for Vertex - Edge degenerates into a list of edge pairs. A spares matrix for edge-face degenerates into a list of face triplets.