# What was Gauss's algorithmic method to solve a certain "nearest neighbour search" problem in multi-dimensional euclidean space?

In his 1829 paper on a new formulation of mechanics, Gauss presented his principle of least constraint, which parallels previous formulations of analytical mechanics and provides a new point of view about them. However, in his very short paper he discussed only holonomic constraints; constraints of motion represented by equations rather than inequalities.

In the last years of his life, Gauss attempted to extend his principle to non-holonomic constraints, and we can learn from August Ritter's notebooks (Ritter was a pupil of Gauss) that in Gauss's 1850/51 lectures he discussed the following problem of computational geometry:

A region of space in a euclidean space $$E^n$$ is specified by linear equations and inequalities. Find its shortest distance from a given point in space.

In modern terms Gauss discussed a "Nearest Neighbour Search" (NNS) problem with the metric being the usual euclidean metric. This problem might look easy in low number of dimensions and constraints, but the "naive" ways to find the shortest distance become computationally inefficient as the number of dimensions and constraints grows up, since the "hyper-polyhedra" that bounds the region can become quite complicated.

It seems that Gauss discovered a more algorithmically efficient way of approaching this problem (similar to more modern algorithms). I am interested in obtaining more information about Gauss's method. Either a direct explanation or some pointers to relevant literature would be much appreciated.

It is perhaps worth mentioning that Gauss mainly gave this problem as an examplary problem, and his original motivations/ideas might be deeper. It is also worth mentioning that Ritter wrote his 1853 doctoral thesis "On Gauss's principle of least constraint", which dealt with applications to non-holonomic constraints, under the close supervision of Gauss (unfortunately I did not find his doctoral thesis on web).

The sources which I based this question on are p. 469-481 of volume 10-1 of Gauss's werke, as well as Paul Stackel's 1917 article "Remarks on the principle of least constraint" (which can be found in p.421-436 of this collection of translations). Unfortunately, the website of Gottingen digital library no longer enables to make immediate translation of text, so I could not read an English translation of the relevant pages of Gauss's werke.

• Stäckel's paper where he "thoroughly presented the process that he [Gauss] suggested for finding the location of the minimum" and "proposed another way of treating it" is available in pdf on the web, Eine von Gauss gestellte Aufgabe des Minimums. Perhaps you can use Google Docs to translate it. Commented Nov 8, 2022 at 7:49