Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0999.65008
Nievergelt, Yves
A finite algorithm to fit geometrically all midrange lines, circles, planes, spheres, hyperplanes, and hyperspheres. (English)
[J] Numer. Math. 91, No.2, 257-303 (2002). ISSN 0029-599X; ISSN 0945-3245/e

Sind im euklidischen Raum $\bbfR^n$ endlich viele Punkte $\vec x_1,\dots,\vec x_N$ gegeben, so entsteht das Problem, eine Ausgleichshypersphäre mit Mittelpunkt $\vec c\in\bbfR^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\le k\le N}|\rho_k|$.\par 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.\par 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.
[O.Giering (München)]

MSC 2000:: *65D10 Smoothing
65D17 Computer aided design (modeling of curves and surfaces)
65Y20 Complexity and performance of numerical algorithms

Keywords: fitting hyperspheres; fitting hyperplanes; algorithm; computational complexity; numerical examples

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]