An <i>r</i>-Dimensional Quadratic Placement Algorithm

The solution to the problem of placing n connected points (or nodes) in r-dimensional Euclidean space is given and it is proved that the problem reduces to the minimization of a sum or r positive semi-definite quadratic forms which, under the quad ratic constraints, reduces to a problem of finding r eigenvectors of a special "disconnection" matrix.

Abstract

In this paper the solution to the problem of placing n connected points (or nodes) in r-dimensional Euclidean space is given. The criterion for optimality is minimizing a weighted sum of squared distances between the points subject to quadratic constraints of the form X′X = 1, for each of the r unknown coordinate vectors. It is proved that the problem reduces to the minimization of a sum or r positive semi-definite quadratic forms which, under the quadratic constraints, reduces to the problem of finding r eigenvectors of a special “disconnection” matrix. It is shown, by example, how this can serve as a basis for cluster identification.