A finite algorithm to fit geometrically all midrange lines, circles, planes, spheres, hyperplanes, and hyperspheres (Q1601094)

Sind im euklidischen Raum \(\mathbb{R}^n\) endlich viele Punkte \(\vec x_1,\dots,\vec x_N\) gegeben, so entsteht das Problem, eine Ausgleichshypersphäre mit Mittelpunkt \(\vec c\in\mathbb{R}^n\) und Radius \(r\) (oder eine Ausgleichshyperebene) zu bestimmen. Die historische Entwicklung dieses Problems wird zunächst ausführlich dargestellt. Sie zeigt, dass zahlreiche Autoren versuchen, ``den'' Mittelpunkt \(\vec c\) und Radius \(r\) so zu finden, dass \(\sum^N_{k=1} \rho^2_k\) mit \(\rho_k:= \|\vec x_k-\vec c\|- r\) (unter Verwendung der euklidischen Norm \(\|\dots\|\)) minimiert wird. Im Gegensatz dazu minimiert die vom Autor entwickelte Methode die Maximum-Norm \(f_\infty(\vec c,r):= \|(\rho_1,\dots, \rho_N)\|_\infty= \max_{1\leq k\leq N}|\rho_k|\). Es wird ein Algorithmus vorgestellt, der mit endlich vielen arithmetischen Operationen alle endlich vielen globalen Minima von \(f_\infty\) berechnet. Der Algorithmus findet zu einer Ausgleichshypersphäre die dünnste konzentrische Hypersphärenschale sowie zu einer Ausgleichshyperebene die dünnste durch zwei Hyperebenen begrenzte Scheibe, die die vorgegebenen Punkte \(\vec x_1,\dots,\vec x_N\) enthält. Die Existenz von Lösungen wird zuvor ausführlich diskutiert. Die Berechnungskomplexität wird sowohl für dünnste Schalen als auch für dünnste Scheiben ermittelt. Die Empfindlichkeit gegenüber Störungen der Ausgangsdaten wird ebenfalls untersucht. Die sehr fundiert abgefasste Arbeit endet mit Tests and Anwendungen.