A finite algorithm to fit geometrically all midrange lines, circles, planes, spheres, hyperplanes, and hyperspheres
type: Item
instance of: scholarly article
title: A finite algorithm to fit geometrically all midrange lines, circles, planes, spheres, hyperplanes, and hyperspheres
zbMATH Open document ID: 0999.65008
author: Yves Nievergelt
published in: Numerische Mathematik
publication date: 2002-06-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65D10
Mathematics Subject Classification ID: 65D17
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 1756838
zbMATH Keywords: fitting hyperspheres
zbMATH Keywords: fitting hyperplanes
zbMATH Keywords: algorithm
zbMATH Keywords: computational complexity
zbMATH Keywords: numerical examples
reviewed by: Oswald Giering
describes a project that uses: mctoolbox
MaRDI profile type: Publication
full work available at URL: s002110100326
OpenAlex ID: W2010202760
DOI: 10.1007/S002110100326
description: scientific article; zbMATH DE number 1756838