Kreisberechnung um 5 Punkte

[Achim Meyer]

Hallo zusammen,
ich hatte vor 2 Monaten schonmal das Thema "Kreisberechnung mit 3
Punkten" gestartet. Allen Beteidigten erstmal herzlichen Dank! Hat
Prima geklappt.
Jetzt stehe ich vor dem Problem, das ganze für 5 Punkte zu machen:
Also, ich habe 5 gegebene Punkte A(x,y), B(x,y).....und möchte um
diese Punkte herum den kleinstmöglichen Kreis haben. Gesucht ist
Radius und Mittelpunkt.
Mit 3 Punkten ging das ja eigendlich ganz einfach. Bei 5en hab ich
noch nicht mal einen Lösungsansatz.
Das ganze soll hinterher wieder auf Excel laufen. Also mit Zirkel und
Lineal ist mir nicht sehr geholfen.

Vielen Dank schonmal für eure Mühe,

Achim

[Thomas Mautsch]

Post by Achim Meyer
ich hatte vor 2 Monaten schonmal das Thema "Kreisberechnung mit 3
Punkten" gestartet. Allen Beteidigten erstmal herzlichen Dank! Hat
Prima geklappt.
Also, ich habe 5 gegebene Punkte A(x,y), B(x,y).....und möchte um
diese Punkte herum den kleinstmöglichen Kreis haben. Gesucht ist
Radius und Mittelpunkt.
Mit 3 Punkten ging das ja eigendlich ganz einfach. Bei 5en hab ich
noch nicht mal einen Lösungsansatz.
Das ganze soll hinterher wieder auf Excel laufen. Also mit Zirkel und
Lineal ist mir nicht sehr geholfen.

Google doch mal nach "smallest enclosing circle". -
Zur Loesung brauchst Du Voronoi-Diagramme:

http://www.algorithmic-solutions.info/leda_guide/geo_algs/extremal_circles.html
http://www.algorithmic-solutions.info/leda_guide/geo_algs/voronoi.html

[Konrad Fischer]

Post by Thomas Mautsch
Google doch mal nach "smallest enclosing circle". -
http://www.algorithmic-solutions.info/leda_guide/geo_algs/extremal_circles.html
http://www.algorithmic-solutions.info/leda_guide/geo_algs/voronoi.html

Oha, da ist mein Beitrag dann wohl guten Gewissens zu ignorieren :)
Für Reply-Mails bitte ein "n" aus der Adresse streichen.

[Hero]

Achim
"Also mit Zirkel und
Lineal ist mir nicht sehr geholfen. "
Es reizt natürlich doch (Excel kann warten).
Mein Vorschlag:
Um den Mittelpunkt der laengsten
Verbindungslinie einen Kreis durch
die beiden Endpunkte.
Liegen Punkte ausserhalb hilft Thales.
Sprich: betrachte von den Punkten ausserhalb
diese laengste Strecke. Der Punkt, von dem
aus sie unter dem kleinsten Winkel
erscheint ist dann der dritte Punkt, neben
den beiden Endpunkten der laegnsten Strecke,
der den Kreis bestimmt.
Ist dies der kleinste Kreis, in dem alle Punkte
liegen oder geht's kleiner ?
Gruss
Hero

[Thomas Mautsch]

Post by Hero
Achim

Post by Hero
"Also mit Zirkel und
Lineal ist mir nicht sehr geholfen. "

Es reizt natürlich doch (Excel kann warten).
Um den Mittelpunkt der laengsten
Verbindungslinie einen Kreis durch
die beiden Endpunkte.
Liegen Punkte ausserhalb hilft Thales.
Sprich: betrachte von den Punkten ausserhalb
diese laengste Strecke. Der Punkt, von dem
aus sie unter dem kleinsten Winkel
erscheint ist dann der dritte Punkt, neben
den beiden Endpunkten der laegnsten Strecke,
der den Kreis bestimmt.
Ist dies der kleinste Kreis, in dem alle Punkte
liegen oder geht's kleiner ?

Wenn alle Punkte in diesem Kreis liegen,
ist es der kleinste Kreis.

Wenn alle Punkte auf einer Seite der laengsten Verbindungsstrecke
zwischen zwei Punkten liegen, funktioniert Deine Konstruktion.

Falls nicht, bekommst Du Probleme:
Nimm als Gegenbeispiel vier Eckpunkte eines konvexen
Drachenvierecks ABCD, in dem die Achse AC
die laengste der sechs Verbindungen bildet.
Sobald die Innenwinkel bei B und D spitz werden,
wird der Punkt D *ausserhalb* des Umkreises von ABC liegen.

Wenn die Konstruktion des kleinsten einschliessenden Kreises
so einfach waere, wuerde sich sicherlich niemand Gedanken
darueber machen, seitenlange Abhandlungen darueber zu schreiben.

Uebrigens ist man bei solchen Konstruktionen immer gut damit
beraten, einen Blick in die F.A.Q. von comp.graphics.algorithms
zu werfen:
http://www.geometrictools.com/CgaFaq.pdf

Kleinste umschriebene Kreise und Kugeln werden
im Abschnitt 1.5 behandelt
(mit Hinweis auf einen Algorithmus von Emo Welzl, ETH Zuerich).

[Hero]

Schade,
ich sehe, daß meine "Lösung" falsch ist.
Danke für die Korrektur und
auch die Links.
Dir braucht man das nicht zu sagen,
es ist ja auch trivial, doch habe ich
als erste Annaeherung an den kleinsten
Kreis:
ein Kreis um den Mittelpunkt der
laengsten Verbindung mit einem Durchmesser
von (sqrt 3) * Laenge der laengsten Verbindung
enthaelt alle Punkte.
Gruesse
Hero

[Achim Meyer]

Post by Hero
Achim
"Also mit Zirkel und
Lineal ist mir nicht sehr geholfen. "
Es reizt nat=FCrlich doch (Excel kann warten).
Um den Mittelpunkt der laengsten
Verbindungslinie einen Kreis durch
die beiden Endpunkte.
Liegen Punkte ausserhalb hilft Thales.
Sprich: betrachte von den Punkten ausserhalb
diese laengste Strecke. Der Punkt, von dem
aus sie unter dem kleinsten Winkel
erscheint ist dann der dritte Punkt, neben
den beiden Endpunkten der laegnsten Strecke,
der den Kreis bestimmt.
Ist dies der kleinste Kreis, in dem alle Punkte
liegen oder geht's kleiner ?
Gruss
Hero

Das hört sich ziemlich sinnvoll an. Erste Versuche bestätigen das.
Herzlichen Dank für die Hilfe!

Gruss,

Achim

[Thomas Mautsch]

Post by Achim Meyer

Post by Hero
Achim

Post by Hero
"Also mit Zirkel und
Lineal ist mir nicht sehr geholfen. "

Um den Mittelpunkt der laengsten
Verbindungslinie einen Kreis durch
die beiden Endpunkte.
Liegen Punkte ausserhalb hilft Thales.
Sprich: betrachte von den Punkten ausserhalb
diese laengste Strecke. Der Punkt, von dem
aus sie unter dem kleinsten Winkel
erscheint ist dann der dritte Punkt, neben
den beiden Endpunkten der laegnsten Strecke,
der den Kreis bestimmt.
Ist dies der kleinste Kreis, in dem alle Punkte
liegen oder geht's kleiner ?

Das hört sich ziemlich sinnvoll an. Erste Versuche bestätigen das.
Herzlichen Dank für die Hilfe!

Dann kann ich nur hoffen,
dass nicht das Leben oder Wohl anderer Menschen davon abhaengt,
dass auch wirklich *alle* Punkte in dem
von Deinem Programm berechneten Kreis liegen.
:-I

[Konrad Fischer]

On 9 Mar 2005 08:58:25 -0800, achim-***@web.de (Achim Meyer) wrote:

(Vielleicht nicht ganz hilfreicher) Schnellschuss:

Es gibt genau 10=5*4/2 verschiedene Möglichkeiten durch zwei von fünf
Punkten einen Kreis zu zeichnen. Diese müssten dann natürlich auf
entgegengesetzten Punkten des Kreises liegen. Mindestens einer von
ihnen enthält alle fünf Punkte, nur ob es der kleinstmöglichste ist ?

Wie gesagt, dies war nur ein erster Gedanke. Ich hoffe niemand fühlt
sich durch diese eventuelle Vergeudung von Bandbreite auf den Schlips
getreten.

Gruß Konrad
Für Reply-Mails bitte ein "n" aus der Adresse streichen.

[¿?]

"Achim Meyer" <achim-***@web.de> escribi� en el mensaje news:***@posting.google.com...
~ Hallo zusammen,
~ ich hatte vor 2 Monaten schonmal das Thema "Kreisberechnung mit 3
~ Punkten" gestartet. Allen Beteidigten erstmal herzlichen Dank! Hat
~ Prima geklappt.
~ Jetzt stehe ich vor dem Problem, das ganze für 5 Punkte zu machen:
~ Also, ich habe 5 gegebene Punkte A(x,y), B(x,y).....und möchte um
~ diese Punkte herum den kleinstmöglichen Kreis haben. Gesucht ist
~ Radius und Mittelpunkt.
~ Mit 3 Punkten ging das ja eigendlich ganz einfach. Bei 5en hab ich
~ noch nicht mal einen Lösungsansatz.
~ Das ganze soll hinterher wieder auf Excel laufen. Also mit Zirkel und
~ Lineal ist mir nicht sehr geholfen.
~
~ Vielen Dank schonmal für eure Mühe,
~
~ Achim

Für mich ist die einfachste Lösung, mit den 5 Punkten
die position des "Zentroids" [~ Schwerpunkt, sorry, kenn'
den richtigen Deutchen Ausdruck nicht] zu berechnen. Dann
ist der kleinste Kreis der mit mittelpunkt den "Zentroid"
und Radius der grösste Abstand vom "Zentroid" zu jedem Punkt.

[Thomas Mautsch]

[ ... ]

Post by ¿?
~ Also, ich habe 5 gegebene Punkte A(x,y), B(x,y).....und möchte um
~ diese Punkte herum den kleinstmöglichen Kreis haben. Gesucht ist
~ Radius und Mittelpunkt.
Für mich ist die einfachste Lösung, mit den 5 Punkten
die position des "Zentroids" [~ Schwerpunkt, sorry, kenn'
den richtigen Deutchen Ausdruck nicht] zu berechnen. Dann
ist der kleinste Kreis der mit mittelpunkt den "Zentroid"
und Radius der grösste Abstand vom "Zentroid" zu jedem Punkt.

