Given a set of $n$ points on which a triangulation is performed, it is possible to construct coefficients $\lambda_{ij}>0$ such that each point $x_i$ is a convex combination of the points connected to it. Suppose $N(i)$ is a set of points adjacent to $x_i$ in a triangulation; then, for each $x_i$,
$$\sum_{j\in N(i)} \lambda_{ij}x_j = x_i $$
and
$$\sum_{j\in N(i)} \lambda_j = 1.$$
In matrix form,
$$\Lambda x=x$$
where $\Lambda$ is a square, $n\times n$, row stochastic matrix (non-negative entries, and no self-loops).
Now suppose matrix $\Lambda$ is given. My questions are:
Can one reach configuration $x$ by the power method, i.e., by repeatedly multiplying $\Lambda$ by a vector? The "dominant" eigenvector is $1_n$, so one would have to orthogonalize against it to the "second dominant". I am asking because the above matrix form reminds me of the definition of eigenvalue/eigenvector.
If not, what would be a good approach to compute such a configuration? Is the solution unique?
I think that configuration $x$ is the solution to the problem of finding minimum of
$$ \sum_{(i,j) \in E} (x_i - x_j)^2, $$
where $E$ is the set of the edges of the triangulation. However, here one should compute the eigenvectors associated with the smallest eigenvalues. To establish the relation, I used the relation between the Laplacian and the adjacency matrix, as in the following paper.
- Yehuda Koren, On Spectral Graph Drawing [PDF].
One more interesting question:
- Can the coefficients $\lambda_{ij}$ be constructed in such a way that $\lambda_{ij} = \lambda_{ji}$, meaning that the matrix $\Lambda$ is symmetric? This way of constructing coefficients means that the power method should converge to $x$.