Determining the Principal Directions of a Point Set in the Plane and in Space

Source abstract

Introduction . The problem of determining the principal directions of a point set in the plane or in space is solved numerically. The task is to determine the orientation of an extremal line passing through the centroid of the set and minimizing or maximizing the functional defined as the sum of the squared distances from all points of the set to the line. This problem is relevant as an auxiliary component of many tasks involving intelligent systems. Materials and Methods . For a point set in the plane, the principal-direction problem is solved explicitly for two polar angles specifying the directions of the extremal lines corresponding to the maximum and minimum of the error functional. If the denominator in the resulting formula degenerates because the points are arranged symmetrically, changing one coordinate of a single point by 10⁻¹⁴ is sufficient to break the symmetry, make the formula applicable, and obtain a doubleprecision result. For a point set in three-dimensional space, the problem is reduced to a numerical iterative algorithm based on gradient descent with respect to the orientation angles of a line passing through the centroid of the set. A minimal compact C++ implementation for determining the principal directions in the three-dimensional case is proposed. Results . For a spatial point set, an explicit expression is obtained for the error functional and for the components of its gradient in the azimuthal and polar directions of a spherical coordinate system. An empirical formula for the gradient step is obtained as a function of the number of iterations, enabling a double-precision numerical solution with a relatively small number of iterations. It is shown that 100 iterations are sufficient to determine the extremal angles even when the initial orientation differs from the final orientation by π/2 for each angle. Discussion . The principal-direction problems for point sets in the plane and in space are solved numerically with double precision. Two test examples confirm double-precision accuracy for cases with the largest deviation between the initial and final line orientations. Both the explicit formulas for the two-dimensional problem and the formulas of the threedimensional iterative algorithm involve only coefficients represented by homogeneous second-order sums that depend on the point coordinates. There are three such coefficients in the two-dimensional case and six in the three-dimensional case. Conclusions . Despite its algorithmic simplicity, the gradient descent method yields well-defined iterative formulas for any initial and intermediate orientation of a line passing through the centroid of a point set in space. The explicit formulas obtained for the principal directions of a point set in the plane and the gradient-descent formulas for the three-dimensional case can be used in analysis problems involving intelligent systems and neural networks.