Diese Methode liefert einen fast doppelt so grossen Radius wie noetig,
wenn sich viele Punkte an einer Stelle auf dem Rand
des eigentlich minimalen Kreises haeufen,
waehrend wenige andere Punkte weit davon entfernt liegen.

Waehle z.B. 5 Punkte auf einer Geraden,
vier davon nah beieinander, der restliche Punkt weit entfernt. -
Der Radius des kleinstmoeglichen Kreises ist in diesem Fall
gleich der Haelfte des maximalen Abstandes zwischen den Punkten.
Deine Methode liefert einen wesentlich groesseren Radius.


Vielleicht verwechselst Du das Problem ja mit der Frage,
zu gegebenen Punkten einen Kreis zu finden,
so dass die Summe der Quadrate der Abstaende
von den Punkten zur Kreislinie minimal wird. -
Fuer diese Frage ist der Schwerpunkt der Punkte
eine gute *Naeherung* fuer den Mittelpunkt des gesuchten Kreises...

[Gottfried Helms]

Post by Thomas Mautsch
Diese Methode liefert einen fast doppelt so grossen Radius wie noetig,
wenn sich viele Punkte an einer Stelle auf dem Rand
des eigentlich minimalen Kreises haeufen,
waehrend wenige andere Punkte weit davon entfernt liegen.
Waehle z.B. 5 Punkte auf einer Geraden,
vier davon nah beieinander, der restliche Punkt weit entfernt. -
Der Radius des kleinstmoeglichen Kreises ist in diesem Fall
gleich der Haelfte des maximalen Abstandes zwischen den Punkten.
Deine Methode liefert einen wesentlich groesseren Radius.

Hi -

ich habe mal einen iterativen Ansatz versucht mit Translationen
und Rotationen. Ich starte immer mit der Translation des Mittelpunktes
zum Koordinatenursprung.
Mit verschiedenen darauffolgenden Rotations- und Translationsmethoden
komme ich auf verschiedene Optima; möglicherweise birgt ja der eine
oder andere Ansatz eine gute Lösung?

Hier habe ich mal iterationsprotokolle dokumentiert. Zunächst für
einfache Fälle mit 3 Punkten.
Die Radlist zeigt die erreichten optimalen Radii an: sie hat für jede
Methode eine Spalte und jede Iteration eine Zeile.

Weiter unten Beispiele mit 5 Punkten. Komischerweise konvergieren die
Methoden alle schneller wenn ich 5 Punkte nehme. Woran kann das liegen?

Findet jemand bessere Lösungen als die hier jeweils beste? Die 2., 6. und
8. te streiten sich um den ersten Platz...

Gruß -

Gottfried

;===========================================
;MatMate-Listing vom:12.03.05 01:14:48
;============================================
k :
x y
--------------------------
| 4.00 1.00 |
| 1.00 4.00 |
| -2.00 -1.00 |

radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 3.54 3.11 3.06 3.06 3.09 2.76 3.54 3.32 |
| 3.79 2.93 3.06 3.06 3.09 2.76 3.62 3.11 |
| 3.53 2.92 3.06 3.06 3.09 2.76 3.59 2.87 |
| 3.64 2.91 3.06 3.06 3.09 2.76 3.61 2.87 |
| 3.57 2.91 3.06 3.06 3.09 2.76 3.59 2.87 |
| 3.64 2.91 3.06 3.06 3.09 2.76 3.61 2.87 |

k :
x y
--------------------------
| 1.00 2.00 |
| 4.00 3.00 |
| 2.00 -1.00 |

radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 2.45 1.58 2.24 2.24 2.24 1.60 2.42 1.59 |
| 2.25 1.58 2.24 2.24 2.24 1.58 2.24 1.58 |
| 2.37 1.58 2.24 2.24 2.24 1.58 2.37 1.58 |
| 2.24 1.58 2.24 2.24 2.24 1.58 2.24 1.58 |
| 2.37 1.58 2.24 2.24 2.24 1.58 2.37 1.58 |
| 2.24 1.58 2.24 2.24 2.24 1.58 2.24 1.58 |

k :
x y
--------------------------
| 1.00 2.00 |
| 1.00 2.00 |
| 2.00 -1.00 |

radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 1.58 1.12 1.58 1.58 1.58 1.12 1.50 1.50 |
| 1.58 1.12 1.58 1.58 1.58 1.12 1.50 1.50 |
| 1.58 1.12 1.58 1.58 1.58 1.12 1.50 1.50 |
| 1.58 1.12 1.58 1.58 1.58 1.12 1.50 1.50 |
| 1.58 1.12 1.58 1.58 1.58 1.12 1.50 1.50 |
| 1.58 1.12 1.58 1.58 1.58 1.12 1.50 1.50 |

k :
x y
--------------------------
| 4.00 1.00 |
| 1.00 4.00 |
| -2.00 -1.00 |

radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 3.54 3.11 3.06 3.06 3.09 2.76 3.54 3.32 |
| 3.79 2.93 3.06 3.06 3.09 2.76 3.62 3.11 |
| 3.53 2.92 3.06 3.06 3.09 2.76 3.59 2.87 |
| 3.64 2.91 3.06 3.06 3.09 2.76 3.61 2.87 |
| 3.57 2.91 3.06 3.06 3.09 2.76 3.59 2.87 |
| 3.64 2.91 3.06 3.06 3.09 2.76 3.61 2.87 |


5 Punkte : ===================================================

k :
x y
--------------------------
| 9.00 6.00 |
| 6.00 9.00 |
| 3.00 4.00 |
| 1.00 8.00 |
| 7.00 4.00 |

radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 4.10 3.20 4.12 4.12 4.12 3.24 4.09 3.26 |
| 4.10 3.20 4.12 4.12 4.12 3.24 4.09 3.26 |
| 4.10 3.20 4.12 4.12 4.12 3.24 4.09 3.26 |
| 4.10 3.20 4.12 4.12 4.12 3.24 4.09 3.26 |
| 4.10 3.20 4.12 4.12 4.12 3.24 4.09 3.26 |
| 4.10 3.20 4.12 4.12 4.12 3.24 4.09 3.26 |

k :
x y
--------------------------
| 4.00 1.00 |
| 1.00 4.00 |
| -2.00 -1.00 |
| -4.00 3.00 |
| 2.00 -1.00 |

radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 4.10 3.20 4.12 4.12 4.12 3.24 4.09 3.26 |
| 4.10 3.20 4.12 4.12 4.12 3.24 4.09 3.26 |
| 4.10 3.20 4.12 4.12 4.12 3.24 4.09 3.26 |
| 4.10 3.20 4.12 4.12 4.12 3.24 4.09 3.26 |
| 4.10 3.20 4.12 4.12 4.12 3.24 4.09 3.26 |
| 4.10 3.20 4.12 4.12 4.12 3.24 4.09 3.26 |


k :
x y
--------------------------
| 4.00 1.00 |
| 5.00 2.00 |
| 4.00 4.00 |
| 3.00 7.00 |
| 2.00 -1.00 |

radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 4.06 2.90 4.02 4.02 4.03 3.18 3.04 3.04 |
| 4.04 2.90 4.02 4.02 4.03 3.18 3.04 3.04 |
| 4.03 2.90 4.02 4.02 4.03 3.18 3.04 3.04 |
| 4.03 2.90 4.02 4.02 4.03 3.18 3.04 3.04 |
| 4.03 2.90 4.02 4.02 4.03 3.18 3.04 3.04 |
| 4.03 2.90 4.02 4.02 4.03 3.18 3.04 3.04 |
| 4.03 2.90 4.02 4.02 4.03 3.18 3.04 3.04 |

========================================================

[Gottfried Helms]

Am 12.03.05 01:41 schrieb Gottfried Helms:

*@#! Die geposteten Tabellen zeigen nicht die Radii, sondern die
halben Seitenlängen der kleinsten einschließenden Quadrate.
Wahr wohl schon etwas spät gestern abend..

Hier sind die Radius-Tabellen. Sie zeigen keinen durchgängigen Favoriten mehr...

Gottfried Helms



k :
x y
--------------------------
| 4.00 1.00 |
| 1.00 4.00 |
| -2.00 -1.00 |

radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 3.55 3.81 3.70 3.70 3.71 3.87 3.76 3.76 |
| 3.85 3.57 3.70 3.70 3.71 3.87 3.70 3.70 |
| 3.58 3.57 3.70 3.70 3.71 3.87 3.54 3.54 |
| 3.76 3.57 3.70 3.70 3.71 3.87 3.56 3.56 |
| 3.63 3.57 3.70 3.70 3.71 3.87 3.57 3.57 |
| 3.75 3.57 3.70 3.70 3.71 3.87 3.57 3.57 |
| 3.63 3.57 3.70 3.70 3.71 3.87 3.57 3.57 |



k :
x y
--------------------------
| 1.00 2.00 |
| 4.00 3.00 |
| 2.00 -1.00 |

radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 2.52 2.24 2.50 2.50 2.50 2.24 2.25 2.25 |
| 2.25 2.24 2.50 2.50 2.50 2.24 2.24 2.24 |
| 2.50 2.24 2.50 2.50 2.50 2.24 2.24 2.24 |
| 2.24 2.24 2.50 2.50 2.50 2.24 2.24 2.24 |
| 2.50 2.24 2.50 2.50 2.50 2.24 2.24 2.24 |
| 2.24 2.24 2.50 2.50 2.50 2.24 2.24 2.24 |




k :
x y
--------------------------
| 1.00 2.00 |
| 1.00 2.00 |
| 2.00 -1.00 |

radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 1.58 1.58 1.58 1.58 1.58 1.58 1.58 1.58 |
| 1.58 1.58 1.58 1.58 1.58 1.58 1.58 1.58 |
| 1.58 1.58 1.58 1.58 1.58 1.58 1.58 1.58 |
| 1.58 1.58 1.58 1.58 1.58 1.58 1.58 1.58 |
| 1.58 1.58 1.58 1.58 1.58 1.58 1.58 1.58 |




k :
x y
--------------------------
| 4.00 1.00 |
| 1.00 4.00 |
| -2.00 -1.00 |
| -4.00 3.00 |
| 2.00 -1.00 |


radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 4.23 4.44 4.17 4.17 4.17 4.29 4.46 4.46 |
| 4.23 4.44 4.17 4.17 4.17 4.29 4.46 4.46 |
| 4.23 4.44 4.17 4.17 4.17 4.29 4.46 4.46 |
| 4.23 4.44 4.17 4.17 4.17 4.29 4.46 4.46 |
| 4.23 4.44 4.17 4.17 4.17 4.29 4.46 4.46 |




k : // nur Translation des vorigen Modells
x y
--------------------------
| 9.00 6.00 |
| 6.00 9.00 |
| 3.00 4.00 |
| 1.00 8.00 |
| 7.00 4.00 |

radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 4.23 4.44 4.17 4.17 4.17 4.29 4.46 4.46 |
| 4.23 4.44 4.17 4.17 4.17 4.29 4.46 4.46 |
| 4.23 4.44 4.17 4.17 4.17 4.29 4.46 4.46 |
| 4.23 4.44 4.17 4.17 4.17 4.29 4.46 4.46 |




k :
x y
--------------------------
| 4.00 1.00 |
| 5.00 2.00 |
| 4.00 4.00 |
| 3.00 7.00 |
| 2.00 -1.00 |

radlist :
Meth1 Meth2 Meth3 Meth4 Meth5 Meth6 Meth7 Meth8
------------------------------------------------------------------------------------
| 4.24 4.03 4.26 4.26 4.26 4.03 4.03 4.03 |
| 4.24 4.03 4.26 4.26 4.26 4.03 4.03 4.03 |
| 4.24 4.03 4.26 4.26 4.26 4.03 4.03 4.03 |
| 4.24 4.03 4.26 4.26 4.26 4.03 4.03 4.03 |
| 4.24 4.03 4.26 4.26 4.26 4.03 4.03 4.03 |

[Hero]

Hei Gottfried,
ich hab mir mal Deine Zahlen
vorgenommen.
Wie schon frueher gesagt, man sucht die
laengste Verbidnungslinie mit Mittelpunkt
D und Länge d. Dann liegen alle Punkte
sicher im Kreis um D mit Radius d/sqrt 3.
Andererseits muss der Kreis midestens
den Radius d/2 haben, egal wo
der Mittelpunkt ist.
Das dritte Beispiel von Dir hat zwei
identische Punkte, Loesung klar.
Die erste Beispiel hat d=2* sqrt 10
und das zweite d=2* sqrt 5. In beiden
Beispielen ist man dann mit einem
Kreis um den Mittelpunkt der laengsten
Strecke schon fertig.
Die anderen Beispiele habe ich mir noch
nicht angeschaut.
Verständnisfrage.
Translation und Rotation klar,
aber in Deinen Listen bedeutet doch
jede Spalte von oben nach untern auch
Schrumpfen, oder ?
(Zusammengenommen das Verhalten
eines "Schrumpfschlauches" , den man
über ein Kabelbündel zieht und dann
erhitzt).
Gruss
Hero

[Hero]

Das Auge des Clusters:
Schneide die beiden Kreise um die
Endpunkte der laengsten Strecke d
mit Radius d, dann erhaelt man eine
Form wie eine optische Linse.
Zeichne um den Mittelpunkt D von d
einen Kreis mit Radius d/2.
Falls Punkte ausserhalb dieses Kreises
liegen, suche den entferntesten C davon, und
zeichne innerhalb der Linsenform
einen Kreis( bzw zwei Kreisbögen) mit
Radius DC um D.
Das ganze sieht jetzt aus wie ein
Auge, gedreht.
Der innere Kreis, die Pupille, hat den kleinsten Radius.
Alle Punkte des gegebenen Punkthaufens (Cluster)
liegen im Bereich Pupille + Iris.
Viel Spass
Hero

[Gottfried Helms]

Post by Hero
Schneide die beiden Kreise um die
Endpunkte der laengsten Strecke d
mit Radius d, dann erhaelt man eine
Form wie eine optische Linse.
Zeichne um den Mittelpunkt D von d
einen Kreis mit Radius d/2.
Falls Punkte ausserhalb dieses Kreises
liegen, suche den entferntesten C davon, und
zeichne innerhalb der Linsenform
einen Kreis( bzw zwei Kreisbögen) mit
Radius DC um D.
Das ganze sieht jetzt aus wie ein
Auge, gedreht.
Der innere Kreis, die Pupille, hat den kleinsten Radius.
Alle Punkte des gegebenen Punkthaufens (Cluster)
liegen im Bereich Pupille + Iris.
Viel Spass
Hero

Hallo Hero -


Hmm, so ähnlich hatte ich es mir auch gedacht.

Infrage kommen ja im Prinzip nur translationen,
wobei man schnell findet, daß die Translation des
Zentroids auf den Koordinatenursprung nicht unbedingt
die beste Lösung liefert, wie Du das ja schon angemerkt
hast.
Ich habe mir deswegen überlegt, ob es eine Folge von
solchen Translationen gibt, die meinetwegen mit der
Zentroid-Verschiebung anfangen mag und dann sukzessive
verbessert wird. Denn im Endeffekt kann ja der Mittelpunkt
des besten Kreises im Koordinatenursprung festgelegt
werden und ist durch Translationen erreichbar.

Ich nehme jetzt nicht die Zentroid-Translation, sondern
ich bestimme die beiden längsten Distanzen sowhl in X- als
auch in Y-Richtung und nehme den Mittelpunkt der beteiligten
Punkte (maximal 4) als neuen Koordinatenursprung.

Wenn man zunächst solch eine Mitten-Translation durchführt,
kann man dann das resultierende Punktesystem so rotieren,
daß bspw die längste Differenz zwischen zwei Punkten
parallel zur x-Achse erscheint. In einem günstigen Fall
liegen dann einige Punkte oberhalb und einige Punkte
unterhalb dieser Parallele. Der Kreisdurchmesser wird
durch diese längste Distanz bestimmt, wenn alle anderen
Distanzen genügend kleine y-Koordinaten haben.
Ich mache eine neue Mitten-Translation und rotiere neu
nach meinem gewählten Rotationskriterium.

Die Hoffnung ist, daß dieses Verfahren - bei geeignetem
Rotationskriterium - zum optimalen Mittelpunkt führt.
Allerdings wei0 ich nicht, ob das überhaupt stimmt... :-)

Es hat so Ähnlichkeiten mit Deinem Linsen/Pupillen/Iris
Beispiel, weil der errechnete Umkreisradius zu einem
-anscheinend leider methodenspezifischen- Minimum konvergiert.

Gottfried Helms

[Hero]

Gottfried,
ich hoffe, ich hab's begriffen.
Du schrumpfst gar nicht irgendeinen Kreis.
Du verschiebst und drehst, wie Du ja auch
schreibst.
Aber konvergiert Dein Verfahren nicht dahin,
dass zum Schluss der Mittelpunkt der
laegsten Strecke im Ursprung liegt ?
Gruss
Hero

[Hero]

Noch eine Frage.
Du erreichst doch ein eigentlich
ein Rechteck, in dem alle
Punkte liegen.
Was ist das Kriterium von einem Schritt
zum nächsten, sagen wir mal in x-Richtung
wird es kleiner, aber in y-Richtung
groesser?
Gruss
Hero

[Gottfried Helms]

Hallo Hero -

Post by Hero
Noch eine Frage.
Du erreichst doch ein eigentlich
ein Rechteck, in dem alle
Punkte liegen.

Tja, ich fürchte auch, daß es dabei bleibt. Allerdings
wird es wohl ein Quadrat.

Post by Hero
Was ist das Kriterium von einem Schritt
zum nächsten, sagen wir mal in x-Richtung
wird es kleiner, aber in y-Richtung
groesser?

Ich probiere ja mehrere Kriterien parallel, die allerdings
alle eigentlich nicht auf dieses Problem zugeschnitten
sind. Deshalb die Vergleichsliste.
Eines dieser Kriterien, das (bei der Rechteck/Quadrat-
Tabelle allerdings) abgeschnitten hat, ist, die Punkte
mit den größten vorhandenen Abstände zur X- bzw der
Y-Achse zu rotieren.

Das dreht dann denn ganzen Punkteschwarm entsprechend.
Nun habe ich möglicherweise eine sehr große positive
Y-Koordinate, aber nur eine absolut kleinere negative.
Ich schiebe dann so "nach unten", daß der Mittelpunkt
zwischen diesen beiden Koordinaten in den Ursprung kommt
(unter Verwendung des gleichen Kriteriums für die X-
Koordinaten).

Mal sehen, ob das in ASCII geht:


-->Rotation--> --->Translation--->

*
|
* | | *|
| * | |
| * | * |
--------+-------- --------+-------- --------+--------
* | * | * | *
| |* |
| | |
*

Ich habe dann zwei gegensätzliche Y-Koordinaten und zwei etwa
gegensätzliche X-Koordinaten. Abs(Y_max) und abs(Y_min) sind
dann gleich, und der Radius des kleinsten Kreises muß dann
das Minimum der absoluten X-abweichungen und absoluten Y-
Abweichungen sein. (So jedenfalls mein Gedanke ;-) )

Die vorhandenen Rotationskriterien, die ich anwende, verwenden
allerdings keine punktindividuellen Maximierungen (insbesondere
keine absoluten Werte, sondern Quadrierungen oder Potenzen von 4),
sondern ähnlich wie die Hauptachsenrotation die Maximierung (oder
Minimierung) eines Kriteriums über *alle* Punkte gemeinsam. Also
enthalten sie in etwa leider auch das von Dir bereits angemerkte
Zentroid-Problem.

Gruß -

Gottfried Helms

[Hero]

Bisher hat Thomas alle Fehler gefunden
und angemerkt (nicht ich).
Schoenen Dank Thomas.

Gottfried, Helmut hat ja eine exakte Loesung
gefunden - zum Beweis kann man
uebrigens auch Deine Translationen
und Rotationen nehmen, so nach dem
Motto, "jetzt geht der Kreis durch zwei Punkte,
kann ich ihn noch bewegen und auch schrumpfen?".

Aber damit bist Du ( sind wir) noch nicht arbeitslos,
denn so ab 6,7 Punkten ausserhalb des
kleinen Kreises um die laengste Strecke
wird der Aufwand der Pruefung leicht quadratisch.
Also für grosse Punktmengen koennte auch eine
Naeherungsloesung interessant sein, und vielleicht
kommt ja sogar eine exakte Loesung heraus.
(Und eigentlich hast Du ja eine neue Aufgabenstellung
praesentiert: Finde das kleinste Rechteck fuer
einen Bienenschwarm (den kleinsten Fotoausschnitt
einer Punktwolke).
Erst mal noch eine Anmerkung:
Bei der Kreisloesung koennen durchaus
beide Endpunkte der laegsten Strecke
innerhalb des Kreises und nicht auf dem
Rand liegen.
Viel Spass
Hero

[Helmut Richter]

n Punkte in der Ebene, kleinster einschließender Kreis.

Der Kreis ist immer eindeutig und zwar entweder

- der Umkreis eines spitzwinkligen Dreiecks aus dreien der Punkte oder

- ein Kreis, von dem die Verbindungsstrecke zweier der Punkte ein
Durchmesser ist.

Damit hat man nur endlich viele Möglichkeiten der Lösung.

Ich würde mit zwei Punkten anfangen und dem Mittelpunkt zwischen ihnen
als Kreismittelpunkt und dem halben Abstand als Radius anfangen. Von
da an:

Schritt 1: Bestimme ein Dreieck aus dem Kreis.

- Hat man einen Kreis über einer Strecke (so wie am Anfang) und es
liegen nicht alle Punkte im Inneren, nimmt den am weitesten vom
Mittelpunkt entfernten als dritten Punkt zu den beiden Endpunkten
der Strecke hinzu.

- Hat man einen Umkreis um ein spitzwinkliges Dreieck und es liegen
nicht alle Punkte im Inneren, nimmt den am weitesten vom Mittelpunkt
entfernten als dritten Punkt zu den beiden von ihm weiter entfernten
Ecken des Dreiecks hinzu.

Schritt 2: Bestimme einen Kreis aus dem Dreieck:

- Ist das Dreieck spitzwinklig, so nimmt man seinen Umkreis.

- Ist das Dreieck stumpfwinklig, so nimmt man den Kreis, der die
längste Seite als Durchmesser hat.

- (Ist es rechtwinklig, kommt in beiden Fällen derselbe Kreis heraus.)

Zurück zu Schritt 1.

Sollte rasch den kleinsten Kreis ergeben, the proof is left to the
reader.

Helmut Richter

[Helmut Richter]

Post by Helmut Richter
- Hat man einen Kreis über einer Strecke (so wie am Anfang) und es
liegen nicht alle Punkte im Inneren, nimmt den am weitesten vom
Mittelpunkt entfernten als dritten Punkt zu den beiden Endpunkten
der Strecke hinzu.
- Hat man einen Umkreis um ein spitzwinkliges Dreieck und es liegen
nicht alle Punkte im Inneren, nimmt den am weitesten vom Mittelpunkt
entfernten als dritten Punkt zu den beiden von ihm weiter entfernten
Ecken des Dreiecks hinzu.

Wahrscheinlich ist es völlig wurscht, in welcher Reihenfolge man die
Punkte berücksichtigt, und "den am weitesten vom Mittelpunkt
entfernten" kann man einfach ignorieren. Stattdessen "einen außerhalb
des Kreises gelegenen". Damit steht der vom OP geforderten
Programmierung in einem Excel-Blatt auch nichts mehr im Wege, selbst
für beliebig viele Punkte. Würde mich jetzt reizen, aber ich habe echt
was Wichtigeres zu tun.

Helmut Richter

[Hero]

Das ist clever, Helmut.
Ich kann Deine Lösung nur bestaetigen, ich
habe sie mir auch bewiesen.
Und - es ist eine exakte Loesung, keine
Annaeherung!
Einzige Anmerkung:
Du schreibst:
"Schritt 2: Bestimme einen Kreis aus dem Dreieck:
- Ist das Dreieck spitzwinklig, so nimmt man seinen Umkreis.
- Ist das Dreieck stumpfwinklig, so nimmt man den Kreis, der die
längste Seite als Durchmesser hat.
- (Ist es rechtwinklig, kommt in beiden Fällen derselbe Kreis heraus.)
"
Da oder wenn man im allerersten Schritt die laengste
Verbindung gefunden hat, und wenn dann noch ein
oder mehrere Punkte ausserhalb des ersten Kreises gefunden
werden, kann man sich im folgenden (hier)
auf spitzwinklige Dreiecke beschraenken.
Herzlichen Glückwunsch und hoffentlich gibt
das Schwung bei der anderen Arbeit.
Viel Spaß
Hero

[Helmut Richter]

Post by Helmut Richter
Wahrscheinlich ist es völlig wurscht, in welcher Reihenfolge man die
Punkte berücksichtigt, und "den am weitesten vom Mittelpunkt
entfernten" kann man einfach ignorieren. Stattdessen "einen außerhalb
des Kreises gelegenen".

Präziser ausgedrückt: Um einen weiteren Punkt hinzuzunehmen, braucht man
nur die zwei oder drei Stützstellen des bisherigen Kreises zu kennen,
nicht aber alle bisherigen Punkte. Und wenn man es so präzisiert, sieht
man auch, dass es falsch ist. Gegenbeispiel:

A = <-4, 3>
B = <4, 3>
C = <0, -5>
D = <0, 4>
E = <0, -14>

Der engste Kreis um A, B, C, D geht um den Ursprung mit dem Radius 5;
der engste um A, B, C, D, E geht um C mit dem Radius 9. Nimmt man also E
zu den anderen vier Punkten dazu, muss man sich an den Punkt D erinnern,
der wieder auf den Rand gerät, obwohl er bis jetzt unauffällig in der
Mitte lag.

Man muss also doch beweisen, dass so ein Fall nicht auftreten kann, wenn
man die Punkte in der Reihenfolge hernimmt, die ich im ersten Beitrag
beschrieb.

Helmut Richter

[Hero]

Jetzt klingt das so, als waere da keine exakte
Loesung, aber hier noch mal Deine Loesung
(mit etwas Majo von mir):

"n Punkte in der Ebene, kleinster einschließender Kreis.
Der Kreis ist immer eindeutig und zwar entweder
- der Umkreis eines spitzwinkligen Dreiecks aus dreien der Punkte oder
- ein Kreis, von dem die Verbindungsstrecke zweier der Punkte ein
Durchmesser ist.
Damit hat man nur endlich viele Möglichkeiten der Lösung.
Ich würde mit zwei Punkten anfangen und dem Mittelpunkt zwischen ihnen

als Kreismittelpunkt und dem halben Abstand als Radius anfangen."

Ich wähle die zwei Endpunkte der laengsten Verbindungsstrecke.

"Von da an:
Schritt 1: Bestimme ein Dreieck aus dem Kreis. "
1A
"- Hat man einen Kreis über einer Strecke (so wie am Anfang) und es
liegen nicht alle Punkte im Inneren, nimmt den am weitesten vom
Mittelpunkt entfernten als dritten Punkt zu den beiden Endpunkten
der Strecke hinzu."
Jetzt kommen nur noch Umkreise spitzwinkliger Dreiecke in
Betracht. Angenommen, man hätte ein stumpfwinkliges,
dann könnte man den Kreis verkleinern ,indem man
die längste Seite des Dreiecks als Kreisdurchmesser
nimmt. Da diese aber kürzer ist als die längste
Verbindung überhaupt, waere der Kreis zu klein
und die längste Verbindung überhaupt waere
nicht im Kreis.
1B
"- Hat man einen Umkreis um ein spitzwinkliges Dreieck und es liegen
nicht alle Punkte im Inneren, nimmt den am weitesten vom Mittelpunkt
entfernten als dritten Punkt zu den beiden von ihm weiter entfernten
Ecken des Dreiecks hinzu.
Schritt 2: Bestimme einen Kreis aus dem Dreieck:
- Ist das Dreieck spitzwinklig, so nimmt man seinen Umkreis."
("- Ist das Dreieck stumpfwinklig, so nimmt man den Kreis, der die
längste Seite als Durchmesser hat.
- (Ist es rechtwinklig, kommt in beiden Fällen derselbe Kreis
heraus.)" )
Klammer überfluessig.
"Zurück zu Schritt 1." (1B)

Interessant wird es, wenn Du Deinen Punkten
die Punkte
F=( -5,3)
G=(5,3)
und H=( -9.5, -4.735)
Aber auch hier kommt man zu einer exakten Loesung
oder Thomas ?
Schoenen Sonnentag
Hero

[Helmut Richter]

Post by Hero
Jetzt klingt das so, als waere da keine exakte
Loesung, aber hier noch mal Deine Loesung

Vermutung ohne Beweis: Wenn man mit der längsten Strecke anfängt und
weitermacht wie ursprünglich beschrieben, nämlich immer den abgelegensten
Punkt als nächsten dazunimmt, gehts. Das liefert eine exakte Lösung in
endlich vielen Schritten.

In meinem letzten Beitrag ergänzt: Wenn man irgendwo anfängt und jeweils
einen *beliebigen* Punkt dazunimmt, muss es nicht gehen. Im Beispiel ist
der Punkt E zu spät dazugenommen worden.

Post by Hero
Ich wähle die zwei Endpunkte der laengsten Verbindungsstrecke.

Zusatzfrage: wie findet man diese zwei Punkte mit geringem Aufwand?

Post by Hero
Schoenen Sonnentag

Eben deswegen höre ich jetzt auf, bevor mich wieder die Sucht packt.

Helmut Richter

[Hero]

Helmut,
traust Du Deiner eigenen Logik nicht ?
Deine Behauptung stimmt schon, es gibt
eine exakte Loesung in endlich vielen Schritten.

Hier noch mal fuer Achim fuer sein Excel:
Finde die laengste Verbindungsstrecke und
zeichne einen Kreis so, dass sie den
Durchmesser bildet. Falls dann noch Punkte
auussserhalb sind, musst - sozusagen vor vorne
angefangen - den Umkreis von je drei Punkten
aus der Menge aller Punkte mit dem groessten Radius
finden.Dann liegen alle Punkte in diesem Kreis
bzw. auf seinem Rand und er kann nicht kleiner.

Die laengste Verbidnungsstrecke finde ich immer
durch Aufmalen und manchmal ein bisschen Rechnen.
Mit Computer bildet man die Differenzen aller
Koordinatenpaare, quadriert die beiden Komponenten
und addiert sie.
(A=(3,-4) B=(-2,-5) folgt A-B=(5,1) folgt 25+1=26)
All diese Zahlen bilden so eine untere Dreiecksmatrix.
Und früher gab's mal Bubblesort, heute gibt es
sicher bessere Sortierungsalgorithmen (nach Groesse).

Helmut,
wenn Du Dir den Sonntag nicht verderben willst,
darfst Du aber nicht die weiteren Beitraege lesen.
Viel Spass
Hero

[Helmut Richter]

Post by Hero
Helmut,
traust Du Deiner eigenen Logik nicht ?
Deine Behauptung stimmt schon, es gibt
eine exakte Loesung in endlich vielen Schritten.

Ja, schon, aber Punkte, die man schon mal hatte, können einem entwischen.
Macht nichts, man fängt sie wieder ein.

Post by Hero
wenn Du Dir den Sonntag nicht verderben willst,
darfst Du aber nicht die weiteren Beitraege lesen.

Ich bin spazieren gegangen, und ich weiß jetzt genauer, wo die Beweislücke
ist. Ich habe keinen Zweifel, dass man (sogar ich) sie schließen kann,
aber es ist nicht so einfach, wie ich dachte.

Helmut Richter

[Hero]

Gottfried, genau.
Punkte, die man schon hatte, rutschen wieder raus.
Bei Deinem Verfahren mit der Rotation schwebt mir
so ein Foto der Circumpolarsterne mit einer
Belichtungszeit von ein paar Stunden vor.
Der Trick ist nun, dass Deine Methoden erst
nach der laengsten Verbindungslinie suchen muessen.
Hat man damit alle eingefangen, ist man ja fertig.
Sonst muß ein neues Kriterium sein, den Mittelpunkt
von drei (oder mehr) Punkten mit gleichem Abstand
vom Mittelpunkt zu finden.
Helmut,
ich sehe keine Beweisluecke, dass eine exakte
Loesung in endlich vielen Schritten erreicht werden kann.
Es muesste fuer viele Punkte nur noch etwas effinzienter.
Das mit wachsendem Radius ist schon gut.
Vielleicht noch irgendetwas mit laegster Strecke
aller Punkte, die ausserhalb des ersten Kreises
(der ja um die ueberhaupt laengste Seite geht)?
Oder was mit: auf gegenueberliegenden Seiten
der laengsten Strecke liegend?
Mal sehen.
Schau Dir noch mal die Punktmenge A bis E und
nimm meine F,G,H hinzu, da hat man schon
einen gewissen Test, ob man keine Fehler
macht.
Gruss
Hero

[Helmut Richter]

Post by Hero
Der Trick ist nun, dass Deine Methoden erst
nach der laengsten Verbindungslinie suchen muessen.

Die längste Verbindungslinie hat nichts mit dem engsten Kreis zu tun.
Beispiel:

A = <-209, 0> B = <209, 0>
C = <-240, 120> D = <240, 120>
E = <0, 361> M = <0, 120>

Die längste Verbindungslinie ist zwischen C und D mit der Länge 480. Sie
geht durch M, den Mittelpunkt des Kreises durch A, B und E mit dem Radius 241.
D.h. weder C noch D liegen auf dem engsten Kreis um alle Punkte.

Post by Hero
ich sehe keine Beweisluecke, dass eine exakte
Loesung in endlich vielen Schritten erreicht werden kann.

Ich habe hineingesteckt, dass der engste Kreis um die Punkte einer
endlichen Menge M gleichzeitig engster Kreis einer höchstens
dreielementigen Teilmenge von M ist. Das glaube ich nach wie vor, aber der
einfache Beweis "man nehme einfach immer einen Punkt dazu und zeige alles
durch Induktion nach der Anzahl der Punkte" haut nicht hin, wenn einem
Punkte unterwegs verlorengehen, die man wieder einfangen muss. Der
Induktionsschritt wäre jetzt:

Sei M eine endliche Punktmenge und P ein Punkt außerhalb des engsten
Kreises um M. Dann gibt es entweder Q in M oder Q1 und Q2 in M, so dass
der engste Kreis um {P, Q} bzw. um {P, Q1, Q2} alle Punkte von M
einschließt. Trivial ist es nicht, weil die neuen Kreise flacher sind, so
dass Punkte herausfallen können. Anschaulich klar ist durchaus, dass, wenn
man sich auf das Einfangen der am weitesten entfernten Punkte von M
konzentriert, man auch die anderen, dazwischenliegenden Pukte von M wieder
erwischt. Aber "anschaulich klar" ist nun mal kein Beweis. Da war die
Lücke - äääh, das ist sie noch.

Helmut Richter

[Hero]

Wenn der Kreis um die laengste Strecke nicht
alle Punkte einfaengt, dann kann es keinen
kleinsten
Kreis geben, der nur durch zwei Punkte geht.
Entweder bildet die Verbindung dieser beiden Punkte
einen Durchmesser
( falsch, da dieser Kreis einen groesseren Durchmesser
als die Laenge der langsten Strecke hat)
oder die Verbindung dieser beiden Punkte bildet
eine Sehne (ungleich Durchmesser)
(dann kann man noch verkleinern, indem man
de Mittelpunkt noch an die Sehne heranschiebt).
Also 1. Abchecken nach längster Verbindung.
2 Wenn 1. nicht reicht, weil noch ein Punkt ausserhalb,
dann unter allen Punkten einen Umkreis um drei Punkten suchen.
Gruss
Hero

[Gottfried Helms]

Hallo Hero, hallo Horst -

die Lösung sieht ja nun praktikabel aus; trotzdem
will ich nochmal in meiner Konstruktionswelt bleiben und
ein Verfahren suchen, was so lange wie möglich kontiniuerlich
bleibt und am besten mit meinen vorhandenen Instrumenten
zu lösen geht. (Alternativ würde ich mir gerne überlegen,
ob die Aufgabe so grundsätzlich zu formulieren geht,
daß ich in meinen Programmbaukasten ein solches grund-
sätzliches Verfahren implementieren kann)

Die ALternative, die ich mir schon mal mit der früheren
Frage hier nach dem Einschließen von Punkten mit einer
*Ellipse* überlegt hatte, war die, mit einer zusätzlichen
Raumdimension zu arbeiten.

Wenn ich mir die x-y-Ebene als Grundebene einer Halbkugel
betrachte, und über den 5 (oder n) Punkten die Senkrechten
zum Rand der Halbkugel erreichte, bekomme ich auf der
Kugeloberfläche "Firmament"-Punkte, die vom Ursprung alle die
gleiche Entfernung r haben.

Das Translationskriterium für die Verschiebung der
Grund-Punkte in der x/y-Ebene zum Ursprung hin wäre
dann, eine Stelle zu finden, wo diese Firmamentpunkte
so angeordnet sind, daß
- entweder 2
- oder aber 3
(oder einfacher ausgedrückt - maximal viele)

dieselbe minimale Höhe haben.

Diese identische minimale Höhe dieser 2 oder 3 (oder maximal vieler)
Firmament-Punkte legt den Radius des minimalen Kreises, der alle
Punkte auf der Grundebene einschließt, eindeutig fest.

(Bei der Ellipsenfragestellung käme einfach noch die
spärische Rotation hinzu, könnte aber ansonsten gleich ge-
löst werden)

Im Moment sehe ich das - wenn man auf die "direkte" Methode
verzichtet, nur als Iteration möglich, als Translation mit
Nebenbedingungs-Optimierung.

Weiß auch nicht - irgendwie fasziniert mich diese Sichtweise
des Problems deutlich mehr ;-) Aber wir können die Sache
natürlich auch hier beenden, nachdem ein Algo im Prinzip
ja vorliegt. Wahrscheinlich läufts am Ende eh' auf die
gleichen oder sehr ähnliche Formeln hinaus...

Herzlich -

Gottfried

[Helmut Richter]

Post by Gottfried Helms
die Lösung sieht ja nun praktikabel aus; trotzdem
will ich nochmal in meiner Konstruktionswelt bleiben und
ein Verfahren suchen, was so lange wie möglich kontiniuerlich
bleibt und am besten mit meinen vorhandenen Instrumenten
zu lösen geht.

Die vorgeschlagene Lösung ist insofern diskoninuierlich, als nur die
vier Grundrechenarten für die Berechnung der Kreismittelpunkte
verwendet werden. D.h.: Sind alle Aufgangskoordinaten rational, so
auch die Koordinaten aller berechneten Kreismittelpunkte. Damit ist
dann auch die Entscheidung, ob ein Punkt innerhalb oder außerhalb
eines Kreises liegt, ohne Rundungsfehler zu bewerkstelligen. Das halte
ich für einen Vorteil gegenüber "kontinuierlichen" Methoden.

Helmut Richter

[Hero]

Die Suche nach einem Algorithmus ist durchaus
sinnvoll bei vielen Punkten, Gottfried.
Das Firmament hat was.
Der Algorithmus kann abbrechen, wenn
entweder 2 Punkte auf dem Aequator
(Hoehe Null) sich genau gegenueber liegen
oder mindestens drei Punkte auf dem
Aequator liegen
und natuerlich alle Punkte innerhalb
der Kugel sind.

Ich habe mir noch mal versucht, mir die
Algorithmen vorzustellen.
Nehmen wir mal als simpel Kriterium
Distanz in x-Richtung.
Anfangsstellung x max : +5 und -3
also verschieben (der Punkte) um
Eins nach links.
Drehen um 5 Grad (bei sehr vielen
Punkten kleinere Drehungen)
Jetzt x-max +4 und -3
Distanz ist kleiner, also nicht
verschieben
Drehen um 5 Grad
Distanz nicht kleiner, nicht verschieben
Drehen
Jetzt x-max +4 und - 4.5,
also verschieben um 0.25 nach rechts.
Habe ich das so begriffen, nur
verschieben, wenn Distanz groesser?
Jetzt ist die Frage nach den Kriterium.
Bei meinem simpel-Kriterium landet der
Mittelpunkt in der Mitte der laengsten
Verbindungsstrecke.
Jetzt zum Firmament
Grund stellung
Wie gross ist der Radius des ersten Halbkugel?
Halber Radius der x-Distanz (bzw wenn groesser
der y-Distanz)?
Gruss
Hero

[Gottfried Helms]

Hallo Hero, hallo Horst -

schade, de Grippe packt mich gerade, deshalb nur
kurz hierzu.

Post by Hero
Die Suche nach einem Algorithmus ist durchaus
sinnvoll bei vielen Punkten, Gottfried.
Das Firmament hat was.
Der Algorithmus kann abbrechen, wenn
entweder 2 Punkte auf dem Aequator
(Hoehe Null) sich genau gegenueber liegen
oder mindestens drei Punkte auf dem
Aequator liegen
und natuerlich alle Punkte innerhalb
der Kugel sind.

Ja - die Größe der Halbkugel kann bei dem ersten Schritt,
der Translation zum Zentroid, sofort mitbestimmt werden.
Ihr Durchmesser kann beliebig größer oder gleich der
maximalen Distanz werden. Man kann ihn auch 1 setzen
und alle Koordinaten standardisieren.

Post by Hero
Ich habe mir noch mal versucht, mir die
Algorithmen vorzustellen.
Nehmen wir mal als simpel Kriterium
Distanz in x-Richtung.
Anfangsstellung x max : +5 und -3
also verschieben (der Punkte) um
Eins nach links.
Drehen um 5 Grad (bei sehr vielen
Punkten kleinere Drehungen)
Jetzt x-max +4 und -3
Distanz ist kleiner, also nicht
verschieben
Drehen um 5 Grad
Distanz nicht kleiner, nicht verschieben
Drehen
Jetzt x-max +4 und - 4.5,
also verschieben um 0.25 nach rechts.
Habe ich das so begriffen, nur
verschieben, wenn Distanz groesser?

Ähm, warte mal... mal sehen - gleich.

Post by Hero
Jetzt ist die Frage nach den Kriterium.
Bei meinem simpel-Kriterium landet der
Mittelpunkt in der Mitte der laengsten
Verbindungsstrecke.

Ich habe aus dem Baukasten der Faktor-Analyse-Rotationen das
fertige Modul Quartimax-Rotation. Dies rotiert eine
Gruppe Punkte so, daß maximale Distanzen (als Koordinaten)
in Richtung der x- bzw der y-Achse ausgerichtet werden.
Allerdings ist dies ein gemeinsamer Kennwert *über alle*
Punkte, also nicht eine 2-Punkt-Optimierung, auf die es
hier aber im Endeffekt ankommt.
Eine Umdrehung des Quartimax-Kriteriums führt zu einer
Orientierung, bei der im Endeffekt die längsten Distanzen
entlang der Diagonale und die *kleinsten* Distanzen/Koordinaten
antlang der Achsen liegen ( damit kann man dem Problem
des kleinsten Rechtecks näher(!) kommen.)
Eine wiederholte Quartimax/negative Quartimax-Rotation abwechselnd
mit geeigneten Translationen sollte dann zum Ziel führen.
Das weiß ich aber nicht exakt, da es "lokale Minima" geben
könnte, die einen solchen Iterationsprozeß an der falschen
Stelle anhalten könnten.

Wenn man das Quartimax-Kriterium immer *nur für die 3 Punkte*
bestimmt, die die extremsten Koordinaten haben, könnte dies
hingegen zu einem globalen Maximum/Minimum führen.

Eine Kontrollrechnung hierfür habe ich entlang der
Idee, die Du oben ausgeführt hast, gestern mal programmiert,
und *das* scheint auch zu funktionieren: nach der
anfänglichen Zentrierung des Punkteschwarms werden
immer die drei Punkte gesucht, die die kleinsten Höhen haben,
und das Translationskriterium so berechnet, daß deren
Streuung (nur dieser 3 Punkte) minimal wird (also im besten Fall
alle gleich).
Konkret: die Punkte mit der kleinsten Höhe seien a,b,c,
dann werden Translationsschritte in x/y-Richtung solange
mit einer gewissen Schrittweite gemacht, wie die Streuung der
Höhen von a,b,c sich verkleinert.
Wächst sie wieder an, wird die Schrittweite halbiert und die
Richtung der Translationen umgedreht, solange, bis keine Änderung
mehr auftritt.
Genaugenommen wird die Richtung nicht genau um 180° umgedreht,
sondern mit einer Quartimax die Richtung so rotiert, daß
die längsten Distanzen /höchsten Koordinaten wiederum auf den Achsen
liegen, - und diese wird dann als neue Translationsrichtung
verwendet. Diese Änderungen der Translations-Richtung schießen
sich irgendwann auch auf 180°,180°,... ein und das ganze
Verfahren konvergiert. (... <ahem>. Muß man noch sehen).

Man sieht allerdings: nach der Begeisterung für die Eleganz
der Firmamentpunkte wird das dann womöglich schnell uninteressant,
da es unter Effizienzaspekten wahrscheinlich ein absoluter Overkill
wird, der durch den einfacheren Suchalgo um Längen geschlagen
wird. (Allerdings könnte sich das ja bei ein paar tausend Punkten
ändern ;-) ) Wie gesagt: mir ging es bei dem Verfolgen dieser
Idee auch darum, die Reichweite der vorhandenen Rotations-
Tools auszutesten / genauer zu verstehen. Wenn es reicht, würde ich
in mein kleines Statistikprogramm nur das Translationskonzept
hinzufügen, um solche Probleme *generell* lösen zu können.

Post by Hero
Jetzt ist die Frage nach den Kriterium.
Bei meinem simpel-Kriterium landet der
Mittelpunkt in der Mitte der laengsten
Verbindungsstrecke.
Jetzt zum Firmament
Grund stellung
Wie gross ist der Radius des ersten Halbkugel?
Halber Radius der x-Distanz (bzw wenn groesser
der y-Distanz)?

Jepp. Oder vielleicht etwas größer, um der anfänglich größten
Distanz nicht ein unwiederruflich großes Gewicht zu geben, was
dann vielleicht schenll in ein *lokales* Minimum führt.

Post by Hero
Gruss
Hero

.... zurück -
Gottfried Helms

(... und ab-ins-Bett gleich. Hoffe ich konnte mich trotz der
leichten grippemäßigen geistigen Verschattung ;-) verständlich
machen)

[Hero]

Guite Besserung
Hero

[Hero]

Ich hoffe, dass Du mit dem Quartimax noch
ein schoenes Ergebnis herausbekommst, Gottfried.

Wie kann man nun bei vielen Punkten die
Zahl der Berechnung gering halten ?
(Egal fuer welches Verfahren, ob alle Dreierkombinationen
durchprobieren, oder Maximierung).
Wenn man einerseits einen Kreis hat, in dem
sicher alle Punkte liegen (so wie in "Iris
und Pupille") und andererseits eine Untergrenze
fuer den Kreisradius, kann man dann Punkte
ausschliessen?
Gottfried, deine Drehungen brachten mich auf
folgendes:
Nimmt man eine Springform vom Kuchenbacken
(11 cm Radius) und bewege einen Kuchenteller
(8 cm Radius) im Inneren hin und her, rolle ihn
am Innenrad der Form herum - immer bleibt ein
innerer Kreis von 11 - 2*(11-8)=5 (cm) Radius
bedeckt.

So und damit hat man jetzt fogende
Vorgehensweise.
Bestimme die laengste Verbindungsstrecke d
des Punkthaufens. Liegen alle Punkte
in einem Kreis um den Mittelpunkt D und
Durchmesser d , dann ist man schon fertig.
So nicht, bestimme man die Entfernung s
des am weitesten von D entfernten Punktes.
Schlage um D einen Kreis mit dem Radius
r1 = s - 2* (s - d/2).
Entferne alle Punkte aus dem inneren
Kreis, bzw betrachte im folgenden nur
noch Punkte im Kreisring, also mit
Abstand von D groesser/gleich r1.
Bilde alle Umkreise von je drei Punkten.
Der grösste davon ist der gesuchte
minimale Kreis fuer alle Punkte des
Clusters.
(Anmerkung: bei sehr großen
Punktmengen nutze die Tatsache aus, dass nur
spitzwinklige Dreiecke betrachtet werden.
Ebenso kann man nach Finden eines oder
mehrerer Umkreise mit Radius s2, s3,..
groesser s (s=s1 genannt),
nochmals Punkte entfernen und zwar aus einem
Kreis um D mit Radius
r2 = s2 - 2* (s2 - d/2)
r3 = s3 - 2* (s3 - d/2)
Man wiederholt also das Experiment mit
derselben Springform, aber groesserem
Teller.)
Rollt mal schoen mit dem Auge
(des Clusters)
und Gottfried gute Besserung
Hero

[Gottfried Helms]

Hallo Hero -

das sieht ja ganz gut aus. Ich habe das zwar noch nicht
1:1 durchgerechnet, aber ich habe einen Einwand:

Wenn Du mit einem Kreis anfängst, der durch die längste
Punkte-Differenz festgelegt ist(indem sie sein Durchmesser ist)
und einen neuen Punkt hinzufügst, der außerhalb des Kreises liegt,
und Du baust nun einen Kreis, der diesen Punkt zusätzlich
auf der Kreislinie hat, dann wird bei einer Größenminimierung
sicherlich auch der Mittelpunkt verschoben.

Dann kann es aber sein, daß vorhandene Punkte nach außen
rutschen, - auch *ohne* daß eine neue "längste Distanz"
entstanden sein müßte.
Du mußt dann also *alle* vorhandenen Punkte daraufhin
überprüfen.

Ist dieses Problem in Deinem Ansatz behandelt? (habe ich vielleicht
nur übersehen)

Noch mal zurück zu meinem (aufwendigeren) iterativen
Verfahren mit dem minimalen Quadrat/Rechteck. Ein Gedanke
dabei war, daß die Extrempunkte auf dem minimalen Rechteck/Quadrat
Kreispunkte sein müßten (bzw innen liegen) und daher den
minimalen Kreis um den Ursprung definieren. Wäre das nicht
richtig?

Gruß -

Gottfried Helms

Post by Hero
Jetzt klingt das so, als waere da keine exakte
Loesung, aber hier noch mal Deine Loesung

[snip]

[Helmut Richter]

Post by Gottfried Helms
Dann kann es aber sein, daß vorhandene Punkte nach außen
rutschen, - auch *ohne* daß eine neue "längste Distanz"
entstanden sein müßte.

Es genügt, wenn bei jedem Schritt der Kreisradius wächst. Es gibt nur
endlich viele Kreise, und so terminiert das Verfahren.

Post by Gottfried Helms
Du mußt dann also *alle* vorhandenen Punkte daraufhin
überprüfen.

Das ist richtig. Wenn man einen neuen Kreis festgelegt hat, muss man bei
der Suche nach Punkten, die noch außerhalb liegen, *alle* Punkte
betrachten, auch die man schon mal hatte. Trotzdem ist man nach endlich
vielen Schritten fertig.

Helmut Richter

[Hermann Kremer]

Achim Meyer schrieb in Nachricht

Post by Achim Meyer
Also, ich habe 5 gegebene Punkte A(x,y), B(x,y).....und möchte um
diese Punkte herum den kleinstmöglichen Kreis haben. Gesucht ist
Radius und Mittelpunkt.
Mit 3 Punkten ging das ja eigendlich ganz einfach. Bei 5en hab ich
noch nicht mal einen Lösungsansatz.
Das ganze soll hinterher wieder auf Excel laufen. Also mit Zirkel und
Lineal ist mir nicht sehr geholfen.

Vielleicht hilft ja auch der Satz von Heinrich W. E. Jung (1876 - 1953)
http://www.mathematik.uni-halle.de/history/jung/index.html
http://mathworld.wolfram.com/JungsTheorem.html
und hier das Original-Paper:
http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?did=D261177

Grüße
Hermann
--

Post by Achim Meyer
Vielen Dank schonmal für eure Mühe,
Achim

[Rainer Rosenthal]

"Hermann Kremer" schrieb

Post by Hermann Kremer
Vielleicht hilft ja auch der Satz von Heinrich W. E. Jung (1876 - 1953)
http://www.mathematik.uni-halle.de/history/jung/index.html
http://mathworld.wolfram.com/JungsTheorem.html
http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?did=D261177

*** Für Schnell-Leser: Nix.

Auf de.rec.denksport gibt es mal wieder eine prächtige Aufgabe
von Gerhard Wöginger(*).

================== Aufgabe vom 18.3.2005 =========================
Ein Tangram Spiel besteht aus 7 Teilen:

1 Quadrat mit Seitenlaenge 1
2 rechtwinklige Dreiecke mit Seitenlaengen 1,1,sqrt(2)
2 rechtwinklige Dreiecke mit Seitenlaengen 2,2,sqrt(8)
1 rechtwinkliges Dreieck mit Seitenlaengen sqrt(2),sqrt(2),2
1 Parallelogramm, mit Seitenlaengen 1 und sqrt(2) und
einem Innenwinkel gleich 45 Grad

Der Durchmesser einer geometrischen Figur F ist der
groesstmoegliche Abstand zweier Punkte in F.


Finde eine (nicht-ueberlappende) Anordnung der sieben
Tangramteile in der Ebene, die den *Durchmesser* der
resultierenden Figur minimiert!
===================================================================

Ein wenig mogelnd bin ich mit Google unterwegs gewesen. Und dabei
fand ich eine nette Experimentier-Seite, die zum Thema dieses Threads
passt, an dem ich mich leider nicht beteiligen konnte:
http://www.delphiforfun.org/Programs/circle_covering_points.htm

... Hoppla, dies war eine Echtzeit-Unterbrechung von ca. 30 Minuten,
... denn auf der Suche durch R. K. Guy's wunderbares UPINT bin ich
... mächtig abgelenkt worden durch den lapidaren Anfangssatz des
... Kapitels F10, wo es heisst: "Graham asks about the residue of
... 2^n mod n." Nix weiter. Passt Faust-Auge-mässig auf meinen Thread
... in alt.math.recreational, wo ich (angeregt durch die Massbänder!)
... aus meiner Verwunderung über 2^n mod n die Folge 18, 25, 27, ...
... vorgestellt hatte.

Hier ist also das zum Thread passende Kapitel F1 aus UPINT (s.u.)

"Ein sehr schwieriges ungelöstes Problem ist
DAS PROBLEM VON GAUSS: Wie viele Gitterpunkte
sind im Kreis mit Radius r um den Ursprung?"

Ein paar Ansätze dazu werden genannt. Mit dem Ansatz Pi+r^2 + h(r)
arbeitend, haben Hardy & Landau zeigen können, dass h(r) *nicht*
als o(r^(1/2)*(ln r)^(1/4)) abgeschätzt werden kann. [Anm. WAS
die Leute alles beweisen, tz tz tz ...].
Es wird vermutet, dass h(r) = O(r^(7/11+epsilon)), und das beste
Ergebnis stammt von Huxley: h(r) = O(r^(46/73+epsilon)).

Mit UPINT ist gemeint:

Richard K.Guy
Unsolved Problems in Number Theory Volume 1
Springer Verlag 1994
ISBN 0-387-94289-0

(*) Eine? VIELE!!!

Herzlichen Gruss,
Rainer Rosenthal
***@web.de

[Hermann Kremer]

Post by Rainer Rosenthal
"Hermann Kremer" schrieb

Post by Hermann Kremer
Vielleicht hilft ja auch der Satz von Heinrich W. E. Jung (1876 - 1953)
http://www.mathematik.uni-halle.de/history/jung/index.html
http://mathworld.wolfram.com/JungsTheorem.html
http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?did=D261177

*** Für Schnell-Leser: Nix.

Hmm, da in Göttingen anscheinend immer noch eine Baustelle ist, hier
ein Link, der soeben (!) noch funktionierte:

H: Jung: Über den kleinsten Kreis, der eine ebene Figur einschließt.
J. reine u. angew. Math. 137 (1910), S. 310 - 313
http://gdz-srv3.sub.uni-goettingen.de/sub/digbib/loader?did=D261177
oder
http://gdz-srv3.sub.uni-goettingen.de/cache/toc/D261168.html

Post by Rainer Rosenthal
Ein wenig mogelnd bin ich mit Google unterwegs gewesen. Und dabei
fand ich eine nette Experimentier-Seite, die zum Thema dieses Threads
http://www.delphiforfun.org/Programs/circle_covering_points.htm
Hier ist also das zum Thread passende Kapitel F1 aus UPINT (s.u.)
"Ein sehr schwieriges ungelöstes Problem ist
DAS PROBLEM VON GAUSS: Wie viele Gitterpunkte
sind im Kreis mit Radius r um den Ursprung?"
Ein paar Ansätze dazu werden genannt. Mit dem Ansatz Pi+r^2 + h(r)
arbeitend, haben Hardy & Landau zeigen können, dass h(r) *nicht*
als o(r^(1/2)*(ln r)^(1/4)) abgeschätzt werden kann. [Anm. WAS
die Leute alles beweisen, tz tz tz ...].
Es wird vermutet, dass h(r) = O(r^(7/11+epsilon)), und das beste
Ergebnis stammt von Huxley: h(r) = O(r^(46/73+epsilon)).

Die Literatur dazu hatte ich vor einiger Zeit mal für Eric Weisstein
zusammengesucht, siehe
http://mathworld.wolfram.com/GausssCircleProblem.html
Die Papers von Edmund Landau gibt es alle online am GDZ in Göttingen.

Grüße
Hermann
--

Post by Rainer Rosenthal
Richard K.Guy
Unsolved Problems in Number Theory Volume 1
Springer Verlag 1994
ISBN 0-387-94289-0
(*) Eine? VIELE!!!
Herzlichen Gruss,
Rainer Rosenthal

[Rainer Rosenthal]

"Hermann Kremer" schrieb

Post by Hermann Kremer
Hmm, da in Göttingen anscheinend immer noch eine Baustelle ist, hier
H: Jung: Über den kleinsten Kreis, der eine ebene Figur einschließt.
J. reine u. angew. Math. 137 (1910), S. 310 - 313
http://gdz-srv3.sub.uni-goettingen.de/sub/digbib/loader?did=D261177
oder
http://gdz-srv3.sub.uni-goettingen.de/cache/toc/D261168.html

Post by Rainer Rosenthal
Hier ist also das zum Thread passende Kapitel F1 aus UPINT (s.u.)
"Ein sehr schwieriges ungelöstes Problem ist
DAS PROBLEM VON GAUSS: Wie viele Gitterpunkte
sind im Kreis mit Radius r um den Ursprung?"

Die Literatur dazu hatte ich vor einiger Zeit mal für Eric Weisstein
zusammengesucht, siehe
http://mathworld.wolfram.com/GausssCircleProblem.html
Die Papers von Edmund Landau gibt es alle online am GDZ in Göttingen.

*verneig* und *danke*!

Hast Du zu F10 vielleicht auch mal was gesehen? Also zum Thema 2^n mod n.

Herzlich grüssend,
Rainer Rosenthal
***@web.de

[Hermann Kremer]

Post by Rainer Rosenthal
"Hermann Kremer" schrieb
Hast Du zu F10 vielleicht auch mal was gesehen? Also zum Thema 2^n mod n.

Leider nein, sorry.

Viele Grüße
Hermann
--

Post by Rainer Rosenthal
Herzlich grüssend,
Rainer Rosenthal

[Helmut Richter]

Post by Hermann Kremer
Vielleicht hilft ja auch der Satz von Heinrich W. E. Jung (1876 - 1953)
http://www.mathematik.uni-halle.de/history/jung/index.html
http://mathworld.wolfram.com/JungsTheorem.html
http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?did=D261177

Mindestens der letzte Link ist unzugänglich.

Aber egal, wir hatten die meisten Ergebnisse hier schon im Thread. Weil
sie so verstreut sind, fasse ich sie noch einmal zusammen, nicht zuletzt
für mich selbst.

Def.: Ein Punkthaufen (das ist die Terminologie in Toeplitz/Rademachers
Buch) ist eine endliche, mindestens zweielementige Menge von Punkten in
der Ebene.

Def.: Der Hüllkreis (T/R nennen das "Pferchkreis", aber das ist
unglücklich, weil das Wort in der Messtechnik etwas anderes bezeichnet)
eines Punkthaufens ist der kleinste Kreis, der alle Punkte des
Punkthaufens enthält.

Der Hüllkreis ist eindeutig, und er ist der Hüllkreis einer zwei- oder
dreielementigen Teilmenge des Punkthaufens. Im zweielementigen Fall liegen
die beiden Punkte sich auf dem Kreis gegenüber, im dreielementigen Fall
bilden die drei Punkte ein spitzwinkliges Dreieck. Das hatte ich im Thread
vorausgesetzt, ohne es zu beweisen; hole ich unten nach.

Die zwei bzw. drei Punkte nenne ich "Stützpunkte" des Kreises; liegen mehr
als drei Punkte des Punkthaufens auf der Kreislinie, gibt es
möglicherweise mehr als ein spitzwinkliges Dreieck von Stützpunkten, aber
das ist egal: man kann dann irgendeines nehmen.

Damit hat man einen Algorithmus: Man beginne mit zwei Punkten als
Stützpunkten und dem Kreis dazu. Solange noch Punkte außerhalb des Kreises
liegen, konstruiert man den Hüllkreis der Menge, die aus einem der Punkte
außerhalb sowie den alten Stützpunkten besteht, und macht dann mit den
Stützpunkten des neuen Hüllkreises weiter. Da es nur endlich viele
potentielle Hüllkreise gibt und die Radien immer größer werden, terminiert
das Verfahren. Es terminiert aber nicht, bevor alle Punkte eingefangen
sind. Daher liefert es die Lösung.

Man darf nicht glauben, dass ein einmal eingefangener Punkt in den
folgenden Kreisen weiterhin enthalten ist - das ist i.A. nicht wahr. Das
macht aber nichts, weil er später wieder eingefangen wird, wenn er
entwischt ist.

Um die blöde Rechnerei nicht zu oft machen zu müssen, möchte man bald
große Kreise haben. Das macht man, indem man mit zwei weit entfernten
Punkten beginnt und dann immer recht weit entfernte dazunimmt. Viel Grips
in die Entfernungsberechnungen zu stecken lohnt aber nicht, weil
mitnichten die entferntesten auch die besten Punkte zum Weitermachen sind.
Ich würde vorschlagen, am Anfang den nördlichsten, südlichsten,
östlichsten und westlichsten Punkt zu nehmen und mit diesen zwei bis vier
Punkten zu beginnen; die Reduktion von vier Punkten auf drei braucht man
im Algorithmus eh.

So, und jetzt die fehlenden Sätze:

Satz 1: Der Hüllkreis ist eindeutig.

Beweis: Gäbe es zwei Hüllkreise, so würden sie sich in einem
Kreisbogenzweieck schneiden, das alle Punkte des Punkthaufens enthält. Das
hätte aber einen kleineren Hüllkreis.

Satz 2: Der Hüllkreis enthält nicht zwei Punkte des Punkthaufens in der
Weise, dass sie sich nicht gegenüberliegen und der längere der beiden
Kreisbögen keinen weiteren Punkt des Punkthaufens enthält.

Beweis: Wir teilen die Ebene mittels der Geraden durch die beiden Punkte
in zwei Halbebenen. Sei R die Halbebene (ohne die Gerade), die den
längeren Kreisbogen enthält und sei K die Menge der Punkte des
Punkthaufens, die in R liegen. Wir bestimmen nun den kleinsten Winkel
alpha unter den Winkeln, unter denen von einem Punkt aus K die Strecke
zwischen den beiden gegebenen Punkten erscheint. Dann unterscheiden wir:

- Ist alpha > 90° oder ist K leer, so ist der Kreis ein Hüllkreis, der die
Strecke zwischen den beiden Punkten als Durchmesser hat.

- Sonst ist der Fasskreis zum Winkel alpha über dieser Strecke der
Hüllkreis.

In beiden Fällen ist der neu konstruierte Hüllkreis kleiner als der
gegebene, im Gegensatz zur Minimaleigenschaft.

Satz 3: Der Hüllkreis eines Punkthaufens enthält mindestens zwei Punkte
davon. Wenn er genau zwei Punkte enthält, liegen sie sich auf dem Kreis
gegenüber.

Beweis: Im Fall von zwei Punkten folgt das aus Satz 2. Im Fall von keinem
oder einem Punkt ließe sich der Punkthaufen um zwei bzw. einen Punkt so
ergänzen, dass Satz 2 verletzt würde.

Satz 4: Der Hüllkreis der Ecken eines spitzwinkligen Dreieck ist dessen
Umkreis.

Beweis: Nach Satz 3 gibt es nur drei Kandidaten für einen Hüllkreis mit
nur zwei Punkten darauf. Die funktionieren alle nicht. Also muss der
Hüllkreis durch alle drei Punkte gehen und das tut nur der Umkreis.

Satz 5: Der Hüllkreis eines Punkthaufens ist der Hüllkreis einer zwei-
oder dreielementigen Teilmenge des Punkthaufens.

Beweis: Der Hüllkreis enthält mindestens zwei Punkte des
Punkthaufens. Enthält er mehr als drei, so kann man welche weglassen,
solange das Dreieck spitzwinklig bleibt; das lässt sich immer erreichen,
wenn sich nicht zwei Punkte gegenüberliegen.

Das wars.

Helmut Richter

[Hero]

Erstmal Gottfried alles Gute und weiterhin
gute Besserung. Viellleicht kann er ja schon wieder
mitlesen.

Rainer , toll Dein Link. Wie bist Du denn darauf
gekommen ?
Na ja, die Ergebnisse hier schneiden nicht so schlecht ab.
Auch die Erweiterung auf Tangram-Teile ist nicht schlecht,
mal sehen, wann wir wieder anfangen zu puzzeln.
Oder hat da schon jemand eine Loesung.
Und dass Gauss auch schon Gitterpunkte in Kreisen
einfing, und man bis heute dazu keine exakte
Loesung hat, wusste ich nicht. Na, wen reizt das?
Jedenfalls viel Erfolg bei den Linealen.

Hermann, das Papier von Heinrich W.E.Jung
war ein Volltreffer. Da hast Du Dich sicher gefreut.
1910, heisst das, dass er einer der ersten (der
erste) Cluster-Forscher ist?
Ich hatte nur auf dem einen Link die Abschätzung d/sqrt 3
gelesen. Jetzt las ich auch die Abhandlung.
Na ja, selber herausfinden, macht auch Spass.
Das sehen wir ja an Helmut, der alles
mal exakt bewiesen hat.

Gottfried (und natuerlich alle stillen
Mitleser), bleibt also, ein effektives
Verfahren zu finden bei vielen Punkten,
damit man nicht alle durchprobieren muss.
Meine Vorschläge , wie man Punkte
ausschliessen kann (mit dem Kuchenteller-
Verfahren), hatte ich ja schon gemacht.

Viel Spass weiterhin
Hero

[Rainer Rosenthal]

"Hero" schrieb

Post by Hero
Und dass Gauss auch schon Gitterpunkte in Kreisen
einfing, und man bis heute dazu keine exakte
Loesung hat, wusste ich nicht. Na, wen reizt das?

Eben, das hat mich auch vom Sockel gehauen. Und ich dachte,
dass ich das unbedingt erzählen müsste. Dass *unser* Hermann
das nicht nur wusste sondern obendrein noch die Literatur
für die Online-Gemeinde verfügbar gemacht hatte, das war dann
das i-Tüpfelchen! Oder besser: der dicke Sahne-Klacks.

Gruss,
Rainer Rosenthal
***@web.de

[Hermann Kremer]

Hero schrieb in Nachricht

Post by Hero
Erstmal Gottfried alles Gute und weiterhin
gute Besserung. Viellleicht kann er ja schon wieder
mitlesen.

Dem möchte ich mich anschließen.

Post by Hero
Hermann, das Papier von Heinrich W.E.Jung
war ein Volltreffer. Da hast Du Dich sicher gefreut.
1910, heisst das, dass er einer der ersten (der
erste) Cluster-Forscher ist?

Gut möglich. Es gibt noch ein Paper von ihm von 1901:

Heinrich Jung: Über die kleinste Kugel, die eine
räumliche Figur einschließt.
J. f. reine u. angew. Mathematik 123 (1901), S. 241 - 257
http://gdz-srv3.sub.uni-goettingen.de/sub/digbib/loader?did=D261400
http://gdz-srv3.sub.uni-goettingen.de/cache/toc/D261386.html
http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?did=D261400
Ich hoffe, daß mindestens einer der Links funktioniert ...

Post by Hero
Ich hatte nur auf dem einen Link die Abschätzung d/sqrt 3
gelesen. Jetzt las ich auch die Abhandlung.
Na ja, selber herausfinden, macht auch Spass.
Das sehen wir ja an Helmut, der alles
mal exakt bewiesen hat.

Yep.

Viele Grüße
Hermann
--

[Gottfried Helms]

Post by Hermann Kremer
Hero schrieb in Nachricht

Post by Hero
Erstmal Gottfried alles Gute und weiterhin
gute Besserung. Viellleicht kann er ja schon wieder
mitlesen.

Dem möchte ich mich anschließen.

Hallo Hero, Hermann -

das ist ja nett - da geht es einem gleich viel besser... :-)
Ja, herzlichen Dank. Mitlesen war schon ok, aber es hat halt
nur für die eine oder andere kurze MSG hier & da gereicht.

Post by Hermann Kremer

Post by Hero
Hermann, das Papier von Heinrich W.E.Jung
war ein Volltreffer. Da hast Du Dich sicher gefreut.
1910, heisst das, dass er einer der ersten (der
erste) Cluster-Forscher ist?

Heinrich Jung: Über die kleinste Kugel, die eine
räumliche Figur einschließt.

Jezt fällt mir auch wieder ein, warum ich überhaupt auf diesen
rotationsanalytischen Ansatz gekommen war: weil diese Rotations-
Verfahren, mit denen ich aus der Faktorenanalyse vertraut bin,
von vornherein alle als beliebig multidimensional ausgelegt
sind. Ich hatte das vor einiger Zeit einmal in dem best-passende
Ellipse-Thread ausprobiert - allerdings ging es dort nicht um die
einhüllende Kurve/Oberfläche/Hypersurface, sondern um eine
Least-Squares-Approximation.

Für die guten Wünsche
nochmals herzlichen Dank -

Gottfried Helms