Skript zum Kurs Geometrie mit dem Computer Sommersemester 2007

Skript zum Kurs Geometrie mit dem Computer Sommersemester 2007 Hans-Gert Gr¨abe, Univ. Leipzig 19. Juli 2007

0

Einfu ¨ hrung

Die (synthetische) Geometrie ist eine sehr alte mathematische Disziplin und stand lange Zeit wohl f¨ ur Mathematik schlechthin, ehe ihr dieser Platz durch eine st¨ urmische Entwicklung der Mathematik in den letzten 200 Jahren von anderen Disziplinen streitig gemacht wurde. Nat¨ urlich hat sich in dieser Zeit auch die Geometrie weiter entwickelt. Teildisziplinen wie Differentialgeometrie oder Algebraische Geometrie untersuchen komplizierte geometrische Gebilde und haben zu wichtigen Einsichten u uhrt. Die elementare Geometrie ist dar¨ uber, ¨ ber die Struktur von Raum (und Zeit) gef¨ vollkommen zu unrecht, in die zweite Reihe ger¨ uckt. Das findet insbesondere seinen Ausdruck im Curriculum der Schule, in dem (elementar)geometrische Fragestellungen nur noch in geringem Umfang auftauchen. Andererseits faszinieren solche Aufgaben immer wieder durch die Einfachheit, mit der relevante Probleme formuliert werden k¨ onnen, sowie den Scharfsinn und die Tiefgr¨ undigkeit der Argumentation, die zu deren Beantwortung herangezogen werden m¨ ussen. Sie sind damit f¨ ur Hobbymathematiker, interessierte Sch¨ uler eingeschlossen, immer wieder eine Fundgrube von Problemen und Ideen, an denen man die eigene Argumentationskraft trainieren und verbessern kann. Die Vielfalt der Argumentationsmuster, die dabei zum Einsatz kommen, lassen eine Mechanisierung derartiger Beweisans¨ atze als schier unm¨ oglich erscheinen. Besonders Fragen der Konstruierbarkeit mit Zirkel und Lineal haben Mathematiker verschiedener Epochen immer wieder fasziniert. So geh¨oren die beiden großen Fragestellungen aus der antiken Mathematik nach der Verdopplung eines W¨ urfels und der Dreiteilung eines beliebigen Winkels mit diesen Instrumenten zu den wohl auch außerhalb der Mathematik bekanntesten geometrischen Problemen. Trotz der Einfachheit der Fragestellung ließ sich deren Unl¨osbarkeit erst exakt nachweisen, als ein entsprechender algebraischer Apparat, in diesem Fall die K¨orpertheorie, entwickelt wurde. Eine solche Methode der Symbolisierung“ geometrischer Sachverhalte in der Spra” che der Algebra erlaubte es C.F. Gauß im Jahre 1796, die Konstruierbarkeit eines 17-Ecks nachzuweisen. Die entsprechenden Argumente sind heute in den meisten Standardwerken zur (h¨oheren) Algebra als Anwendungsbeispiele dieser Theorie enthalten. Ein exaktes Studium der mit der Konstruierbarkeit verbundenen Fragestellungen kommt um eine ordentliche Fundierung, eine Axiomatisierung der Geometrie nicht herum. Auch hier lassen sich die entsprechenden Ans¨ atze bis in die Antike hinein, etwa zu den B¨ uchern des Euklid, verfolgen. Mathematiker hat dabei immer interessiert, geometrische Aussagen und Konstruktionen mit m¨oglichst geringen Voraussetzungen herzuleiten bzw. auszuf¨ uhren. Die aus der Schule bekannte Geometrie setzt dabei das umfangreichste Instrumentarium voraus. Neben Punkten, Geraden, Parallelen, L¨ angen und Winkelgr¨ oßen gibt es auch noch Strecken, Strahlen und Halbebenen, wozu auf jeder Geraden g (auf konsistente Weise) eine Ordnungsrelation zur Verf¨ ugung stehen muss, die 1

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

2

es erlaubt, f¨ ur drei Punkte A, B, C ∈ g zu entscheiden, ob C zwischen A und B liegt. Geometrische Aussagen, die von Strahlen, Halbebenen und dieser Zwischenrelation Gebrauch machen, werden der Ordnungsgeometrie zugeordnet. Da algebraische Verfahren, die wir zum Mechanisieren ausschließlich heranziehen werden, mit solchen Ordnungsrelationen nicht gut zusammenspielen, wollen wir derartige geometrische Aussagen im Weiteren ausklammern. Damit wird der Kreis der betrachteten geometrischen Aufgaben aber nur etwas eingeschr¨ankt, da viele Konfigurationen, in denen Strecken vorkommen, diese Ordnungsrelation in Wirklichkeit nicht ausnutzen. So kann man etwa den Mittelpunkt einer Strecke AB bestimmen, ohne zu wissen, wo auf der Geraden g = g(AB) links oder rechts ist, indem nach dem aus der Schule bekannten Verfahren die Kreise c(A, B) (mit Mittelpunkt A und Peripheriepunkt B) und c(B, A) zum Schnitt gebracht und deren zwei Schnittpunkte miteinander verbunden werden. Der Schnittpunkt dieser Verbindungsgeraden mit g ist der zu konstruierende Mittelpunkt. Eine solche Geometrie, welche nur von Punkten, Geraden, Parallelen, L¨angen und Winkelgr¨oßen (und damit auch Senkrechten und Kreisen) gebrauch macht, wird als Euklidsche, Bewegungsode Kongruenzgeometrie bezeichnet. Allerdings ben¨ otigt man ein so umfangreiches Arsenal von Hilfsmitteln zur Konstruktion des Mittelpunkts einer Strecke nicht wirklich. Man kann den Mittelpunkt einer Strecke AB auch bestimmen, indem man einen dritten Punkt C beliebig w¨ahlt und das Parallelogramm ACBD konstruiert. Die Mitte der Strecke AB ist dann genau der Diagonalenschnittpunkt in diesem Parallelogramm.

Affine Geometrie: Konstruktion des Mittelpunkts einer Strecke

Wir haben daf¨ ur die M¨ oglichkeit der Euklidschen Geometrie, L¨angen (und Winkel) vorgegebener Gr¨oße in einem vorgegebenen Punkt anzutragen, nicht ben¨otigt, sondern einzig die M¨oglichkeit, zu vorgegebenen Geraden Parallelen konstruieren zu k¨onnen. Eine Geometrie, die nur mit Punkten, Geraden und Parallelen auskommt, bezeichnet man als affine Geometrie. Im Mittelpunkt dieser Geometrie stehen der Strahlensatz, Teilverh¨altnisse und Eigenschaften des Parallelogramms. Noch allgemeinere S¨ atze der projektiven Geometrie erh¨alt man, wenn man auch auf die Verwendung von Parallelen verzichtet. Derartige S¨atze sind invariant unter projektiven Transformationen, ¨ d.h. solchen, die man in der Malerei bei der Ubertragung einer weiten Landschaft auf die Staffelei antrifft, wenn sich die ehemals parallelen Geraden im Bild auf der Horizontlinie schneiden. Eine solche projektive Transformation π u ¨ bertr¨agt eine geometrische Konfiguration von einer Ebene ε (im Raum) auf eine andere Ebene ε′ nach folgendem Verfahren: W¨ ahle ein Projektionszentrum Z außerhalb der beiden Ebenen aus. Den Bildpunkt A′ = π(A) ∈ ε′ zu einem Original A ∈ ε findet man als den Schnittpunkt von g(AZ) mit ε′ . Offensichtlich gehen bei dieser Konstruktion Geraden in Geraden u ¨ ber. In der Tat, die Geraden g(AZ) f¨ ur A ∈ g spannen eine Ebene auf, so dass die Bildpunkte auf der Schnittgeraden dieser Ebene mit ε′ liegen. Allerdings besitzt nicht jeder Punkt A der Urbildebene ε einen Bildpunkt, denn die Gerade g(AZ) kann ja parallel zu ε′ verlaufen. Die entsprechenden Punkte A mit dieser Eigenschaft liegen genau auf der Schnittgeraden von ε mit der Parallelen zu ε′ durch Z. Diese Gerade bezeichnet man als die Ausnahmegerade auf ε. Ihre Punkte werden in die unendlich ferne“ ” Gerade von ε′ abgebildet. Insbesondere sind die Bilder zweier Geraden, die sich in ε auf dieser ′ Ausnahmegeraden schneiden, parallel zueinander. Genauso gibt es auf ε eine Ausnahmegerade.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

3

Die Abbildung π ist jenseits der beiden Ausnahmegeraden eineindeutig. Erweitert man ε bzw. ε′ jeweils durch Hinzunahme einer Ferngeraden zur projektiven Ebene ε bzw. ε′ , wobei die jeweilige Ferngerade Bild bzw. Urbild der Ausnahmegeraden der anderen Ebene ist, so wird die Abbildung π sogar im Ganzen eineindeutig. Aussagen der projektiven Geometrie enthalten also typischerweise Formulierungen der Art . . . die Geraden schneiden sich oder sind parallel zueinander . . .“. ” Wie kann man nun eine solche Vielfalt von Ans¨atzen unter einen Hut bringen? Zun¨achst waren es Mathematiker am Ende des 19. Jahrhunderts, vor allem F. Klein und D. Hilbert, die einen Zusammenhang zwischen dem Umfang der eingesetzten Konzepte und Transformationsgruppen herausfanden. Die aus der Schule bekannte Phrase eindeutig bis auf Kongruenz“ besagt genau ” dies. Aussagen der Bewegungsgeometrie, etwa die Konstruktion eines Dreiecks aus vorgegebenen drei Streckenl¨ angen, sind immer nur eindeutig bis auf Kongruenztransformationen m¨oglich. Form und Gr¨oße des Dreiecks sind eindeutig bestimmt, seine Lage in der Zeichenebene kann durch Drehung, Verschiebung und Spiegelung weitgehend frei gew¨ahlt werden. Die zugeh¨orige Bewegungsgruppe ist die O(2), die Gruppe der orthogonalen Transformationen der Ebene. Streckenl¨angen und Winkelgr¨ oßen bleiben dabei erhalten, so dass orthonormale Koordinatensysteme bei solchen Transformationen in orthonormale Koordinatensysteme u uhrt werden. Solche Koordinatensy¨berf¨ steme bezeichnen wir auch als karthesische Koordinaten. Aussagen der affinen Geometrie bleiben unter weitergehenden Transformationen erhalten. Die zugeh¨orige Gruppe ist die Gl(2), die orthonormale Koordinatensysteme in schiefwinklige u uhrt und auch die ¨ berf¨ L¨angen“ der Einheitsstrecken nicht erh¨alt (aber ” L¨angen gibt es ja nicht). Allerdings kann man durch Parallelogramme wenigstens Strecken vorgegebener L¨ange auf parallelen (und mit einem transitiven Ansatz damit auch auf derselben) Geraden abtragen, was Grundlage f¨ ur (unabh¨ angige) Koordinaten auf wenigstens jeder der beiden Achsen ist. Nat¨ urlich muss ein exakt arbeitender Mathematiker hier auch einen Eindeutigkeitssatz beweisen. Wie lautet der Satz und wie geht der Beweis?

Affine Geometrie: Abtragen einer Streckenl¨ange auf derselben Geraden

Schließlich gibt es noch weitergehende Transformationen, unter denen Aussagen der projektiven Geometrie erhalten bleiben. Die zugeh¨orige Gruppe P Sl(2) ist mit projektiven oder homogenen Koordinaten verbunden, auf die hier zun¨achst nicht eingegangen werden soll. Unsere haupts¨ achlichen Arbeitsmittel werden die Einf¨ uhrung von Koordinaten und Methoden der analytischen Geometrie sein. Es stellt sich dabei heraus, dass es ein solcher Ansatz gestattet, konstruktive, also algorithmische Ans¨atze auf der Seite der Geometrie mit Hilfe eines informatiktheoretischen Hilfsmittels, des Unterprogramms, in einem symbolischen Kontext in vielen F¨allen so auszuwerten, dass sich daraus ein im mathematischen Sinne exakter Beweis ergibt. Das Vorhandensein eines Koordinatensystems werden wir dabei als gegeben voraussetzen. Da ¨ hierf¨ ur allein die Festlegung einer Einheitsstrecke und deren Ubertragbarkeit an alle Orte und Richtungen der Ebene gew¨ ahrleistet sein muss, stellt das wenigstens f¨ ur Problemstellungen innerhalb der Euklidschen Geometrie keine Einschr¨ankung dar. Das Vorhandensein eines Koordinatensystems kann allerdings aus noch viel allgemeineren Annahmen heraus abgeleitet werden. Diese Frage steht im Zentrum der axiomatischen Einf¨ uhrung der Geometrie und wird deshalb in den entsprechenden Lehrb¨ uchern umfassend abgehandelt. Insbesondere in der Monographie [5] von W.T. Wu sind dazu interessante Ausf¨ uhrungen enthalten, in denen auch Koordinatensysteme u ¨ ber nichtkommutativen Zahlbereichen eine Rolle spielen. Wir werden darauf nicht n¨aher eingehen. Eine weitere praktische Anwendung der Koordinatenmethode wird uns allerdings interessieren, denn sie ist auch die Basis f¨ ur die bildliche Darstellung geometrischer Konfigurationen in GrafikSoftware, so dass dieser Kurs gegen¨ uber fr¨ uheren einen st¨arkeren informatik-praktischen Bezug

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

4

haben wird. Wir werden parallel zu den mathematischen Fragen auch die Modellierung in entsprechender Dynamischer Geometrie-Software (DGS) studieren, wozu wir den im Hause entwickelten Java-basierten GeoFuchs“ als Grundlage heranziehen werden. Er ist noch nicht sehr vollkommen, ” deshalb wird auch andere DGS, insbesondere das Programm Zirkel und Lineal“ von Ren´e Groth” mann aus Eichst¨ att, Verwendung finden. Die grundlegende Struktur all dieser Programme ist aber ¨ahnlich.

1

Einige S¨ atze aus der ebenen Geometrie

In diesem Kapitel wollen wir zun¨ achst einige einfache und weniger einfache S¨atze aus der ebenen Geometrie kennenlernen bzw. uns wieder ins Ged¨achtnis zur¨ uckrufen. Dies soll zum einen ausreichendes Material f¨ ur die weiteren Betrachtungen zur Verf¨ ugung stellen, an dem sich zu entwickelnde algorithmische Ans¨atze werden demonstrieren lassen, und zum anderen die Vielfalt geometrischer Argumente noch einmal demonstrieren, die im Rahmen einer Mechanisierung unter einen gemeinsamen Hut zu bringen sind. Außerdem sollen wichtige Begriffe, die beim Beweisen geometrischer Sachverhalte eine Rolle spielen, beispielhaft demonstriert werden.

1.1

S¨ atze u ¨ber die Ecktransversalen im Dreieck

Satz vom Schnittpunkt der Mittelsenkrechten Verwendet den Begriff der Ortslinie: Eine Mittelsenkrechte besteht aus genau den Punkten, die von zwei gegebenen Punkten A, B den gleichen Abstand haben. Aus dem Beweis ergibt sich dann außerdem, dass der Schnittpunkt O von allen drei Eckpunkten gleichweit entfernt ist, also der Umkreismittelpunkt sein muss. Eine Ortslinie verbindet eine geometrische (Mittelsenkrechte als Gerade) mit einer logischen (P mit |AP | = |BP |) Eigenschaft. Ihre Beweiskraft entwickeln Ortslinien aus dem Zusammenspiel beider Seiten.

Die Mittelsenkrechten eines Dreiecks schneiden sich in einem Punkt, dem Umkreismittelpunkt

Beweis : Sei ABC das gegebene Dreieck, D, E, F die Mittelpunkte der Seiten BC, AC, AB und M der Schnittpunkt der beiden Mittelsenkrechten mAB und mBC . Wir zeigen, dass M dann auch auf der dritten Mittelsenkrechten liegt.

M ∈ mAB ⇒ |M A| = |M B| M ∈ mBC ⇒ |M B| = |M C| Daraus folgt |M A| = |M C|, also M ∈ mAC .



Satz vom Schnittpunkt der Winkelhalbierenden Auch hier spielen Ortslinien eine Rolle: Eine Winkelhalbierende besteht aus genau den Punkten, die von zwei gegebenen Geraden den gleichen Abstand haben. Aus dem Beweis ergibt sich dann außerdem, dass der Schnittpunkt W von allen drei Dreiecksseiten gleichweit entfernt ist, also der Inkreismittelpunkt sein muss.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

5

C

B

A

Inkreis und Ankreise eines Dreiecks Allerdings ist das ungenau, denn der genannte geometrische Ort besteht aus den Punkten auf dem Geraden-Paar, das die Halbierenden von Innen- und Außenwinkel bilden. Innenwinkel und Außenwinkel sind allerdings Begriffe der Ordnungsgeometrie und deshalb von unserem Standpunkt aus nicht zu unterscheiden. Die drei Winkelhalbierendenpaare haben neben dem Inkreismittelpunkt noch die drei Mittelpunkte der Ankreise gemeinsam. ¨ Man beachte die Ahnlichkeit zum Begriff des Parallelenpaars als dem geometrischen Ort aller Punkte, die von einer gegebenen Gerade einen vorgegebenen Abstand haben. Zwei Geraden schneiden sich (normalerweise) immer in genau einem Punkt. Wenn drei Geraden durch einen gemeinsamen Punkt gehen oder parallel sind, so liegt schon eine besondere Situation vor. Solche Geraden nennt man konkurrent. Umgekehrt geht durch zwei Punkte (normalerweise) immer genau eine Gerade. Wenn drei Punkte auf einer gemeinsamen Geraden liegen, so liegt ebenfalls eine besondere Situation vor. Solche Punkte nennt man kollinear. Ein nicht so einfaches Beispiel f¨ ur Geraden am Dreieck, die durch einen gemeinsamen Punkt gehen, kann man als Nebeneffekt der Konstruktion der Ankreise beobachten: Um einen Kreis zu zeichnen brauchen wir neben dem Mittelpunkt einen Punkt auf der Peripherie, im Fall des Ankreises also den Lotfußpunkt aus dem Ankreismittelpunkt auf die zugeh¨orige Dreiecksseite. Diese drei Lote gehen durch einen gemeinsamen Punkt!

C

A

B

Die Lote aus den Ankreiszentren gehen durch einen gemeinsamen Punkt

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

6

C

Satz vom H¨ ohenschnittpunkt Beweis u ¨ ber Mehrfachanwendung von Thaleskreis und Peripheriewinkelsatz. Eine weitere Anwendung des Sehnensatzes liefert die zus¨atzliche Eigenschaft, dass der H¨ ohenschnittpunkt die H¨ohen so teilt, dass die Produkte aus den beiden H¨ohenabschnitten jeweils gleichgroß sind.

1.2

D E

A

F

B

Der Satz von Ceva

All diese S¨ atze kann man aus einem allgemeinen Prinzip u ¨ ber Teilverh¨altnisse von Transversalen am Dreieck herleiten. Satz 1 (Satz des Ceva) Drei Ecktransversalen des Dreiecks △ ABC m¨ogen die gegen¨ uberliegenden Seiten in den Punkten D, E, F schneiden. Diese drei Ecktransversalen gehen genau dann durch einen Punkt, wenn |BD| |CE| |AF | · · =1 |DC| |EA| |F B| gilt. Beweis durch Fl¨ achenzerlegung. In diesem Beweis spielen Verh¨ altnisse der Art t = T V (A, B; F ) = |AF | / |F B| f¨ ur kollineare Punkte A, B, F eine wichtige Rolle, die auch als Teilverh¨altnis bezeichnet werden. F¨ ur Punkte innerhalb AB bestimmt es die Lage von F eindeutig. Verwendet man gerichtete Streckenl¨angen, so kann man dieses Teilverh¨ altnis auch f¨ ur Punkte F auf AB definieren, die außerhalb der Strecke liegen. F¨ ur Punkte jenseits von A ergeben sich Werte −1 < t < 0, f¨ ur Punkte jenseits von B ergibt sich t < −1. Stets bestimmt der Wert von t die Lage von F eindeutig. Die Ausnahmen F = B sowie t = 1 lassen sich durch Hinzunahme eines Werts t = ∞ sowie eines Fernpunkts auf der Geraden einordnen. Die Punkte der (projektiven) Geraden AB werden so durch t ∈ P1 parametrisiert, wobei als Bezugsgr¨ oßen die Punkte A(t = 0), B(t = ∞) und der Fernpunkt (t = −1) dienen. Als Folgerung erh¨ alt man neue Beweise der S¨atze vom Schnittpunkt der Seitenhalbierenden und vom H¨ohenschnittpunkt. Aufgabe 1 a) Zeigen Sie, dass man aus dem Satz des Ceva auch den Satz vom H¨ohenschnittpunkt herleiten kann, indem Sie die L¨angen der Seitenabschnitte durch geeignete trigonometrische Formeln ausdr¨ ucken. b) Zeigen Sie, dass die Transversalen zu den Ber¨ uhrungspunkten des Inkreises sich in einem Punkt schneiden. (Hinweis: Berechnen Sie die L¨ange der einzelnen Tangentenabschnitte.) Weitere Folgerung: Die Transversalen zu den drei Ber¨ uhrungspunkten der Ankreise schneiden sich in einem Punkt. (Dieser Punkt heißt auch Nagelscher Punkt)

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

7

Wir betrachten dazu verschiedene Beziehungen zwischen den Tangentenabschnitten zu den Ber¨ uhrpunkten der drei Ankreise: x+y+z = r+s+t x+y+t = z+r+s ⇒ z = t Analog gilt x = r, y = s.

1.3

Weitere S¨ atze am Dreieck

Satz 2 (Eulersche Gerade) In einem Dreieck liegen der H¨ohenschnittpunkt H, der Schwerpunkt S und der Umkreismittelpunkt M auf einer Geraden. S teilt HM im Verh¨altnis 2:1. ¨ Im Beweis werden Dreiecke in Ahnlichkeitslage verwendet. ¨ Zwei Dreiecke ABC und A′ B ′ C ′ heißen in Ahnlichkeitslage, wenn einander entsprechende Seiten jeweils zueinander parallel sind.

Die Eulersche Gerade

Dann kann man schlussfolgern, dass das eine Dreieck aus dem anderen durch eine Zentralstreckung hervorgeht. Diese Aussage ist Gegenstand des folgenden Satzes. Satz 3 (Der affine Satz von Desargue) ¨ 1. Sind △ ABC und △ A′ B ′ C ′ in Ahnlichkeitslage, d.h. ABkA′ B ′ , ACkA′ C ′ und BCkB ′ C ′ , so sind AA′ , BB ′ und CC ′ konkurrent oder parallel. 2. Sind umgekehrt AA′ , BB ′ und CC ′ konkurrent oder parallel und ABkA′ B ′ , ACkA′ C ′ , so gilt auch BCkB ′ C ′ .

Der (affine) Satz von Desargue

Aufgabe 2 Leiten Sie diesen Satz aus dem Strahlensatz her. Der Satz von Desargue spielt in der Fundierung der Geometrie als schwache Version des Strah” lensatzes“ eine wichtige Rolle. Er ist schw¨acher als der Strahlensatz und f¨ uhrt damit zu einer umfassenderen als der affinen Geometrie. Details finden sich im Buch [5].

Satz 4 (Der Satz vom Feuerbachschen Kreis) Der Mittelpunkt N von HM ist der Mittelpunkt eines Kreises, auf dem neun ausgezeichnete Punkte des Dreiecks △ ABC liegen, und zwar • die drei Seitenmitten, • die drei H¨ohenfußpunkte und • die drei Mitten der oberen H¨ohenabschnitte Der Feuerbachsche Kreis Beweis : Die beiden Dreiecke, die durch die Seitenmitten bzw. die Mitten der oberen H¨ohen¨ abschnitte aufgespannt werden, sind in Ahnlichkeitslage mit dem Faktor (−1), also zueinander

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

8

kongruent. Da dabei H als H¨ ohenschnittpunkt des H¨ohendreiecks in M als H¨ohenschnittpunkt des Mittendreiecks u ¨bergeht, ist die Mitte N der Strecke M H gerade das Zentrum dieser Punktspiegelung, d.h. Drehung um 180◦ . Das Dreieck ABC geht bei Streckung um den Faktor − 12 mit Zentrum S in das Mittendreieck u ¨ ber, dessen Umkreismittelpunkt M also in den Umkreismittelpunkt des Mittendreiecks. Bild von M bei dieser Streckung ist aber gerade N . Also geht ein Kreis mit Zentrum in N die genannten 6 Punkte. Weiter entsprechen sich bei der Punktspiegelung mit Zentrum in N Seitenmitte und gegen¨ uberliegende Mitte des oberen H¨ohenabschnitts. Die Verbindungsgerade geht also durch das Streckungszentrum N und ist ein Durchmesser des Feuerbachkreises. Aus dem Satz des Thales folgt schließlich, dass auch der H¨ohenfußpunkt auf dem Feuerbachkreis liegt.  Der Feuerbachkreis hat eine weitere, mit elementargeometrischen Mitteln nur schwer zu beweisende Eigenschaft: Er ber¨ uhrt den Inkreis des Dreiecks △ ABC und dessen drei Ankreise.

1.4

S¨ atze am Dreieck aus der neueren Forschung

Wir erw¨ ahnen hier nur zwei S¨ atze, die im Zusammenhang mit dem mechanisierten Theorembeweisen in der Geometrie immer wieder als Beispiele herangezogen werden. Satz 5 (Der Miquelsche Punkt) P, Q, R seien Punkte auf den Seiten des Dreiecks △ ABC. Zeichnet man durch jede Ecke und die beiden Punkte, welche auf den zu dieser Ecke inzidenten Seiten liegen, Kreise, so gehen diese durch einen gemeinsamen Punkt. Der Beweis folgt fast unmittelbar aus dem Satz u ¨ ber das Sehnenviereck und dessen Umkehrung.

Der Miquelsche Punkt

Satz 6 (Die Simsonsche Gerade) F¨allt man von einem Punkt P außerhalb eines Dreiecks △ ABC die Lote auf die Dreiecksseiten oder deren Verl¨angerungen, so liegen die drei Fußpunkte der Lote genau dann auf einer Geraden, wenn P auf dem Umkreis des Dreiecks △ ABC liegt. Die Simsonsche Gerade Beweis : Seien die drei Fußpunkte mit A1 , B1 , C1 bezeichnet (d.h. A1 ist der Fußpunkt des Lots von P auf BC usw.). Der Thaleskreis u ¨ ber P C liefert |∠ B1 A1 P | = |∠ B1 CP |. Der Thaleskreis u ¨ ber P A liefert |∠ B1 C1 P | = |∠ B1 AP |. Im Sehnenviereck ABCP ist |∠ AP C| = 180◦ −β. Wegen zweier rechter Winkel ist aber auch |∠ A1 P C1 | = 180◦ − β. Folglich ist |∠ A1 B1 C1 | = |∠ AB1 C| = 180◦ , A1 , B1 , C1 also kollinear.  Zu beiden S¨ atzen g¨ abe es noch eine Menge zu sagen. So kann man etwa zu jedem Punkt P im Inneren des Dreiecks ∆ ABC Punkte A1 , B1 , C1 so auf den Dreiecksseiten finden, dass P der zugeh¨orige Miquelsche Punkt ist. Ein solches Dreieck bekommt man (Thalessatz !) insbesondere dann, wenn man von P aus die Lote auf die drei Dreiecksseiten f¨allt. Dieses Dreieck wird auch als das zum Punkt P geh¨ orende Fußpunktdreieck bezeichet.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

9

Aufgabe 3 a) [2, 1.91] Zeigen Sie, dass die Seiten des Fußpunktdreiecks von P die L¨angen ax by cz , , 2r 2r 2r haben, wobei a = |BC| , b = |AC| , c = |AB| die L¨angen der Seiten des Dreiecks △ ABC, r dessen Umkreisradius und x = |AP | , y = |BP | , z = |CP | die Abst¨ande von den Eckpunkten zu P sind. b) Zeigen Sie, dass f¨ ur den Fl¨acheninhalt des Fußpunktdreiecks △ A B C bzgl. P 2

F (A B C ) =

r2 − |M P | · F (ABC) 4 r2

gilt, wobei M der Umkreismittelpunkt ist. Das eben betrachtete Fußpunktdreieck entartet zu einer Geraden, wenn P auf dem Umkreis des Dreiecks △ ABC liegt und ergibt dann genau die Simsonsche Gerade. Von Satz u ¨ber die Simsonsche Gerade gilt u ¨brigens auch die Umkehrung: Satz 7 (Simsonsche Gerade II) Sind die Lotfußpunkte A1 , B1 , C1 von einem Punkt P auf die Seiten des Dreiecks ∆ ABC oder deren Verl¨angerungen kollinear, so liegt P auf dem Umkreis des Dreiecks. Aufgabe 4 a) Leiten Sie aus der Fl¨acheninhaltsformel f¨ ur das Fußpunktdreieck (vorige Aufgabe) einen zweiten Beweis f¨ ur den Satz ¨ uber die Simsonsche Gerade her. b) Beweisen Sie die Umkehrung des Satzes von der Simsonschen Geraden. Weitere interessante S¨ atze, die an dieser Stelle vielleicht noch zu nennen w¨aren (alle aus [2]): das Schmetterlings-Theorem oder der Satz von Morley.

1.5

S¨ atze der projektiven Geometrie

Wir wollen dieses Kapitel mit einigen S¨atzen aus der projektiven Geometrie beschließen, die ob der verwendeten Mittel (meist nur gen¨ ugend verzwickte Geradenkonfigurationen) einen ganz speziellen Reiz besitzen. Satz 8 (Theorem von Pappus) Sind A, C, E und B, D, F jeweils kollineare Punkte, so sind auch die Schnittpunkte AB ∧ DE, BC ∧ EF und CD ∧ AF kollinear. Die entstehende Gerade wird als Pappus-Gerade bezeichnet.

C E A

D B F

Pappus-Gerade

Beweis : Wir beweisen diesen Satz zuerst in einer speziellen Situation, in der zwei der drei Verbindungegeraden zueinander parallel sind: ABkDE, BCkEF ⇒ CDkAF Der Beweis ergibt sich hier unmittelbar aus dem Strahlensatz und seinen Umkehrungen. F¨ ur den allgemeinen Beweis verwenden wir eine projektive Transformation, bei der die Gerade g(AB ∧ DE, BC ∧ EF ) die Ausnahmegerade ist, d.h. in der Bildebene in die Ferngerade u ¨bergeht.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

10

Damit sind f¨ ur das Bild unserer Geradenkonfiguration die Voraussetzungen des bewiesenen Spezialfalls erf¨ ullt und die Bilder von g(CD) und g(AF ) sind zueinander parallel. Die Urbilder schneiden sich damit auf der Ausnahmegeraden, so dass die drei Schnittpunkte kollinear sind.  ¨ Ubrigens ist auch der Satz von Desargue eigentlich ein projektiver Satz. Satz 9 (Allgemeiner Satz von Desargue) Sind die Schnittpunkte AB ∧ A′ B ′ , AC ∧ A′ C ′ und BC ∧ B ′ C ′ kollinear, so gehen die drei Geraden AA′ , BB ′ und CC ′ durch einen gemeinsamen Punkt. Beweis : Wir betrachten eine projektive Transformation, die die Gerade durch die drei Schnittpunkte auf die Ferngerade abbildet. Dann haben wir gerade die Situation des affinen Satzes von Desargue vorliegen.  Eine interessante Fragestellung, die wir zum selben Thema hier nur aufwerfen wollen, entsteht aus dem Vergleich verschiedener Pappus-Geraden. Sind A1 , A2 , A3 und B1 , B2 , B3 jeweils kollinear, so f¨ uhren die verschiedenen Permutationen der Punkte B1 , B2 , B3 zu insgesamt 6 solchen Geraden (Permutationen der Punkte auf der anderen Geraden haben keinen Einfluss: Ist (σ, τ ) ein Paar von Permutationen der Punkte (A) und (B), so liefert die Permutation (1, σ −1 τ ) dieselbe Pappus-Gerade). Es stellt sich heraus, dass drei dieser Geraden durch einen gemeinsamen Punkt gehen.

C C’ A’ A B’ B

Allgemeiner Satz von Desargue

Die 6 Pappusgeraden zu einer Punktkonfiguration

Der Satz von Pappus ist ein Spezialfall eines noch allgemeineren Satzes der projektiven Geometrie. Wir betrachten dazu eine Konfiguration aus sechs Punkten der Ebene A, B, C, D, E, F , f¨ ur die X = AB ∧ DE, Y = BC ∧ EF und Z = CD ∧ AF kollinear sind. In einer solchen Konfiguration sind die ersten f¨ unf Punkte frei w¨ ahlbar, wobei auch die Lage von X bestimmt wird. Die Richtung der Geraden g = g(EF ) bestimmt Y eindeutig und somit auch Z = CD ∧ XY . F ergibt sich dann als F = AZ ∧ g. Eine solche Punktekonfiguration bezeichnet man als ein Pascalsches Sechseck. F¨ uhrt man Koordinaten ein, so stellt sich heraus, dass sich solche Punktekonfigurationen analytisch recht einfach charakterisieren lassen. Es gilt der folgende E

Satz 10 (Satz von Pascal) Sechs Punkte spannen genau dann ein Pascalsches Sechseck auf, wenn sie auf einer Kurve zweiten Grades liegen. Auf einen vollst¨ andigen Beweis dieses Satzes muss hier verzichtet werden, da hierf¨ ur noch Kurven zweiten Grades einzuf¨ uhren w¨ aren. Man kann aber wie im Beweis des Satzes von Pappus einen wesentlichen Teil durch eine projektive Transformation aus einer spezielleren Situation herleiten, die Gegenstand der folgenden Aufgabe ist.

C

A

F D B

Pascalsches Sechseck

Aufgabe 5 Beweisen Sie den folgenden Spezialfall des Satzes von Pascal:

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

11

Liegen die Punkte A, B, C, D, E, F auf einem Kreis und gilt ABkCD und BCkEF , so ist auch CDkEF . Eine wichtige Folgerung aus dem Satz von Pascal ist die aus der urspr¨ unglichen Definition nicht ersichtliche Tatsache, dass jede Permutation von Punkten, die ein Pascalsches Sechseck aufspannen, wieder ein solches bilden. Das liefert Aussagen der ebenen Geometrie, zu deren Formulierung keine Kurven zweiter Ordnung ben¨ otigt werden. Solche S¨atze heißen in [5] S¨atze vom Pascal-Typ. Ein solcher w¨ are z.B. die folgende Aussage: Sind R = AB ∧ DE, S = BC ∧ EF, T = CD ∧ AF kollinear, so sind auch X = AD ∧ CF, Y = BD ∧ CE, Z = BF ∧ AE kollinear.

E C

A R

Um dieses Bild zu zeichnen m¨ ussen die Punkte in geeigneter Reihenfolge eingef¨ uhrt werden: R, T und A k¨onnen frei gew¨ ahlt werden. Die Punkte S ∈ RT, B ∈ AR, C ∈ BS, D ∈ CT und E ∈ DR ergeben sich als (semifreie) Gleiter auf Geraden, der letzte Punkt F = ES ∧ AT als Schnittpunkt zweier Geraden.

1.6

T

D

S F

B

Satz vom Pascal-Typ

Zur Dualit¨ at von Punkten und Geraden in der projektiven Geometrie

In vielen geometrischen Aussagen u ¨ ber Punkte und Geraden kann man die Worte Punkt“ und ” Gerade“ vertauschen und bekommt einen ebenfalls g¨ ultigen geometrischen Satz. Die einfachsten ” Aussagen dieser Art sind • Es gibt genau eine Gerade durch zwei (voneinander verschiedene) Punkte. • Zwei voneinander verschiedene Geraden haben genau einen Schnittpunkt (oder sind parallel). Die Sonderrolle zueinander paralleler Geraden kann man aufheben, wenn man von der affinen zur projektiven Ebene u ugen der Punkte auf einer Ausnahmegeraden ¨ bergeht, die man durch Hinzuf¨ erh¨alt, die unendlich weit“ entfernt liegen, so dass zwei parallele Geraden genau einen gemeinsa” men Punkt auf dieser Ferngeraden haben. Als Beispiele f¨ ur solche dualen“ S¨ atze betrachten ” wir zun¨achst den folgenden Satz:

E A

Satz 11 (Dualer Satz von Pappus) Seien g1 , g2 , g3 und h1 , h2 , h3 jeweils konkurrente Geraden, die sich in P bzw. Q schneiden und A, ..., F die Schnittpunkte A = h1 ∧ g1 , B = g1 ∧ h2 , C = h2 ∧ g2 , D = g2 ∧ h3 , E = h3 ∧ g3 und F = g3 ∧ h1 . Die drei Verbindungsgeraden AD, BE und CF gehen durch einen gemeinsamen Punkt.

D

F B

h3 h1 C h2 P

g3 g1 g2 Q

Dualer Satz von Pappus

Aufgabe 6 Durch eine projektive Transformation kann man die Punkte P und Q auf die Ferngerade legen und bekommt so einen (gleichwertigen) Satz ¨ uber zwei Tripel paralleler Geraden. Formulieren und beweisen Sie diese Aussage.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

12

Da bei projektiven Transformationen zwar keine Kreise erhalten bleiben, aber Quadriken in Quadriken u ¨ bergehen, ist auch der Satz von Pascal eine Aussage der projektiven Geometrie. Vertauscht man hier die Rolle von Punkt“ und Gerade“, so erh¨alt man den Satz von Brian¸con. ” ” Satz 12 (Satz von Brian¸ con) Die Geraden a, b, c, d, e, f m¨ogen eine Quadrik ber¨ uhren, so dass sich benachbarte“ Geraden in den Punkten ” A, B, C, D, E, F schneiden (d.h. ABCDEF ist ein Tangentensechseck). In jedem solchen Tangentensechseck gehen die Diagonalen AD, BE und CF zwischen gegen¨ uber liegenden Eckpunkten durch einen gemeisamen Punkt. Der Satz von Brian¸con

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

2

13

Die Koordinatenmethode

2.1

Grundlegende geometrische Zusammenh¨ ange in koordinatengeometrischer Interpretation

F¨ ur die Visualisierung geometrischer Konfigurationen spielt die Darstellung durch Koordinaten eine zentrale Rolle. Im klassischen Zugang der ebenen Geometrie werden dazu Punkte P durch Koordinaten (p1 , p2 ) im Punktraum A2 dargestellt und Darstellungen anderer geometrischer Objekte daraus abgeleitet. Geraden k¨ onnen etwa durch zwei Punkte, ein kreis durch Zentrum und Peripheriepunkt gegeben werden. Eine kompakte Geradendarstellung ergibt sich durch Tripel g = (g1 , g2 , g3 ), das f¨ ur die Gerade aus den Punkten { (x1 , x2 ) : g1 x1 + g2 x2 + g3 = 0 } steht. Ein solches Tripel bezeichnet man als homogene Koordinaten der Geraden g. Zueinander proportionale Tripel beschreiben dieselbe Gerade g und f¨ ur (echte) Geraden d¨ urfen g1 und g2 nicht gleichzeitig verschwinden. Die wichtigsten geometrischen Eigenschaften von Punkten und Geraden spiegeln sich dann in den folgenden Formeln wider: • A, B, C sind kollinear, d.h. liegen auf einer gemeinsamen Geraden g genau dann, wenn das homogene lineare Gleichungssystem g 1 a1 + g 2 a2 + g 3 = 0 g1 b1 + g2 b2 + g3 = 0 g 1 c1 + g 2 c2 + g 3 = 0 eine (nichttriviale) L¨ osung in (g1 , g2 , g3 ) besitzt, d.h. wenn   a1 a2 1  b1 b2 1 = 0 c1 c2 1

gilt.

• Analog gehen drei Geraden g, h, k durch einen gemeinsamen Punkt genau dann, wenn das lineare Gleichungssystem g1 x1 + g2 x2 + g3 = 0 h1 x1 + h2 x2 + h3 = 0 k1 x1 + k2 x2 + k3 = 0 eine L¨ osung in (x1 , x2 ) besitzt. Das ist genau dann der Fall, wenn die zugeh¨orige Koeffizientenmatrix denselben Rang wie die erweiterte Koeffizientenmatrix hat. Da dieser Rang h¨ochstens 2 sein kann, muss also   g1 g2 g3 det h1 h2 h3  = 0 k1 k2 k3

gelten. Ist der Rang der Koeffizientenmatrix gleich 2, so hat das System dann eine (eindeutig bestimmte) L¨ osung. Ist ihr Rang dagegen gleich 1, d.h. sind ihre drei Zeilen (g1 , g2 ), (h1 , h2 ) und (k1 , k2 ) zueinander proportional, so sind die drei Geraden g, h, k zueinander parallel, schneiden sich also “im Unendlichen” oder fallen zusammen. Geraden, die durch einen gemeinsamen Punkt gehen oder zueinander parallel sind, bezeichnet man als konkurrente Geraden.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

14

• F¨ ur die Parameter einer Geraden durch zwei Punkte A, B erhalten wir aus der Zwei-PunkteGleichung (g1 , g2 , g3 ) = (b2 − a2 , a1 − b1 , a2 b1 − a1 b2 ) • Zwei Geraden g, h sind parallel genau dann, wenn g1 h2 − h1 g2 = 0 gilt, d.h. ihre Normalenvektoren (g1 , g2 ) und (h1 , h2 ) zueinander parallel sind. • Die Parameter der Parallelen h zu g durch einen Punkt P ergeben sich durch Adjustieren des Absolutglieds von g als (h1 , h2 , h3 ) = (g1 , g2 , −(g1 p1 + g2 p2 )). • Die Koordinaten des Schnittpunkts P zweier Geraden g, h berechnet sich als L¨osung des entsprechenden Gleichungssystems nach der Cramerschen Regel zu   g 2 h3 − g 3 h2 g 3 h1 − g 1 h3 (p1 , p2 ) = mit d = g1 h2 − h1 g2 , d d • Ein Punkt X auf der Geraden g = AB hat bei bekanntem Verh¨altnis u = naten (x1 , x2 ) = ((1 − u) a1 + u b1 , (1 − u) a2 + u b2 )

|AX| |AB|

die Koordi-

Dieses Verh¨ altnis u bestimmt die Lage von X auf g relativ zu A, B eindeutig. Wir bezeichnen u = GP (X; A, B) als Gleiterparameter. Liegt X im Inneren der Strecke AB, so gilt 0 < u < 1, f¨ ur Punkte X jenseits von B gilt u > 1 und f¨ ur Punkte jenseits von A schließlich u < 0. |AX| Zum fr¨ uher eingef¨ uhrten Teilverh¨altnis T V (A, B; X) = |XB| besteht der Zusammenhang u T V (A, B; X) = 1−u . Auch Begriffe aus der Euklidschen Geometrie lassen sich symbolisch durch entsprechende Koordinaten ausdr¨ ucken: • So ergibt sich der Abstand zwischen den Punkten A, B aus der Formel p d(A, B) = (a1 − b1 )2 + (a2 − b2 )2 .

Da es sich dabei nicht um einen arithmetischen Ausdruck handelt, wollen wir statt dessen mit dem Abstandsquadrat sqrdist(A, B) = d(A, B)2 arbeiten.

• Zwei Geraden g, h sind orthogonal genau dann, wenn ihre Normalenvektoren (g1 , g2 ) und (h1 , h2 ) senkrecht aufeinander stehen, d.h. f¨ ur das entsprechende Skalarprodukt g 1 h1 + g 2 h2 = 0 gilt. • Schließlich l¨ asst sich das Lot h von P auf die Gerade g ausdr¨ ucken als (h1 , h2 , h3 ) = (g2 , −g1 , g1 p2 − g2 p1 ).

2.2

Homogene Punktkoordinaten

Bei der Betrachtung der Konkurrenz dreier Geraden k¨onnen wir statt nach L¨osungen (x1 , x2 ) des inhomogenen Gleichungssystems g1 x1 + g2 x2 + g3 = 0 h1 x1 + h2 x2 + h3 = 0 k1 x1 + k2 x2 + k3 = 0

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

15

auch nach L¨ osungen (x1 , x2 , x3 ) des homogenen Gleichungssystems g1 x1 + g2 x2 + g3 x3 = 0 h1 x1 + h2 x2 + h3 x3 = 0 k1 x1 + k2 x2 + k3 x3 = 0

(∗)

mit x3 = 1 fragen. Da L¨ osungen homogener Gleichungssysteme durch einen skalaren Faktor variiert werden k¨ onnen, reicht die Existenz von L¨osungen mit x3 6= 0 aus. Solche Koordinaten X = (x1 , x2 , x3 ) bezeichnet man als homogene oder projektive Punktkoordinaten. Sie sind — wie die homogenen Geradenkoordinaten — nur bis auf einen skalaren Faktor verschieden Null eindeutig bestimmt, wobei den affinen Koordinaten (x1 , x2 ) die projektiven Koordinaten (x1 , x2 , 1) entsprechen. Letztere bezeichnen wir auch als normierte Koordinaten und schreiben X. X liegt auf der Geraden g genau dann, wenn g1 x1 + g2 x2 + g3 x3 = 0 gilt. An dieser Formel sieht man schon, dass Punkt- und Geradenkoordinaten in zueinander dualer Weise eingehen, was die fr¨ uher beschriebene Dualit¨at von Punkten und Geraden in S¨atzen der projektiven Geometrie plausibel macht. Die Punkte, f¨ ur deren homogene Koordinate x3 = 0 gilt, liegen auf der Ferngeraden, denn deren homogene Koordinaten lauteten ja gerade (0 : 0 : 1). Wir bezeichnen diese Erweiterung der affinen Ebene A2 um die Punkte der Ferngeraden als projektive Ebene P2 . Bezeichnen wir dual dazu mit P∗2 den Raum der projektiven Geraden, so lassen sich die weiter oben untersuchten geometrischen Beziehungen nennerfrei durch Skalar-, Vektorund Spatproduktoperationen im 3 beschreiben.

R

 a1 • A, B, C in homogenen Punktkoordinaten sind kollinear ⇔ det a2 a3

b1 b2 b3

Notation: |A B C| = 0 (Spatprodukt)

 c1 c2  = 0 c3

• Analog sind drei Geraden g, h, k konkurrent ⇔ |g h k| = 0 • Punkt P und Gerade g sind inzident ⇔ p1 g1 + p2 g2 + p3 g3 = 0 Notation: P ∗ g = 0 (Skalarprodukt) • F¨ ur den Schnittpunkt P zweier Geraden g, h k¨onnen wir die fr¨ uhere Formel nennerfrei interpretieren:   g2 g3 g3 g1 g1 g2 , P = (g2 h3 − g3 h2 , g3 h1 − g1 h3 , g1 h2 − g2 h1 ) = , h2 h3 h3 h1 h1 h2 = (g1 , g2 , g3 ) × (h1 , h2 , h3 ) = g × h

Das sind genau die Koordinaten des Vektorprodukts zweier Vektoren im

R3.

• Die Gleichung einer Geraden durch zwei in homogenen Koordinaten gegebene (verschiedene) Punkte A, B lautet analog g = (a2 b3 − a3 b2 , a3 b1 − a1 b3 , a1 b2 − a2 b1 ) = A × B • A, B, C sind kollinear ⇔ A ist inzident zur Geraden durch B und C ⇔ A ∗ (B × C) = 0. dies stimmt wegen des bekannten Zusammenhangs |A B C| = A ∗ (B × C) zwischen Spat-, Vektor- und Skalarprodukt im

R3 mit obiger Determinantenformel u¨berein.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

16

Homogene Punkt- bzw. Geradenkoordinaten sind genau dann nicht zul¨assig, wenn sich (0 : 0 : 0) ergibt. Aus der Formel f¨ ur die Koordinaten des Schnittpunkts zweier Geraden g, h ist ersichtlich, dass sich nicht zul¨ assige Koordinaten genau dann ergeben, wenn die Koordinaten von g und h proportional sind, d.h. wenn g und h identisch sind. Analog ergeben sich nicht zul¨ assige Geradenkoordinaten f¨ ur die Verbindungsgerade zweier Punkte A und B genau dann, wenn A = B gilt. Auch Parallelit¨ at und Teilverh¨ altnisse kann man ausdr¨ ucken, wenn ber¨ ucksichtigt wird, dass diese Gr¨oßen nicht projektiv invariant sind, d.h. bei ihrer Definition die Ferngerade l0 = (0 : 0 : 1) eine Rolle spielen muss: • Zwei Geraden g, h sind parallel ⇔ sie schneiden sich auf der Ferngeraden, d.h. |g h l0 | = 0. Das stimmt mit unserer weiter oben hergeleiteten Formel u ¨ berein. • Die Gerade h durch P , die parallel zu g verl¨auft, ergibt sich als Verbindung von g × l0 = (−g2 : g1 : 0) und P : h = P × (g × l0 ). • Alle Senkrechten zur Geraden g gehen durch den gemeinsamen Fernpunkt Og = (g1 : g2 : 0), so dass sich die Senkrechte h zu g durch P als h = P × Og = (−p3 g2 : p3 g1 : p1 g2 − p2 g1 ) in ¨ Ubereinstimmung mit der fr¨ uher gefundenen Darstellung ergibt. Mit Parallelen kann man aus einem Standardframe ein ganzes affines Koordinatensystem gewinnen. Als Standardframe bezeichnet man die Punkte e1 = (1 : 0 : 0), e2 = (0 : 1 : 0), e3 = (0 : 0 : 1), u = (1 : 1 : 1). Geometrisch sind e3 der Ursprung des (affinen) Koordinatensystems, e1 , e2 die Fernpunkte in x- bzw. y-Richtung (diese bestimmen zusammen mit e3 die x- und y-Richtung) und u der Einheitspunkt mit den (affinen) Koordinaten (1, 1). Parallelen zur x- bzw. y-Achse durch u schneiden die y- bzw. x-Achse in den Koordinaten-Einheiten und auch andere Teilpunkte auf den Achsen mit ganzzahligen Koordinaten lassen sich leicht konstruieren. Teilverh¨ altnisse: Die Mittelpunktsformel       1 b1 1 a1 m1 + = m2 2 a2 2 b2 gilt f¨ ur homogene Koordinaten nicht mehr, da sie selbst nicht homogen ist. Die richtige Modifikation lautet       m1 a1 b1 m2  = b3 a2  + a3 b2  2 2 m3 a3 b3

und allgemeiner f¨ ur einen Gleiter M auf AB mit Parameter u       b1 a1 m1 m2  = u b3 a2  + (1 − u) a3 b2  b3 a3 m3

Die Ferngerade bildet insgesamt eine Art schwarzes Loch“, denn liegt einer der beiden Rand” punkte dort, so auch M (es gilt stets m3 = a3 b3 ). Wenn beide Randpunkte A und B auf der Ferngeraden liegen, so ergeben sich f¨ ur M unzul¨assige Koordinaten. Die beiden Koeffizienten in der Darstellung M = u b3 A + (1 − u) a3 B ergeben in der Summe nicht mehr unbedingt 1, so dass sich ein Gleiter M auf AB auch als M = µA A + µB B darstellen l¨ asst. In der Tat, ist g = (g1 , g2 , g3 ) die Gerade durch A und B, also g ∗ A = g ∗ B = 0, so gilt g ∗ M = 0 auch f¨ ur jede solche Linearkombination M . Andererseits ergeben Paare (µA , µB ), welche sich nur durch einen skalaren Faktor unterscheiden, verschiedene homogene Koordinaten

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

17

f¨ ur denselben Punkt M , so dass die Punkte auf AB durch das Verh¨altnis µA : µB ∈ P1 eindeutig charakterisiert werden (das Verh¨ altnis ∞ ist m¨oglich und entspricht dem Punkt A). Dieses Verh¨altnis ist f¨ ur a3 = b3 = 1 gerade das fr¨ uher eingef¨ uhrte Teilverh¨altnis T V (A, B; M ), wie sich ¨ durch Ubergang zu normierten Koordinaten auch f¨ ur M leicht nachrechnen l¨asst. Allgemein gilt T V (A, B; M ) =

µA /µB , a3 /b3

denn aus M = µA A + µB B folgt f¨ ur normierte Koordinaten m3 M = µA a3 A + µB b3 B mit m3 = µA a3 + µB b3 . Das Teilverh¨ altnis ist also keine projektive Invariante, sondern h¨angt von der speziellen Wahl der homogenen Koordinaten von A und B ab. Invariant wird erst das Doppelverh¨altnis DV (A, B; M, N ) = T V (A, B; M ) : T V (A, B; N ), wobei N = νA A + νB B ein weiterer Punkt auf der Geraden AB ist: DV (A, B; M, N ) =

µA /µB νA /νB

Durch das Verh¨ altnis µA /µB werden also die Punkte M ∈ AB eindeutig parametrisiert, aber ihre genaue Lage nicht absolut beschrieben, sondern nur relativ zueinander. H¨alt man allerdings einen weiteren Punkt auf der Geraden fest, so beschreibt das Teilverh¨altnis die Lage auch absolut. Das Teilverh¨ altnis kann etwa als Doppelverh¨altnis mit N = F , dem Fernpunkt auf der Geraden AB, geschrieben werden: Wegen F = −b3 A + a3 B ergibt sich T V (A, B; M ) = −DV (A, B; M, F ). Hieraus folgt, dass projektive Transformationen, welche die Ferngerade fest lassen (also genau die affinen Transformationen), auch teilverh¨altnisinvariant sind.

2.3

Zur Algorithmisierung geometrischer Konstruktionen. Analytische Geometrie mit dem Computer

Wir k¨onnen auf der Basis der im Abschnitt 2.1 hergeleiteten Beziehungen nun in einer klassischen imperativen Programmiersprache (die an dieser Stelle noch nicht u ¨ ber die F¨ahigkeit zur Symbolverarbeitung verf¨ ugen muss) Funktionen schreiben, die in der Lage sind, Beziehungen in durch konkrete Koordinatenwerte vorgegebenen geometrischen Konfigurationen zu u ufen oder ge¨berpr¨ suchte Gr¨ oßen auszurechnen. Entsprechende Funktionen sind auch die Grundlage f¨ ur dynamische Geometriesysteme, mit denen entsprechende Konfigurationen grafisch dargestellt werden k¨onnen. Die elementaren geometrischen Objekte Punkt und Gerade setzen wir dazu als Klassen Point und Line um, die in Java etwa als public class Point { public Scalar x,y; public Point () { } public Point(Scalar x, Scalar y) { this.x=x; this.y=y; } ... }; public class Line { public Scalar a,b,c; public Line () {}

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

18

public Line(Scalar a, Scalar b, Scalar c) { if (iszero(a) & iszero(b) & iszero(c)) throw new GeoException("Gerade mit Nullkoordinaten"); this.a=a; this.b=b; this.c=c; } ... }; definiert werden k¨ onnen und Punkte P (x1 , x2 ) bzw. Geraden g = {(x1 , x2 ) : g1 x1 + g2 x2 + g3 = 0} darstellen. Scalar ist dabei der Grundbereich, aus dem die Werte der Koordinaten kommen, also in Java etwa der interne Typ double oder etwas Selbstgestricktes wie Rational oder Complex. Wir wollen annehmen, dass es sich um einen K¨orper handelt, also f¨ ur diesen Datentyp die arithmetischen Operationen + − ∗ / sowie ein boolesches Pr¨adikat boolean iszero() definiert sind. Geometrische Grundkonstruktionen k¨onnen wir in diesem Kontext als Funktionen auffassen, die aus gegebenen Objekten neue konstruieren, und in einer weiteren Klasse GeoFunctions als Klassenfunktionen b¨ undeln. 1) Die Gerade durch zwei Punkte P und Q public static Line pp_line(Point p, Point q) { return new Line(q.y-p.y, p.x-q.x, p.y*q.x-p.x*q.y); } P und Q sind dabei als formale Parameter vom Typ Point Container f¨ ur die aktuellen Koordinaten, der R¨ uckgabewert der Funktion vom Typ Line der Container f¨ ur die berechneten Koodinaten des davon abh¨ angenden Objekts. 2) Analog k¨ onnen wir den Schnittpunkt zweier Geraden berechnen, wobei die zu definierende Funktion mit einer Ausnahme abbricht, wenn kein bzw. kein eindeutig bestimmter Schnittpunkt existiert. public static Point intersection_point(Line g, Line h) { Scalar d = g.a*h.b-g.b*h.a; if (iszero(d)) throw new GeoException("Geraden sind parallel"); return new Point((g.b*h.c - g.c*h.b)/d,(g.c*h.a - g.a*h.c)/d); } Auch hier sind g und h formale Parameter, diesmal vom Typ Line. 3) F¨ ur das Lot l von einem Punkt P auf eine Gerade g erhalten wir analog public static Line ortho_line(Point p, Line g) { return new Line(g.b, -g.a, g.a*p.y - g.b*p.x); } und f¨ ur die Parallele zu einer Geraden g durch einen Punkt P public static Line par_line(Point p, Line g) { return new Line(g.a, g.b, -(g.a*p.x + g.b*p.y)); } Das Abstandsquadrat ergibt sich schließlich als public static Scalar sqrdist(Point p, Point q) { return new Scalar((p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y)); }

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

19

4) Neben freien Punkten, die mit dem Punktkonstruktor erzeugt werden k¨onnen, sind auch Punkte auf vorgegebenen Geraden (Geradengleiter) oder Kreisen (Kreisgleiter) interessant. Einen Geradengleiter auf einer durch zwei Punkte gegebenen Geraden kann man etwa durch ein variables Teilverh¨ altnis festlegen: public static Point varpoint(Point P, Point Q, Scalar u) { return new Point((1-u)*p.x+u*q.x,(1-u)*p.y+u*q.y); } Insbesondere liefert Point midpoint(Point P,Point Q) { return varpoint(P,Q,new Scalar(1/2)); } den Mittelpunkt der Strecke P Q. 5) Komplexere geometrische Konstruktionen (Makros) k¨onnen aus nacheinander ausgef¨ uhrten Grundkonstruktionen zusammengesetzt werden. Dem entsprechen auf der Seite der Programmiersprachen zusammengesetzte Funktionen. So findet man etwa den Fußpunkt des Lots vom Punkt P auf die Gerade a als public static Point pedalpoint(Point P, Line a) { return intersection_point(ortho_line(P,a),a); } Aufgabe 7 Geben Sie entsprechende Funktionen an • Line p bisector(Point A, Point B) f¨ ur die Mittelsenkrechte (perpendicular bisector) auf der Seite AB, • Line altitude(Point A, Point B, Point C) f¨ ur die H¨ohe durch A im Dreieck ABC, • Line median(Point A, Point B, Point C) f¨ ur die Seitenhalbierende, die durch A im Dreieck ABC verl¨auft. 6) Schließlich kann man testen, ob f¨ ur gewisse Konfigurationen geometrische Bedingungen erf¨ ullt sind. So kann man etwa testen, ob zwei gegebene Geraden g und h parallel oder orthogonal sind, indem man pr¨ uft, ob g1 h2 − g2 h1 bzw. g1 h1 + g2 h2 verschwindet, oder ob ein Punkt P auf einer Geraden g liegt. Entsprechende Funktionen haben folgende Spezifikation: public static boolean is_parallel(Line g, Line h) { return iszero(g.a*h.b-h.a*g.b); } bzw. public static boolean is_orthogonal(Line g, Line h) { return iszero(g.a*h.a+g.b*h.b); } public static boolean is_point_on_line(Point P, Line g) { return iszero(g.a*P.x+g.b*P.y+g.c); } Auch kompliziertere Bedingungen, die wir im letzten Paragraph hergeleitet hatten, kann man auf diese Weise pr¨ ufen, so z.B., ob drei gegebene Punkte P, Q, R kollinear oder drei gegebene Geraden a, b, c konkurrent sind. Die entsprechenden Funktionen is collinear und is concurrent lassen sich leicht angeben.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

20

Aufgabe 8 F¨ uhren Sie die Implementierung entsprechender Funktionen wie oben begonnen in Java zu Ende. Mit diesem Arsenal kann man die Koordinaten auch komplizierterer geometrischer Objekte bestimmen und entsprechende geometrische S¨atze in konkreten Konfigurationen u ufen. ¨ berpr¨ Beispiel 1: Der Satz vom Schnittpunkt der Mittelsenkrechten. Die Funktion static boolean CircumCenter_Test1(Point A, Point B, Point C) { return is_concurrent(p_bisector(A,B), p_bisector(B,C), p_bisector(C,A)); } pr¨ uft, ob f¨ ur ein Dreieck, das durch seine Eckpunkt(koordinaten) A, B, C gegeben ist, die drei Mittelsenkrechten durch einen gemeinsamen Punkt gehen. Alternativ kann man wie im elementargeometrischen Beweis dieses Satzes auch zuerst die Koordinaten des Schnittpunkt zweier der Mittelsenkrechten bestimmen und dann zeigen, dass dieser Punkt auf der dritten Mittelsenkrechten liegt: static boolean CircumCenter_Test2(Point A, Point B, Point C) { Point M = intersection_point(p_bisector(A,B), p_bisector(B,C)); return on_line(M, p_bisector(C,A)); } Letztere Funktion l¨ asst sich zu eine Test erweitern, der zeigt, dass dieser Schnittpunkt der Mittelpunkt des Umkreises des Dreiecks ∆ ABC ist. Dazu ist sqrdist(M, A) = sqrdist(M, B) = sqrdist(M, C) zu testen, d.h. die letzte Zeile durch return iszero(sqrdist(M,A) - sqrdist(M,B)) & iszero(sqrdist(M,B) - sqrdist(M,C)); zu ersetzen. Aufgabe 9 Geben Sie analoge Testfunktionen f¨ ur die S¨atze vom Schnittpunkt der H¨ohen bzw. der Seitenhalbierdenden. Lassen Sie auch testen, dass die Produkte aus den H¨ohenabschnitten im Dreieck gleich sind bzw. der Schnittpunkt der Seitenhalbierenden diese im Verh¨altnis 2:1 teilt. Beispiel 2: Der Satz von der Eulerschen Geraden: static boolean EulerLine_Test(Point A, Point B, Point C) { Point M = intersection_point(p_bisector(A,B), p_bisector(B,C)); Point H = intersection_point(altitude(A,B,C), altitude(B,C,A)); Point S = intersection_point(median(A,B,C), median(B,C,A)); return is_collinear(M,H,S); } Aufgabe 10 Modifizieren Sie diese Testfunktion so, dass sie den Satz vom Feuerbachschen Kreis testet. (Feuerbach Test(Point A, Point B, Point C)) Testen Sie den (affinen) Satz von Desargue.(Desargue Test(Point A, Point B, Point C))

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

2.4

21

Zum grunds¨ atzlichen Aufbau einer dynamischen Geometrie-Software (DGS)

Wir wollen uns an dieser Stelle auf die Betrachtung von Punkten und Geraden in der Ebene E beschr¨anken und die grundlegenden informatischen Begriffe entwickeln, die f¨ ur das Verst¨andnis einer DGS erforderlich sind, sowie deren Verh¨altnis zu anderen Begriffen und Konzepten der Informatik insgesamt herausarbeiten. Im letzten Abschnitt hatten wir bereits gesehen, dass sich das Attribute und Methoden b¨ undelnde Klassen- und Instanzenkonzept des objektorientierten Programmierens gut f¨ ur DGS eignet. Es erlaubt die Kapselung von durch Koordinaten gegebener geometrischer Gebilde in neuen Sinneinheiten. Die in der Informatik u ¨bliche Unterscheidung von abstrakter Identit¨at eines Objekts und dessen sich im Laufe der Zeit ¨ andernden Objektzustands spielt f¨ ur DGS eine wichtige Rolle. Wie bei Variablen haben wir dabei zu unterscheiden zwischen dem Objekt als Container des Zustands (dieser wird in den Attributen des Objekt dargestellt) und dem sich u ¨ ber die Zeit ¨andernden Zustand selbst (also den Attributwerten). Ist g.c also ein Attribut eines Objekts g mit Werten in einem Bereich C, so wird in der Attributdeklaration public CType c von g Speicherplatz f¨ ur das Attribut g.c reserviert, der dann konkrete Werte g.c ∈ C aufnehmen kann. Dieser Wert kann sich u andern, was als g.c(t) ∈ C f¨ ur einen Zeitparameter t ∈ T oder gleich als ¨ ber die Zeit ¨ Attributwertfunktion g.c : T → C dargestellt werden kann. Attributwerte k¨ onnen also einmal als spezielle Werte aus einem Wertebereich C, zum anderen als Werte aus einem Funktionenraum FC = Map(T , C) verstanden werden. Arithmetische Operationen auf C lassen sich zu solchen auf FC fortsetzen, indem etwa f¨ ur Funktionen f, g ∈ FC die Summe f + g ∈ FC punktweise durch (f + g)(c) = f (c)+ g(c) definiert wird. Der Definitionsbereich D(f + g) dieser Verkn¨ upfung ergibt sich als Durchschnitt der Definitionsbereiche D(f )∩D(g) bzw. im Fall eines Quotienten als D(f /g) = D(f ) ∩ D(g) \ V (g = 0). Dabei kann es passieren, dass der Definitionsbereich der Verkn¨ upfung leer ist, etwa im Fall, dass f und g disjunkte Definitionsbereiche haben. Auf diese Feinheiten gehen wir hier aber nicht ein. Das Bewegen geometrischer Objekte kann die Bewegung anderer geometrischer Gebilde zur Folge haben – Zustands¨ anderungen propagieren also durch ein Netz von Abh¨angigkeiten. Diese Abh¨angigkeiten werden durch Formeln beschrieben, nach denen die Koordinaten des abh¨angigen Objekts aus denen der Vaterobjekte bestimmt werden kann, so dass es sich um Abh¨angigkeiten zwischen den Objekten selbst handelt. Wir f¨ uhren deshalb die folgende begriffliche Unterscheidung ein: Definition 1 Die Klassen Punkt und Gerade bezeichnen wir als geometrische Typen, Instanzen einer solchen Klassen als geometrische Objekte. Jeden Objektzustand eines solchen geometrischen Objekts bezeichnen wir als spezielles geometrisches Objekt. Geometrische Objekte haben eine abstrakte Identit¨at, die wir an Bezeichner binden k¨onnen. Spezielle geometrische Objekte sind konkrete Auspr¨agungen dieser abstrakten Identit¨at in Raum und Zeit. F¨ ur jeden geometrischen Typ T spezifizieren wir ein spezielles Attribut c vom Typ CT , welches die Koordinaten des jeweiligen Objekts enth¨alt, und bezeichnen dieses als Koordinatenattribut. Ist etwa g ∈ Line ein Objekt vom Typ Gerade, so steht g.c f¨ ur das Koordinatenattribut von g. Wie oben haben wir zu unterscheiden zwischen dem Attribut g.c selbst als informatischem Begriff, konkreten Attributwerten g.c ∈ CL oder g.c(t) ∈ CL f¨ ur t ∈ T und der Attributwertfunktion g.c ∈ FL , welche die zeitliche Existenz von g in ihrer Gesamtheit beschreibt. CL ist dabei der Bereich der (f¨ ur Geraden zul¨assigen) Koordinatenwerte, FL = Map(T , CL ) der zugeh¨orige Funktionenraum. Beides h¨ angt nicht von g selbst, sondern nur vom geometrischen Typ g ∈ Gerade und nat¨ urlich vom gew¨ ahlten Koordinatenmodell ab. Das Modell der homogenen

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

22

¨ Geradenkoordinaten l¨ asst sich als Menge von Aquivalenzklassen
CL = K 3 \ {(0, 0, 0)} / ∼

bzgl. der Relation

(x, y, z) ∼ (x′ , y ′ , z ′ ) ⇔ ∃ c ∈ K ∗ : x′ = c x, y ′ = c y, z ′ = c z oder kurz als Menge der nichttrivialen Orbits der Aktion der multiplikativen Gruppe K ∗ auf K 3 beschreiben. Ein solches Koordinatenmodell basiert stets auf einem Grundbereich K, aus welchem die Werte der Koordinaten kommen. Wir wollen stets voraussetzen, dass K ein algebraisch abgeschlossener K¨ orper mit char(K) = 0 ist. DGS sind als grafische Anwendungen sinnvollerweise nach dem Modell-View-Controler-Konzept aufgebaut, wobei der Controler mit dem View vereinigt sein kann. Mausaktionen werden vom View u ¨ber den Controler an das Modell weitergegeben, dort die entsprechenden Berechnungen aktualisiert, und schließlich u ¨ ber den Controler (oder auch direkt u ¨ber Event-Steuerung) an den View der Befehl zu einem (re)paint gegeben. In diesem Kontext ist g als geometrisches Objekt auf der Modell-Seite, die speziellen geometrischen Objekte g(t) auf der View-Seite zu finden. Geometrische Objekte werden durch entsprechende Konstruktionswerkzeuge Schritt f¨ ur Schritt erzeugt, welche auf der Seite der Informatik als Funktionen daherkommen. F¨ ur Funktionen haben wir zwischen Funktionsdefinition und Funktionsaufruf zu unterscheiden, wobei in einer Funktionsdefinition formale Parameter als Platzhalter f¨ ur geometrische Objekte als Aufrufargumente auftreten. Die Dynamik eines so neu konstruierten geometrischen Objekts ergibt sich aus der Dynamik der geometrischen Objekte, welche an der Konstituierung beteiligt waren, und der Spezifik des Konstruktionswerkzeugs selbst. Diese Werkzeuge sind prototypisch von zwei verschiedenen Arten. Prototyp 1: Point H = pedalpoint(Point P, Line a) Mit diesem Aufruf des Werkzeugs pedalpoint wird aus zwei vorhandenen geometrischen Objekten P ∈ Point und a ∈ Line ein neues geometrisches Objekt H ∈ Point erzeugt, dessen Dynamik H.c ∈ FP sich aus den Dynamiken P.c ∈ FP und a.c ∈ FL als Zusammensetzung P.c×a.c

φ

H.c = φ ◦ (P.c × a.c) : T −−−−−→ CP × CL −−−−→ CP ergibt, wobei φ : CP × CL → CP beschreibt, wie aus den Koordinaten von P und a diejenigen von F zu berechnen sind. Prototyp 2: Point M = varpoint(Point A, Point B, X u) Hier h¨angt M noch zus¨ atzlich von einem Stellparameter u ab, dessen Natur X wir nun n¨aher spezifizieren wollen. Ein Vergleich mit Prototyp 1 zeigt, dass u hier in derselben Doppelbedeutung wie ein geometrisches Objekt auch auftritt: Einerseits als abstrakte Identit¨at eines Stellparameters, welcher selbst eine zeitliche Dynamik hat, und andererseits als Eingangsparameter, welcher die Dynamik von M beeinflusst. u bestimmt diese Dynamik aber nur relativ zu A und B, denn ein ¨ Bewegen eines dieser Punkte ohne Anderung des Stellparameters u ¨andert die Lage des speziellen geometrischen Objekts M ebenfalls. X steht also f¨ ur einen weiteren Datentyp eines Stellparameters SP, dessen Wertebereich im Koordinatenmodell der homogenen Punktkoordinaten liegt. In Analogie zu den geometrischen Objekten bezeichnen wir einen solchen Typ als Parametertyp und Instanzen u dieses Typs als Parameterobjekte. Ein solches Parameterobjekt hat einerseits eine abstrakte Identit¨at und andererseits einen zeitlichen Verlauf u.c ∈ FS = F (CS ) mit Werten aus dem (skalaren) Parameterbereich CS (S wie Stellparameter). Diese Funktion bezeichnen wieder als Parameterfunktion, einen konkreten Wert u.c(t) ∈ CS als speziellen Parameter. Wir k¨onnen uns die Entkopplung von der visuellen Darstellung als Bewegen mit der Maus“ etwa ” als Schieberegler vorstellen, dessen Schieben den Punkt M auf der Geraden AB bewegt. Eine solche

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

23

Trennung ist auch bei freien Punkten sinnvoll, da f¨ ur diese ebenfalls eine mittelbare Steuerung der Bewegung denkbar w¨ are1 . Allerdings haben freie Punkte zwei Freiheitsgrade, so dass hierf¨ ur noch ein zweiter Parametertyp MP mit einem Parameterbereich CM (M wie Mausparameter) und einem Funktionenraum FM ben¨ otigt wird. Mit diesen zus¨ atzlichen Definitionen k¨onnen wir nun eine einheitliche Definition eines Konstruktionswerkzeugs geben, welche davon ausgeht, dass gen¨ ugend Parameterobjekte zur Verf¨ ugung stehen, aber selbst das Anlegen eines einzigen freien Punktes durch ein Konstruktionswerkzeug geschieht (und so ist es ja praktisch auch). Die gesamte Dynamik der Konstruktion ist in den Parameterobjekten gekapselt. Allerdings werden auch konstante“ Parameterobjekte ben¨otigt, wenn ” wir z. B. den Mittelpunkt einer Strecke als varpoint(A,B,1/2) konstruieren wollen. Diese Implementierungsfeinheiten von Parameterobjekten sollen hier aber nicht diskutiert werden. Definition 2 Seien T1 , . . . , Tn geometrische oder Parametertypen, Ta ein geometrischer Typ und C1 , . . . , Cn , Ca die zugeh¨origen Wertebereiche. Als Konstruktionswerkzeug w bezeichnen wir eine (informatische) Funktion der Signatur w : (T1 × . . . × Tn ) → Ta zusammen mit einer mathematischen Funktion w.c : (C1 × . . . × Cn ) → Ca , so dass f¨ ur Objekte oi ∈ Ti der richtigen Typen, also oi .c ∈ Ci , und oa = w(o1 , . . . , on ) ∈ Ta oa .c = w.c(o1 .c, . . . , on .c) ∈ Ca gilt. Weiter sei w e = id × w : (T1 × . . . × Tn ) → (T1 × . . . × Tn × Ta )

der Graph von w, also die Abbildung, welche die Aufrufargumente mit in das R¨ uckgabetupel aufnimmt, und w.c e entsprechend der Graph von w.c. w.c induziert eine Funktion

F (C1 ) × . . . × F (Cn ) → F (Ca ),

welche die Dynamik des Koordinatenattributs von oa in Abh¨angigkeit der Dynamiken der Koordinatenattribute von o1 , . . . , on beschreibt. w.c ist die Berechnungsvorschrift, nach welcher bei ¨ Anderung der Eingabewerte o1 .c, . . . , on .c der Ausgabewert oa .c neu zu berechnen ist. Eine weitere Feinheit haben wir dabei noch nicht ber¨ ucksichtigt: Ist z.B. Line g = pp line(Point A, Point B) das Konstruktionswerkzeug, welches zu zwei gegebenen Punkten die Gerade durch diese Punkte konstruiert, so ist f¨ ur spezielle Punkte A und B diese Gerade nur definiert, wenn diese nicht zusammenfallen. pp line.c : CP × CP −→ CL ist also nur eine partiell definierte Funktion. Die Ausnahmemenge wird durch ein boolesches Pr¨adikat pp line.DG : CP × CP −→ Boolean bestimmt, welches in unserem Fall die einfache Form pp line.DG(c1 , c2 ) = isequal(c1 , c2 ) hat. Hierbei ist Boolean der Wertebereich des Datentyps boolean. 1 Das ist auch praktisch so: Die Koordinaten des Mauszeigers werden auf der View-Seite in Fensterkoordinaten abgegriffen und auf der Modell-Seite in Weltkoordinaten umgerechnet.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

24

Definition 3 Zu jedem Konstruktionswerkzeug w gibt es weiter eine Degenerationsbedingung w.DG : (C1 × . . . × Cn ) → Boolean, so dass w.c genau auf denjenigen Werten (c1 , . . . , cn ) ∈ C1 × . . . × Cn definiert ist, f¨ ur welche w.DG(c1 , . . . , cn ) = false gilt. Beispiele: freePoint: MP → Point legt einen freien Punkt an. pp line: Point×Point → Line erzeugt die Gerade durch zwei gegebene Punkte. ur c1 , c2 ∈ CP . Die zugeh¨ orige Degenerationsbedingung ist pp line.DG(c1 , c2 ) = isequal(c1 , c2 ) f¨ intersection point: Line×Line → Point erzeugt den Schnittpunkt zweier Geraden. Die zugeh¨ orige Degenerationsbedingung ist intersection point.DG(a, b) = is parallel(a, b) f¨ ur a, b ∈ CL . Konstruktionswerkzeuge werden eingesetzt, um mit ihnen eine geometrische Konfiguration schrittweise aufzubauen, wobei neu erzeugte geometrische Objekte von bereits vorhandenen sowie von Parameterobjekten abh¨ angen. Diese Abh¨angigkeitsverh¨altnisse lassen sich durch einen (endlichen) gerichteten azyklischen Graphen (DAG) darstellen und intern durch Ereignispropagation modellieren. Auch auf dieser Ebene wollen wir zwischen Definition und Aufruf unterscheiden, da die Abh¨angigkeitsverh¨ altnisse zwischen Ein- und Ausgabegr¨oßen der Konstruktionswerkzeuge auf der Ebene der geometrischen Typen und nicht der geometrischen Objekte liegen. Definition 4 Als Konfiguration bezeichnen wir deshalb einen Abh¨angigkeitsgraphen Γ = (T, E) zwischen Typen. Ein Tupel O = (oτ ∈ τ | τ ∈ T ) dazu passender spezieller Objekte der korrekten Typen bezeichnen wir als Realisierung der Konfiguration Γ. Wir bezeichnen weiter Γ = (T, E) als Parameterkonfiguration, wenn T ausschließlich Parametertypen enth¨alt. Damit k¨ onnen wir nun den Begriff der Konstruktion schrittweise herleiten. Definition 5 Sei Γ = (T, E) ein Konfiguration und w : (T1 × . . . × Tn ) → Ta ein Konstruktionswerkzeug. w ist auf Γ anwendbar, wenn es eine Belegung f : [1 . . . n] → T mit f (i) = Ti gibt. Als Konstruktionsschritt bezeichnen wir in diesem Fall die Sequenz folgender Aktionen: 1. Auswahl einer solchen Belegung f , 2. Erg¨anzung von Γ zu Γ′ = (T ∪ {Ta }, E ∪ {(Ti , Ta ), i = 1, . . . , n}). Ist O = (oτ ∈ τ | τ ∈ T ) eine Realisierung von Γ und oi = of (i) , so bezeichnen wir die Sequenz folgender Aktionen als Ausf¨ uhrung des Konstruktionsschritts:

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

25

1. Anwendung des Konstruktionswerkzeugs zur Erzeugung von oa = w(o1 , . . . , on ) ∈ Ta , 2. Erg¨anzung von O zu O′ = O ∪ {oa }. Es ist sinnvoll, als Belegung f nicht nur injektive Funktionen zuzulassen. So kann etwa das Konstruktionswerkzeug altitude(A, B, C), welches die H¨ohe durch A im Dreieck △ ABC konstruiert, auch f¨ ur A = B sinnvoll angewendet werden, um eine Senkrechte in B zu errichten. In all diesen Definitionen ist es m¨ oglich, den Begriff des Konstruktionswerkzeugs so zu fassen, dass statt eines einzelnen Objekts oa gleich ein ganzes Tupel (oa1 , . . . , oam ) von Objekten konstruiert wird, deren Typen (Ta1 , . . . , Tam ) vorgegeben sind. Ein solches Konstruktionswerkzeug bezeichnen wir als verallgemeinertes Konstruktionswerkzeug. Definition 6 Als Konstruktion K bezeichnen wir eine Folge von Konstruktionsschritten, welche die Startkonfiguration ΓS = (TS , ES ) durch endlich viele konsekutive Konstruktionsschritte ΓS = Γ0 → Γ1 → . . . → ΓN = ΓE

(∗)

mit der Endkonfiguration ΓE = (TE , EE ) verbindet. Ist OS = (oτ ∈ τ | τ ∈ TS ) eine Realisierung von ΓS , so bezeichnen wir die Herstellung der Realisierung OE = (oτ ∈ τ | τ ∈ TE ) von ΓE durch sukzessives Anwenden der Konstruktionsschritte als Anwenden der Konstruktion auf OS . Wir schreiben auch kurz OE = K(OS ). Die Folge der Konstruktionsschritte, in welchen die Konfiguration Γ entsteht, bezeichnen wir als Konstruktionsbeschreibung. Als Zeichnung bezeichnen wir schließlich die Anwendung einer Konstruktion auf eine Realisierung einer Parameterkonfiguration (also ein weißes Blatt“). ” Die Definition zeigt, dass zusammen mit (∗) auch jede Teilfolge ΓS = Γ0 → Γ1 → . . . → Γi eine Konstruktion ist. Wir bezeichnen sie als Teil- oder Zwischenkonstruktion K(i) . Die dynamischen Freiheitsgrade einer Konstruktion werden allein durch deren Parameterobjekte bestimmt, sind also bereits in der Startkonfiguration festgelegt. Jede Konstruktionsbeschreibung ist zugleich ein verallgemeinertes Konstruktionswerkzeug, was die Einf¨ uhrung des Konzepts von Makros erm¨oglicht: F¨ ur ein verallgemeinertes Konstruktionswerkzeug w : T1 × · · · × Tn → U1 × · · · × Um kann man w aus dem Abbildungsgraphen w e = id × w : T1 × · · · × Tn → T1 × · · · × Tn × U1 × · · · × Um

von w durch Projektion auf die U -Komponenten gewinnen. Dasselbe gilt f¨ ur die Koordinatenabbildungen w.c. e Ist nun w e

w e

w e

2 1 → . . . −−−N−→ ΓN = ΓE → Γ1 −−−− ΓS = Γ0 −−−−

die Folge von Konstruktionsschritten, welche eine Konstruktion K beschreibt, so beschreibt Y Y w eK = w eN ◦ · · · ◦ w e1 : (τ ∈ TS ) −→ (τ ∈ TE ) das zugeh¨ orige verallgemeinerte Konstruktionswerkzeug.

Die zugeh¨ orige Degenerationsbedingung ergibt sich analog als oder-Verkn¨ upfung aus den Abbildungen (i)

w eK .DG :

Q

w ei−1 .c ◦···◦ w e1 .c

(C(τ ) : τ ∈ TS ) −−−−−−−−−−→

Q

w .DG

i (C(τ ) : τ ∈ T (Γi−1 )) −−− −→ Boolean

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

26

f¨ ur i = 1, . . . , N , in welcher die Ausf¨ uhrbarkeit der i-ten Teilkonstruktion kodiert ist. Konstruktionsbeschreibungen werden wir in der formalen Notation eines geometrischen Linearprogramms (GLP) angeben. Ein solches Programm enth¨alt in den ersten Zeilen die Startkonfiguration. Danach folgt die Angabe der einzelnen Konstruktionsschritte, wobei die Angabe der Belegung des entsprechenden Konstruktionswerkzeugs u ur die konstruierten geo¨ ber Bezeichner f¨ metrischen Objekte ohne Vorw¨ artsreferenzen erfolgt. Die Konstruktion eines durch drei freie Punkte aufgespannten Dreiecks l¨asst sich damit wie folgt beschreiben: MP u1 , u2 , u3 ; Point A = freePoint(u1); Point B = freePoint(u2); Point C = freePoint(u3); Line a = pp line(B,C); Line b = pp line(A,C); Line c = pp line(A,B); Sind in solchen GLP als Abk¨ urzungen geschachtelte Funktionsaufrufe wie folgt erlaubt Point F = intersection point(pp line(B,C),ortho line(A,pp line(B,C))); so sprechen wir von der schwachen GLP-Notation. Sind als Parameter in einem Konstruktionswerkzeug nur Bezeichner zugelassen, so sprechen wir von der strengen GLP-Notation. In obigem Beispiel ist F der Lotfußpunkt der H¨ohe durch A im Dreieck △ ABC. Jedes GLP in schwacher Notation kann ohne Schwierigkeiten durch Einf¨ uhrung anonymer geometrischer Objekte in die strenge Notation u berf¨ u hrt werden (und dies wird intern bei der geometrischen Darstellung ¨ einer solchen Konfiguration auch ausgef¨ uhrt). Obiger Schritt kann wie folgt in eine Sequenz von Konstruktionsschritten entschachtelt werden: Line l1 = pp line(B,C); Line l2 = ortho line(A, l1); Point F = intersection point( l1, l2); Dies kann sogar automatisch geschehen, wenn man zul¨asst, dass dasselbe geometrische Objekt ” mehrfach konstruiert wird“.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

3 3.1

27

Geometrie und Formeln Symbolische analytische Geometrie

Ist das geometrische Objekt o = w(o1 , . . . , on ) mit dem Konstruktionswerkzeug w konstruiert worden, so berechnet sich der Wert des Koordinatenattributs von o zum Zeitpunkt t aus den aktuellen Werten der Koordinatenattribute von o1 , . . . , on als o.c(t) = w.c(o1 .c(t), . . . , on .c(t)). Dabei sind jedesmal dieselben Rechnungen w.c mit je anderen Werten, also eine allgemeine Berechnungsvorschrift auszuf¨ uhren. Ist allgemeiner w e

w e

w e

2 1 → . . . −−−N−→ ΓN = ΓE → Γ1 −−−− K : ΓS = Γ0 −−−− eine Konstruktion und OS eine Realisierung der Startkonfiguration, so berechnen sich die Koordinatenwerte der zugeh¨ origen Endkonfiguration OE = K(OS ) nach einer Berechnungsvorschrift, die sich als Zusammensetzung w eN .c ◦ · · · ◦ w e1 .c der Berechnungsvorschriften der einzelnen Konstruktionsschritte ergibt.

Damit entsteht die Frage, ob sich diese h¨aufig auszuf¨ uhrenden Berechnungsvorschriften durch gleichwertige, aber effizienter auszuf¨ uhrende ersetzen lassen. Aus Sicht der Informatik w¨are insbesondere u ¨ ber eine compilierte Form nachzudenken, was eine DGS mit entsprechenden F¨ahigkeiten ¨ zur inkrementellen Ubersetzung erfordert. Dieser Ansatz soll uns hier nicht weiter interessieren. Wir wollen stattdessen eingeschr¨ ankte Klassen von Funktionen betrachten, auf die sich unsere Anwendungen bisher immer reduzieren ließen: Die Koordinaten von o.c sollen sich durch arithmetische Operationen aus den Koordinaten von o1 .c, . . . , on .c berechnen lassen. Da in eine Konstruktion nur endlich viele Parameterobjekte eingehen und diese die einzige Quelle der Dynamik der Konstruktion sind, l¨ asst sich jede Berechnungsvorschrift durch arithmetische Operationen aus Kernen aufbauen, die nur die Koordinatenwerte γa der Parameterobjekte enthalten.

Ersetzen wir diese Kerne durch Variablen xa , so wird aus der Berechnungsvorschrift eine Formel A der Termalgebra k(xa ) und wir k¨ onnen nach Vereinfachung dieser Formel zu einer Formel A′ in der Termalgebra fragen. Die Berechnungsvorschrift l¨asst sich aus der Formel durch die Substitution s = {xa → γa } zur¨ uckgewinnen. Die Vereinfachung der Formel A zur Formel A′ in der Termalgebra ist nat¨ urlich nur dann interessant, wenn die zugeh¨origen Berechnungsvorschriften subs(A, s) und subs(A′ , s) berechnungs¨ aquivalent sind, d. h. dasselbe berechnen. Im Rahmen eines CAS kann die Umwandlung einer Formel in eine Berechnungsvorschrift durch Ersetzen der Variablen durch Zahlenwerte mit dem Substitionsoperator erreicht werden, da bei der Auswertung der Formel mit Zahlenwerten die enstprechenden Operationen als Funktionsaufrufe interpretiert werden. Dabei kann es allerdings geschehen, dass die Berechnung mit einem Fehler (Ausnahme) abbricht. Entsprechende Implementierungen stehen f¨ ur Maple, MuPAD, Reduce und Mathematica mit den GeoProver-Paketen [3] zur Verf¨ ugung. Die Pakete implementieren einen gemeinsamen Sprachstandard f¨ ur Geometriebeweise, dessen Syntax in der GeoCode-Tabelle des SymbolicData-Projekts [4] fixiert ist und unterscheiden in der Version 1.3 (noch) nicht zwischen w und w.c. Kleinere Syntaxunterschiede zwischen den Sprachen der Target-CAS machen außerdem ein gemeinsames ¨ Oberformat und entsprechende Ubersetzungswerkzeuge erforderlich. Hier ist eine Migration nach XML in Arbeit. Wir bezeichnen die Formel A bzw. A′ als universelle Formel der zum Werkzeug w geh¨orenden Berechnungsvorschrift w.c. Da in die Berechnung w.c die Parameter der Aufrufobjekte eingehen, muss zun¨ achst ein Mechanismus eingef¨ uhrt werden, der diese Parameter durch Variable ersetzt. Dieser Ersetzungsmechanismus h¨ angt nicht von den geometrischen Objekten ab, sondern nur von deren Typ, so dass wir zun¨ achst f¨ ur jeden Typ ein zugeh¨origes universelles Objekt definieren. Sei dazu X = [xα : α ∈ I] ein Satz von abz¨ahlbar vielen Variablen und R = K[xα : α ∈ I] der Polynomring u ¨ ber K in diesen Variablen. Ist C = C(T ) der Wertebereich eines geometrischen Typs T u ¨ ber dem Grundbereich K, so bezeichnen wir mit C = C ⊗K R den Wertebereich, den man durch Erweiterung K → R des Grundbereichs erh¨alt.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

28

Definition 7 Als universelles Objekt vom Typ T bezeichnen wir ein Element o mit o.c ∈ C, so dass sich f¨ ur jedes spezielle geometrische Objekt o vom Typ T dessen Koordinatendarstellung durch geeignete Variablenspezifikation2 s = {xa → γa } mit γa ∈ K ergibt: o.c = subs(o.c, s). Ein universelles geometrisches Objekt ist selbst wieder ein spezielles geometrisches Objekt u ¨ ber dem erweiterten Koeffizientenbereich R. Zur Definition der universellen Formel eines Konstruktionswerkzeugs mit mehreren Aufrufparametern ben¨ otigen wir mehrere universelle Objekte mit voneinander unabh¨angigen Variablenmengen. Q Definition 8 Als universelles Tupel vom Typ t∈T t bezeichnen wir ein Tupel O = (ot ) mit Q o.c ∈ C t , so dass sich f¨ ur jedes Tupel O = (ot ) spezieller geometrischer Objekte vom Typ t∈T t dessen Koordinatendarstellung durch geeignete Variablenspezifikation s = {xa → γa } mit γa ∈ K ergibt: ot .c = subs(ot .c, s). Insbesondere nennen wir O eine universelle Q Realisierung einer Konfiguration Γ = (T, E), wenn O zugleich ein universelles Tupel vom Typ t∈T t ist3 .

Beschreibt w : T onnen wir diesen mit einem Tupel 1 ×· · ·×Tn → Ta einen Konstruktionsschritt, so k¨  uhren. Da alle von uns bisher implementierten FunktioO = o1 , . . . , on universeller Objekte ausf¨ nen Punkte oder Geraden zur¨ uckliefern, deren Koordinaten sich rational in den Koordinaten der als Aufrufparameter verwendeten Objekte ausdr¨ ucken lassen, erhalten wir f¨ ur die Koordinaten des Ergebnisobjekts dieses Konstruktionsschritts rationale Ausdr¨ ucke in den Koordinaten von O. Diese Ausdr¨ ucke stellen universelle Formeln in dem Sinne dar, dass jede Ausf¨ uhrung des Konstruktionsschritts mit einer zul¨assigen speziellen Realisierung O = (o1 , . . . , on ) der Startkonfiguration, also einer solchen mit w.DG (o1 .c, . . . , on .c) = false, zu einem speziellen Ergebnisobjekt f¨ uhrt, dessen Koordinaten sich auch durch jede Variablenspezifikation aus den universellen Formeln bestimmen lassen, durch welche sich O aus O ergibt. Ist w

w

w

2 1 → . . . −−−N−→ ΓN = ΓE → Γ1 −−−− ΓS = Γ0 −−−− ¨ eine Konstruktion, so k¨ onnen wir diese Uberlegungen auf jeden einzelnen Konstruktionsschritt anwenden. Starten wir mit einer universellen Realisierung OS der Startkonfiguration ΓS , so liefert w1 .c universelle Formeln f¨ ur die Koordinaten des in Γ1 neu konstruierten Objekts o.

Die universelle Formel von w2 ergibt  sich,  wenn statt o auch ein universelles Objekt o verwendet wird. Die Koordinaten von w2 ◦ w1 O ergeben sich, wenn in dieser universellen Formel die

Spezifikation o → o ausgef¨ uhrt wird. Dies bedeutet, in der universellen Formel von w2 die Variablen aus o durch die universellen Formeln zu ersetzen, welche die Koordinaten von o beschreiben. Kurz, in der universellen Formel von w2 haben wir einzelne Variablen durch rationale Ausdr¨ ucke zu ersetzen.

Dies setzt sich u ¨ ber die anderen Konstruktionsschritte fort, so dass sich die Koordinaten der Realisierung O E der Endkonfiguration aus den universellen Formeln des Schritts wN ergeben, indem dort f¨ ur die Variablen rationale Ausdr¨ ucke in den Variablen von O S eingesetzt werden, die sich Schritt f¨ ur Schritt nach demselben Prinzip in den vorangegangenen Konstruktionsschritten ergeben haben. Ersetzt man aber in einem rationalen Ausdruck einzelne Variablen durch andere rationale Ausdr¨ ucke, so entsteht als Ergebnis wieder ein rationaler Ausdruck (oder, wenn sich der Nullausdruck als Hauptnenner ergibt, ein Fehler). Durch eine solche Konstruktion wird der Bereich der rationalen Ausdr¨ ucke also nicht verlassen. 2 Genau gesagt muss gefordert werden, dass dies nicht nur f¨ ur spezielle Objekte mit Koordinaten aus K gilt, sondern auch f¨ ur Objekte, deren Koordinaten in Erweiterungen von K liegen. R hat die universelle Eigenschaft, dass jede (endliche) Erweiterung von K als Spezialisierung der Erweiterung K → R hergestellt werden kann. Auf diese Feinheiten soll hier nicht eingegangen werden. Die Idee eines solchen universellen geometrischen Objekts folgt dem Konzept des allgemeinen Punkts einer Variet¨ at in der algebraischen Geometrie. 3 Was nichts anderes bedeutet als dass wir die Vorgeschichte E der Entstehung von Γ vergessen.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

29

Bestimmen wir etwa die Koordinaten des Umkreismittelpunkts des Dreiecks △ ABC als Schnittpunkt der entsprechenden Mittelsenkrechten m, n, so bedeutet dies auf dem betrachteten symbolischen Niveau, dass beim Aufruf von intersection point(p bisector(B,C), p bisector(C,A)) in der universellen Formel   m2 n 3 − m3 n 2 m3 n 1 − m1 n 3 , , m1 n 2 − m2 n 1 m1 n 2 − m2 n 1 nach der sich die Koordinaten des Schnittpunkts der Geraden m, n berechnen, die Komponenten von m, n durch die entsprechenden rationalen Ausdr¨ ucke   −b21 − b22 + c21 + c22 p bisector.c(B.c, C.c) = b1 − c1 , b2 − c2 , 2

bzw.   a21 + a22 − c21 − c22 p bisector.c(C.c, A.c) = −a1 + c1 , −a2 + c2 , 2 zu ersetzen sind. Diese Ausdr¨ ucke sind ihrerseits w¨ahrend des Aufrufs p bisector(B,C) == ortho line(midPoint(B,C),pp line(B,C)) in einem Substitutions- und Simplifikationsprozess (der Tiefe 2) nach demselben Prinzip entstanden. Wir erhalten in diesem Fall als universelle Formel f¨ ur die Koordinaten des Umkreismittelpunkts M   2 2 2 2 2 2 2 2 a1 b2 − a1 c2 + a2 b2 − a2 c2 − 2

2

2

2

 a22b1 − a22 b2 + a2 c21 + a22c2 +  b1 c2 + b2 c2 − b2 c1 − b2 c2  M.c :=   2 a1 b2 − 2 a1 c2 − 2 a2 b1 + 2 a2 c1 +  2 b1 c2 − 2 b2 c1

,

−a1 b1 + a1 c1 + a1 b1 + a1 b2 − a1 c1 2 − a1 c2 2 − a2 2 b1 + a2 2 c1 −   b1 2 c1 + b1 c1 2 + b1 c2 2 − b2 2 c1 



2 a1 b2 − 2 a1 c2 − 2 a2 b1 + 2 a2 c1 +   2 b1 c2 − 2 b2 c1

wenn wir vom universellen Dreieck △ ABC mit A.c = (a1 , a2 ), B.c = (b1 , b2 ), C.c = (c1 , c2 ) als Startkonfiguration ausgehen. Der Simplifikationsprozess rationaler Funktionen liefert eine einfachere rationale Funktion, die f¨ ur alle Variablenspezifikationen, welche f¨ ur die unsimplifizierte Funktion nicht zu einem Fehlerabbruch f¨ uhren, denselben Wert hat wie diese. Der Definitionsbereich der simplifizierten rationalen Funktion kann allerdings gr¨ oßer sein als derjenige der Ausgangsfunktion. F¨ ur diesen Schnittpunkt M k¨ onnen wir nun untersuchen, ob er tats¨achlich der Umkreismittelpunkt ist, also eine gewisse geometrische Eigenschaft hat. Dazu w¨are etwa zu untersuchen, ob die universellen Formeln sqrdist(M,A)-sqrdist(M,B); sqrdist(M,A)-sqrdist(M,C); welche diese Eigenschaft kodieren, jeweils zu Null simplifizieren. Definition 9 Seien T1 , . . . , Tn geometrische Typen. Eine (informatische) Funktion φ : T1 × · · · × Tn → boolean zusammen mit einer(mathematischen) Funktionen φ.c : C(T1 ) × · · · × C(Tn ) → Boolean bezeichnen wir als geometrische Eigenschaft.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

30

Das eben beschriebene Beispiel ist die typische Konstellation f¨ ur eine ganze Klasse geometrischer S¨atze: Wenn sich eine gewisse Menge geometrischer Objekte in einer durch eine Konstruktion beschriebenen Abh¨ angigkeitsrelation zueinander befindet, dann gilt f¨ ur diese Objekte eine zus¨atzliche geometrische Eigenschaft. S¨ atze dieser Struktur bezeichnen wir als geometrische S¨atze vom konstruktiven Typ. Weitere Beispiele siehe geo-1.txt. Abschließend sei angemerkt, dass die bisherigen Betrachtungen immer vom Modell der affinen Punktkoordinaten ausgingen. F¨ ur das Modell mit homogenen Punktkoordinaten l¨asst sich sogar erreichen, dass alle universellen Formeln polynomial sind, da durch Skalieren mit einem entsprechenden Faktor in den universellen Formeln immer Nennerfreiheit erreicht werden kann. Da die Klasse der polynomialen Ausdr¨ ucke nicht verlassen wird, wenn man in polynomialen Ausdr¨ ucken Variablen durch Polynome ersetzt, gelten dieselben Ausf¨ uhrungen wie oben, wenn man rationale ” Ausdr¨ ucke“ durch polynomiale Ausdr¨ ucke“ ersetzt. Dabei k¨onnen u ¨berhaupt keine rechnerischen ” Ausnahmen mehr auftreten, sondern nur die geometrische Ausnahme, dass sich als universelle Koordinaten eines Objekts (0 : 0 : 0) ergibt.

3.2

Der Mechanisierungssatz fu atze ¨r geometrische S¨ vom konstruktiven Typ

Untersuchen wir nun die Beweiskraft der ausgef¨ uhrten symbolischen Berechnungen f¨ ur S¨atze vom konstruktiven Typ n¨ aher. Wir unterteilen dazu die Menge der Variablen in zwei disjunkte Teilmengen X und Y , wobei die Variablen aus X zum Anschreiben einer universellen Startkonfiguration eingesetzt werden und die Variablen aus Y zum Anschreiben universeller Formeln f¨ ur Konstruktionswerkzeuge. Sei K die Konstruktion, welche die Endkonfiguration beschreibt, in welcher eine gewisse geometrische Eigenschaft gelten soll, O = O(X) eine universelle Realisierung der Startkonfiguration von K, O eine zul¨ assige spezielle Realisierung dieser Startkonfiguration, welche durch die Variablenspezifikation X → X0 aus O entsteht, f¨ ur die also O.c = subs(X = X0 , O.c) gilt. Wir wollen zun¨achst annehmen, dass die Konstruktion auf O ausf¨ uhrbar ist. K ist aus einzelnen Konstruktionsschritten aufgebaut, so dass sich ein induktiver Zugang aufdr¨angt. Seien deshalb K(i−1) und K(i) Teilkonstruktionen sowie w = wi der sie verbindende Konstruktions′ schritt. Die universelle Formel von w ergibt sich aus einem universellen Parametertupel O (Y ) zu ′ w.c(O (Y )). ¨ sind O und Wenden wir K(i−1) auf O an, so entsteht eine Realisierung O i−1 (X) von Γi−1 . Ahnlich Oi−1 verbunden. Wir nehmen als Induktionsvoraussetzung an, dass die Koordinaten von O i−1 (X) durch universelle Formeln in X beschrieben werden, also stets Oi−1 .c = subs(X = X0 , Oi−1 .c) gilt. Anwenden von w auf Oi−1 liefert eine Realisierung O i (X) = w(O e i−1 (X)) von Γi , wobei sich die Koordinaten des neu konstruierten Objekts aus der universellen Formel von wi ergeben, indem ′ die universelle Realisierung O (Y ) zu O i−1 (X) spezifiziert, also jede Variable y ∈ Y durch die entsprechende Formel y = y(X) ersetzt wird: ′

O i .c(X) = w(O e i−1 (X)) = subs(Y = Y (X), w.c(O e (Y ))) .

Die Wirkung ist dieselbe wie beim Aufruf der (informatischen) Funktion wi , wo die in der Definition verwendeten Aufrufparameter durch Werte, in diesem Fall die berechneten universellen Formeln, zu ersetzen sind. Konstruiert man von der speziellen Realisierung Oi−1 ausgehend wi (Oi−1 ), so wird genau derselbe Aufrufmechanismus f¨ ur die Berechnung der Koordinaten des neuen speziellen Objekts aus den speziellen Koordinaten von Oi−1 aufgerufen. Die entscheidende Eigenschaft ist also      wi .c (Oi−1 .c) = wi .c subs(X = X0 , Oi−1 .c) = subs X = X0 , wi .c Oi−1 .c ,

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

31

oder in Worten, dass es egal ist, erst die universelle Formel f¨ ur wi (Oi−1 ) zu berechnen und dann spezielle Koordinaten einzusetzen oder spezielle Koordinaten bereits in Oi−1 einzusetzen (was nach Induktionsvoraussetzung Oi−1 ergibt) und daraus wi (Oi−1 ) zu berechnen. Impliziter Kern der Argumentation ist also die Kommutativit¨at des folgenden Diagramms w e(i−1) .c

w e .c

w e(i−1) .c

w e .c

O.c −−−−−→ O i−1 .c −−−i−→ O i .c    s s s y y y O.c −−−−−→ Oi−1 .c −−−i−→ Oi .c

wobei s f¨ ur die Variablensubstitution X → X0 steht. Dabei werden Formeln in der oberen Zeile mit Berechnungsvorschriften in der unteren Zeile in Verbindung gebracht. Die Zul¨assigkeit von O f¨ ur K(i) l¨ asst sich durch die Bedingung _ w ej .DG(Oj−1 .c) = false j≤i

beschreiben, die eine Konjunktion geometrischer Eigenschaften ist. Nachdem wir nun verstehen, was genau das symbolische Ausf¨ uhren einer Konstruktion bedeutet und welche Rolle die dabei produzierten universellen Formeln spielen, gilt es den Charakter des symbolischen Auswertens einer geometrischen Eigenschaft zu verstehen. Sei also φ : T1 × · · · × Tn → boolean eine solche geometrische Eigenschaft. Rufen wir φ mit speziellen geometrischen Objekten u ¨ ber dem Grundbereich K auf, so erhalten wir einen der Werte true oder false zur¨ uck. Das gilt nicht mehr, wenn wir denselben Aufruf in einer symbolischen Umgebung absetzen, denn der entstehende boolesche Ausdruck wird normalerweise noch Variablen enthalten und kann erst nach Belegung der Variablen mit konkreten Werten vollst¨ andig ausgewertet werden. Rufen wir also φ mit einem Tupel symbolischer Objekte auf, so ist das Ergebnis nicht aus dem Wertebereich Boolean, sondern aus dem Bereich BooleanExpression: φ.c : C(T1 ) × · · · × C(Tn ) → BooleanExpression

Rufen wir φ mit einem Tupel universeller Objekte auf, so ist das Ergebnis der zu φ assoziierte universelle boolesche Ausdruck. Analog zu obigem kommutativem Diagramm erhalten wir das folgende Diagramm w e(N ) .c

φ.c

w e(N ) .c

φ.c

O.c −−−−→ O N .c −−−−→ φ.c(O N .c)    s s s y y y O.c −−−−→ ON .c −−−−→ φ.c(ON .c)

wobei φ.c(O N .c) ∈ BooleanExpression der boolesche Ausdruck ist, welcher sich aus einem universellen booleschen Ausdruck von φ durch Spezifikation des universellen Tupels zu O N ergibt. Die oben gef¨ uhrten Beweise verwenden wiederum implizit die Kommutativit¨at dieses Diagramms, d. h. dass der konkrete boolesche Wert φ.c(ON .c) ∈ Boolean gleichberechtigt als Ergebnis der Anwendung von φ auf ON oder aus φ.c(O N .c) durch die Variablenspezifikation s und nachfolgende Simplifikation des nun variablenfreien booleschen Ausdrucks zu einem booleschen Wert gewonnen werden kann. In allen bisherigen Beispielen l¨ asst sich die Behauptung φ als Verschwinden des Werts einer gewissen Berechnung formulieren, d. h. in der Form φ

iszero

φ.c : C(T1 ) × · · · × C(Tn ) −−−−→ K −−−−→ Boolean

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

32

faktorisieren, was sich nach Grundbereichserweiterung K → R zu φ

iszero

φ.c : C(T1 ) × · · · × C(Tn ) −−−−→ R −−−−→ BooleanExpression orte stets eine polynomiale universelle Formel, aus welcher der in allen F¨allen ver¨andert. Zu φ geh¨ wenigstens rationale Ausdruck φ(O N .c) durch Spezifikation des universellen Tupels zu ON gewonnen wurde. Eine weitere Simplifikation vereinfachte dann bereits diesen rationalen Ausdruck zu Null, woraus folgt, dass iszero ◦ φ(O N .c) bereits als boolescher Ausdruck unabh¨angig von Variablenbelegungen zu true simplifiziert. Von ¨ahnlicher Struktur sind die Zul¨ assigkeitsbedingungen w ej .DG(Oj−1 .c) = false f¨ ur O, die sich bisher meist als iszero ◦ ψj (Oj−1 .c) darstellen ließen, wobei ψj dieselbe Struktur hat wie φ in obigen Betrachtungen. Kern der gesamten Argumentation ist also die Kommutativit¨at der oben angef¨ uhrten Diagramme, was a¨quivalent zur Vertauschbarkeit von Variablensubstitution und Berechnung der entsprechenden universellen Formeln ist. In allen bisher betrachteten Beispielen ist dies durch den polynomialen oder rationalen Charakter der universellen Formeln gew¨ahrleistet, da Variablensubstitutionen operationstreu sind, d. h. mit den arithmetischen Operationen in R bzw. im Quotientenk¨orper Q(R) kommutieren. Wir f¨ uhren deshalb die folgenden Begriffe ein. Definition 10 Ein Konstruktionswerkzeug w, dessen universelle Formel aus rationalen oder sogar polynomialen Ausdr¨ ucken in den Variablen eines universellen Tupels besteht, bezeichnen wir als rational bzw. polynomial. Geometrische Bedingungen φ, die sich wie oben in der Form φ.c = iszero ◦ φ darstellen lassen, so dass die universelle Formel von φ polynomial ist, bezeichnen wir als polynomiale Bedingung. L¨asst sich w.DG als iszero ◦ w.DG wie oben darstellen4 , wobei die universelle Formel von w.DG polynomial ist, bezeichnen wir w als Konstruktionswerkzeug mit polynomialen Degenerationsbedingungen. Eine Konstruktion K bezeichnen wir als polynomial bzw. rational, wenn sie aus polynomialen bzw. rationalen Konstruktionswerkzeugen mit polynomialen Degenerationsbedingungen aufgebaut ist. Als geometrischen Satz vom konstruktiven Typ bezeichnen wir eine rationale Konstruktion K zusammen mit einer auf der Endkonfiguration von K gegebenen polynomialen Bedingung φ. Wir sagen, dass der Satz gilt, wenn f¨ ur jede zul¨assige spezielle Realisierung der Startkonfiguration von K die Bedingung φ auf der zugeh¨origen Realisierung der Endkonfiguration zu true auswertet. Wie ausgef¨ uhrt ist zu beachten, dass diese Definitionen nicht nur vom Charakter der Konstruktionswerkzeuge abh¨ angen, sondern auch vom verwendeten Koordinatenmodell. Im Modell der affinen Punktkoordinaten etwa sind einige der bisher betrachteten Konstruktionswerkzeuge nur rationale Werkzeuge, im Modell der homogenen Punktkoordinaten dagegen alle Konstruktionswerkzeuge polynomial. Alle bisher betrachteten geometrischen S¨atze waren S¨atze vom konstruktiven Typ. Ein solcher Satz ′ (K, φ) wird durch die folgenden Formeln begleitet: Universelle Realisierungen O(X) ⊂ O (X, Y ) von Start- und Endkonfiguration von K, universelle Formeln f¨ ur die Ausf¨ uhrung O E (X) = K(O) ′ von K auf O, die universelle Formel Φ(X, Y ) = φ(O .c) der Behauptung φ sowie das Resultat der Substitution Φ′ (X) = φ(O E .c) = Φ| ′ (enth¨alt nur noch Variablen aus X). O →O E

F¨ ur die ausgef¨ uhrten symbolischen Rechnungen gibt es folgende Alternativen: 4 Mehrere und-verkn¨ upfte solche Bedingungen lassen sich durch Aufmultiplizieren zu einer zusammenfassen, da ein Produkt nur dann verschieden Null ist, wenn alle Faktoren verschieden Null sind. Das ist allerdings eine theoretische Aussage. In praktischen Anwendungen arbeitet man aus Performancegr¨ unden mit mehreren Polynomen.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

33

W ej .DG(O j−1 .c) vereinfacht als BooleanExpression 1. O selbst ist f¨ ur K nicht zul¨ assig, d. h. j w zu true. Es gibt also auch keine zul¨assigen speziellen Realisierungen – die Voraussetzungen des Satzes sind widerspr¨ uchlich. W ej .DG(O j−1 .c) ebenfalls zu true vereinfacht. Sei i minimal mit der Eigenschaft, dass j≤i w Wegen _ _ ei .DG(O i−1 .c) = A ∨ B, w ej .DG(O j−1 .c) ∨ w w ej .DG(O j−1 .c) = j≤i

jsimplify(subs(u,P)),sol1); Zum Beweis des Satzes u ur P ¨ ber die Schnittpunkte der Winkelhalbierenden k¨onnen wir die vier f¨ berpr¨ u fen, ob berechneten Werte wieder in die Bedingung on bisector(P,A,C,B) einsetzen und u ¨ der so entstehende (nicht mehr nur rationale) Ausdruck zu Null vereinfacht: map(u->on_bisector(u,A,C,B),PValues); [0, 0, 0, 0] Allerdings lassen sich geschachtelte Wurzeln nicht immer so problemlos vereinfachen. Außerdem steht eine Interpretation des Ergebnisses a¨hnlich dem Mechanisierungssatz f¨ ur Geometries¨atze vom konstruktiven Typ noch aus. Die Rechnungen verlassen den Polynomring R in Richtung algebraischer Erweiterungen. Es ergibt sich nun die Frage, ob auch ohne explizite Aufl¨osung der Gleichung f¨ ur x2 in Wurzelausdr¨ ucke nachgewiesen werden kann, dass jede der vier L¨osungen auch Nullstelle der Gleichung on_bisector(P,A,C,B); 2 c1 3 x2 − c1 3 − 2 c1 2 c2 x1 − 2 c1 2 x1 x2 + 2 c1 2 x1 + 2 c1 c2 2 x2 − c1 c2 2 + 2 c1 c2 x1 2 − 2 c1 c2 x2 2 − c1 x1 2 + c1 x2 2 − 2 c2 3 x1 + 2 c2 2 x1 x2 + 2 c2 2 x1 − 2 c2 x1 x2 ist. Derartige Fragen wollen wir im n¨achsten Abschnitt genauer formulieren und studieren. Hier sei noch angemerkt, dass man Winkelhalbierende mit einem anderen Konzept auch als geometrische Objekte vom konstruktiven Typ einf¨ uhren kann. Aufgabe 14 Zeigen Sie auf folgende Weise, dass sich die Winkelhalbierenden in einem Punkt schneiden: A und B seien gegeben und D sei der Schnittpunkt der Winkelhalbierenden aus A und B. Dann ist C der Schnittpunkt der Geraden, die aus AB durch Spiegelung an AD bzw. BD hervorgehen. CD ist genau dann Winkelhalbierende, wenn AC bei Spiegelung an CD in BC u ¨bergeht. Sie k¨onnen dazu die GeoProver-Funktion sym line verwenden.

4.2

Geometrische S¨ atze vom Gleichungstyp

Alle unsere Geometrietheoreme hatten die folgende Gestalt: Gegeben ist • eine konstruktiv gegebene (rationale oder polynomiale) geometrische Konfiguration K mit O(X) als universeller Realisierung der Startkonfiguration und daraus abgeleitet universelle Formeln f¨ ur die Endkonfiguration OE (X) = K(O), was wir im Weiteren als allgemeine geometrische Konfiguration (AGK) bezeichnen; • eine Menge von polynomialen geometrischen Bedingungen mit Polynomen F = {f1 , . . . , fm } ⊂ R = k[X] in den Variablen X als universellen Formeln, die weitere implizite Abh¨angigkeiten zwischen den Elementen der Konfiguration ΓE beschreiben und die wir als allgemeine geometrische Voraussetzungen (AGV) bezeichnen; • eine (oft nicht explizit bekannte) polynomiale Nichtdegenerationsbedingung mit universeller Formel h ∈ R f¨ ur die G¨ ultigkeit der Schlussfolgerung, die wenigstens die Ausf¨ uhrbarkeit von K garantiert, sowie

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

46

• eine polynomiale geometrische Bedingung mit universeller Formel g ∈ R, welche die Folgerung des Satzes algebraisch kodiert. Definition 11 Als Geometriesatz vom Gleichungstyp bezeichnen wir dann eine Aussage der folgenden Gestalt: In jeder durch eine Substitution X = X0 erzeugten speziellen Realisierung OE = OE (X0 ), die nicht degeneriert ist (f¨ ur welche also h(X0 ) 6= 0 gilt) und die AGV erf¨ ullt (wenn also X0 eine gemeinsame Nullstelle der Polynome f ∈ F ist), gilt die geometrische Folgerung (d. h. X0 ist auch eine Nullstelle von g). 

∀ X0 ∈ K n 

^

f ∈F



f (X0 ) = 0 ∧ h(X0 ) 6= 0 ⇒ g(X0 ) = 0

Wir schreiben f¨ ur einen solchen Satz auch kurz (F/h ⇒ g). Betrachten wir zum Abschluss dieses Punktes einen weiteren geometrischen Satz, den wir als Satz vom Gleichungstyp formulieren k¨ onnen. Es handelt sich um das folgende Schmetterlingstheorem [2, S. 31]: Auf einer Kreislinie mit dem Mittelpunkt O seien vier Punkte A, B, C, D gegeben. P sei der Schnittpunkt von AC und BD. Die Senkrechte auf der Verbindungslinie OP schneide die Seiten AD und BC (die Schmetterlingsfl¨ ugel“) in den Punkten F und ” G. Dann gilt |P F | = |P G|.

A B O P F

G D

C

Wir wollen bei der Herleitung einer algebraischen Form dieses Satzes zugleich zwischen (in einem sp¨ater zu pr¨ azisierenden Sinne) unabh¨angigen“ Variablen ui , deren Wert frei w¨ahlbar ist, und ” abh¨angigen“ Variablen xi , deren Wert sich eindeutig oder endlich vieldeutig aus den algebraischen ” Bedingungen und bereits fixierten Werten ergibt, unterscheiden. Sei dazu O der Koordinatenursprung und A = (u4 , 0) auf der x-Achse gelegen. B, C und D seien drei weitere Punkte auf dem Kreis. Je eine Koordinate kann frei gew¨ahlt werden, die andere ergibt sich aus der Kreisgleichung. Die Punkte seien also B = (u1 , x1 ), C = (u2 , x2 ) und D = (u3 , x3 ). P = (x4 , x5 ) ergibt sich dann eindeutig als Schnittpunkt, ebenso wie die Senkrechte h und die Punkte F = (x6 , x7 ) und G = (x8 , x9 ). Insgesamt erhalten wir folgende algebraische Formulierung unprotect(O): unprotect(D): O:=Point(0,0); A:=Point(u4,0); B:=Point(u1,x1); C:=Point(u2,x2); D:=Point(u3,x3); P:=Point(x4,x5); F:=Point(x6,x7); G:=Point(x8,x9); c0:=pc_circle(O,A); h:=ortho_line(P,pp_line(O,P)); polys:= { on_circle(B,c0), on_circle(C,c0), on_circle(D,c0), is_collinear(B,D,P), is_collinear(A,C,P), on_line(F,h), is_collinear(A,D,F), on_line(G,h), is_collinear(B,C,G)}; con:=sqrdist(P,F)-sqrdist(P,G);

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

47

n polys = u1 2 + x1 2 − u4 2 , u2 2 + x2 2 − u4 2 , u3 2 + x3 2 − u4 2 ,

u1 x3 − u1 x5 − u3 x1 + u3 x5 + x4 x1 − x4 x3 , u4 x2 − u4 x5 + u2 x5 − x4 x2 , − x4 x6 − x5 x7 + x5 2 + x4 2 , u4 x3 − u4 x7 + u3 x7 − x6 x3 , − x4 x8 − x5 x9 + x5 2 + x4 2 , u1 x2 − u1 x9 − u2 x1 + u2 x9 + x8 x1 − x8 x2

con = x6 2 − 2 x4 x6 + x7 2 − 2 x5 x7 − x8 2 + 2 x4 x8 − x9 2 + 2 x5 x9

o

Das Gleichungssystem hat eine recht u ¨ berschaubare Struktur. Die Anzahl der abh¨angigen Variablen xi entspricht genau der Anzahl der Gleichungen in der Menge polys, die linear in x4 , . . . , x9 und quadratisch in x1 , x2 , x3 sind. MuPAD’ ssolve kann mit diesem Gleichungssystem schon nichts mehr anfangen. vars:=[x.i$i=1..9]; sol:=solve(polys,vars,IgnoreSpecialCases); Maple 9 liefert zwar noch eine L¨ osung“ mit drei RootOf-Symbolen ” vars:={seq(cat(x,i),i=1..9)}; sol:=[solve(polys,vars)]; nops(sol); mit der es aber diesmal auch nichts mehr anfangen kann: map(u->normal(subs(u,con)),sol); Fordert man explizite L¨ osungen f¨ ur die xi , i = 1, . . . , 9 als Ausdr¨ ucke in den ui , i = 1, 2, die sich in diesem Fall als einfache Quadratwurzeln berechnen lassen, so liefert Maple zwar 8 L¨osungen zur¨ uck, kann aber auch mit ihnen nichts mehr anfangen, selbst wenn der m¨achtige Simplifikationsalgorithmus evala f¨ ur algebraische Ausdr¨ ucke angeworfen wird. sol1:=map(allvalues,sol); nops(sol1); map(u->normal(subs(u,con)),sol1); map(u->evala(subs(u,con)),sol1); Der lineare Teil des Gleichungssystems kann per Hand“ gel¨ost, aber auch durch eine st¨arker ” konstruktiv formulierte AGK eliminiert werden. W¨ahlen wir etwa F und G als Geradengleiter und P als Schnittpunkt der Geraden AC und BD sowie F und G als Schnittpunkte mit h, so ben¨otigen wir nur 3 Gleichungen, um das Problem zu formulieren # ==> Butterfly_b O:=Point(0,0); A:=Point(u4,0); B:=Point(u1,x1); C:=Point(u2,x2); D:=Point(u3,x3); P:=intersection_point(pp_line(A,C), pp_line(B,D)); c0:=pc_circle(O,A); h:=ortho_line(P,pp_line(O,P)); F:=intersection_point(pp_line(A,D),h); G:=intersection_point(pp_line(B,C),h); polys:= { on_circle(B,c0), on_circle(C,c0), on_circle(D,c0)}; con:=numer(sqrdist(P,F)-sqrdist(P,G));

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

48

Allerdings verlagert sich damit das Problem nur, denn der Ausdruck f¨ ur con ist nun deutlich komplizierter geworden und enth¨ alt MuPAD kann diesen rationalen Ausdruck schon nicht mehr berechnen.. Maple liefert f¨ ur con einen Ausdruck mit length(con) = 548 465 Termen. vars:={x1,x2,x3}; sol:=[solve(polys,vars)]; nops(sol); map(u->normal(subs(u,con)),sol); sol1:=map(allvalues,sol); nops(sol1); map(u->normal(subs(u,con)),sol1); Maple kann auch in dieser einfachen Formulierung die Behauptung nicht verifizieren, obwohl die L¨osungsmenge sol1 nur einfache Quadratwurzeln enth¨alt. Erst der st¨arkere Simplifikationsoperator evala vereinfacht das Polynom, welches die geometrische Behauptung kodiert, zu Null, wobei die Variante sol deutlich schneller abgearbeitet wird als die Variante sol1. Dasselbe gilt f¨ ur Mathematica und erst recht MuPAD. Einzig Reduce kann eine leicht modifizierte Algebraisierung mit 5 Gleichungen (F und G werden als Geradengleiter auf AD bzw. BC angesetzt, unftiger Zeit zu einem Ende bringen. siehe Butterfly c) in vern¨ Das Schmetterlingstheorem l¨ asst allerdings auch eine konstruktive Formulierung zu, wenn wir zur Definition der Punkte B, C, D eine (rationale) Parametrisierung des Kreises verwenden. Diese ergibt sich, wenn wir durch einen bekannten Punkt auf der Kreislinie Sekanten zeichnen und die Koordinaten des jeweils zweiten Schnittpunkts in Abh¨angigkeit vom Anstieg dieser Sekante ausdr¨ ucken. Wir hatten das weiter oben bereits am Beispiel der Funktion other cl point besprochen. F¨ ur den Einheitskreis x2 + y 2 = 1 und den Referenzpunkt (−1, 0) ergibt sich f¨ ur die Koordinaten eines Kreisgleiters folgende Formel O:=Point(0,0); A:=Point(-1,0); kreis:=pc_circle(O,A); line:=pp_line(A,Point(0,r)); other_cl_point(A,kreis,line); 

 r2 − 1 2r , r2 + 1 r2 + 1 Sind O und A Punkte in allgemeiner Lage, so ergeben sich nur leicht kompliziertere Formeln, die in der GeoProver-Funktion circle_slider(O,A,u) implementiert sind. Das entsprechende algebraische Problem kann mit dem GeoProver-Paket und jedem der Target-CAS gel¨ost werden. O:=Point(0,0); A:=Point(u4,0); B:=circle_slider(O,A,u1); C:=circle_slider(O,A,u2); D:=circle_slider(O,A,u3); P:=intersection_point(pp_line(A,C), pp_line(B,D)); c0:=pc_circle(O,A); h:=ortho_line(P,pp_line(O,P)); F:=intersection_point(pp_line(A,D),h); G:=intersection_point(pp_line(B,C),h); con:=normal(sqrdist(P,F)-sqrdist(P,G));

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

4.3

49

Geometrietheoreme vom linearen Typ

Unsere generelle Vorgehensweise zum Beweis geometrischer S¨atze vom Gleichungstyp wird sein, m¨ogliche Belegungen der Variablen der universellen Realisierung der Startkonfiguration schritt” weise“ zu denken. Wir werden zun¨ achst einen Teil von ihnen, die unabh¨angigen Variablen“, ” mit beliebigen (zul¨ assigen) Werten belegen, und daraus die (endlich vielen) Belegungen f¨ ur die verbleibenden abh¨ angigen“ Variablen, welche die zus¨atzlichen Gleichungen f ∈ F respektieren, ” bestimmen. Untersuchen wir zun¨ achst den einfachsten Fall von Geometrietheoremen vom Gleichungstyp – solche, die auf lineare Gleichungssyteme in den abh¨angigen Variablen f¨ uhren. S¨atze vom konstruktiven Typ lassen sich als solche Geometrietheoreme formulieren und meist gilt auch die umgekehrte Aussage. Betrachten wir als Beispiel den Satz von Desargue: A:=Point(u1,u2); B:=Point(u3,u4); C:=Point(u5,u6); P:=Point(u7,u8); Q:=Point(u9,x1); R:=Point(x2,x3); polys:={is_parallel(pp_line(A,C),pp_line(P,R)), is_parallel(pp_line(B,C),pp_line(Q,R)), is_parallel(pp_line(A,B),pp_line(P,Q))}; con:=

is_concurrent(pp_line(A,P),pp_line(B,Q),pp_line(C,R));

Die drei Gleichungen zur Bestimmung der abh¨angigen Parameter sind linear in x1 , x2 , x3 . Als L¨osung ergeben sich rationale Funktionen in u, die, in die Behauptung con eingesetzt, diese zu Null vereinfachen (MuPAD). sol:=solve(polys,{x1,x2,x3}); map(sol,u->normal(subs(con,u))); u2 u7 − u1 u8 − u2 u9 + u3 u8 − u4 u7 + u4 u9 u3 − u1 u1 u9 − u3 u7 + u5 u7 − u5 u9 x2 = u1 − u3 u2 u7 − u1 u8 − u2 u9 + u3 u8 − u6 u7 + u6 u9 x3 = u3 − u1 x1 =

Bei der Auswahl der unabh¨ angigen und abh¨angigen Parameter sind wir dem konstruktiven Ansatz gefolgt. Statt dessen k¨ onnte man auch versuchen, drei andere der Parameter als abh¨angig zu deklarieren, etwa P:=Point(u7,x1); Q:=Point(u8,x2); R:=Point(u9,x3); polys1:={ is_parallel(pp_line(A,C),pp_line(P,R)), is_parallel(pp_line(B,C),pp_line(Q,R)), is_parallel(pp_line(A,B),pp_line(P,Q))}; Auch hier erhalten wir drei Gleichungen, die linear in den als abh¨angig deklarierten Variablen x1 , x2 , x3 sind. Allerdings ist die entsprechende L¨osungsmenge leer: sol:=solve(polys1,{x1,x2,x3}); Geht man etwas vorsichtiger zu Werke, l¨ost zun¨achst die beiden ersten Gleichungen nach x1 und x2 auf und setzt diese Werte dann in die dritte Gleichung ein, um diese schließlich nach x3 aufzul¨osen, so erkennt man, dass dort x3 bereits nicht mehr enthalten ist, sondern eine Gleichung vierten Grades in u entstanden ist, die Parameter also nicht unabh¨angig sind wie angenommen.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

50

sol:=solve({op(polys1,1..2)},{x1,x2}); normal(subs(polys[3],sol[1]));

−

 u u u 2 +u u 2 u +u 2 u u −u u u 2 +u 2 u u −u 2 u u −u u u 2 −u u u 2 + 4 7 5 4 9 2 9 3 6 9 1 3 6 9 6 7 3 8 1 4 5 2 7 3 2 2 2 2  u4 u1 u8 − u6 u1 u8 + u2 u7 u5 − 2 u4 u1 u8 u5 + u6 u1 u8 u3 − u2 u5 u8 + u1 u6 u5 u8 −  u3 u6 u5 u8 − u2 u3 u1 u8 + u2 u5 u1 u8 + u2 u5 u3 u8 − u3 u1 u4 u7 + u3 u4 u7 u5 −  2 u3 u2 u7 u5 + u3 u1 u6 u7 − 2 u3 u1 u6 u9 + u3 u1 u2 u9 + u5 u1 u4 u7 − u5 u1 u6 u7 − u5 u1 u2 u9 + u5 u6 u7 u3 + u5 u2 u9 u3 + u1 u3 u4 u9 + u1 u5 u4 u9 − u3 u5 u4 u9

(u3 − u5 ) (u1 − u5 )

   

Untersuchen wir nun allgemein, was man u ¨ ber Geometrietheoreme vom Gleichungstyp aussagen kann, in denen die abh¨ angigen Parameter x linear von den unabh¨angigen Parametern u abh¨angen. Solche Geometrietheoreme wollen wir als S¨atze vom linearen Typ bezeichnen. Das entsprechende Gleichungssystem hat die Gestalt m X

cij (u)xj + ci0 (u) = 0, i = 1, . . . , m

j=1

Seine L¨osbarkeit h¨ angt ganz wesentlich von der Determinante D(u) := det|cij (u)|i,j=1,...,m ab. Genauer hat das Gleichungssystem f¨ ur jede Belegung der Parameter u, f¨ ur die D(u) 6= 0 gilt, eine eindeutige L¨ osung, die man nach der Cramerschen Regel in der Form xi = xi (u) = Di (u)/D(u) ∈ k(u) ausdr¨ ucken kann. F¨ ur obiges Beispiel l¨ asst sich die Koeffizientenmatrix wie folgt extrahieren (MuPAD): vars:=[x1,x2,x3]; l:=map([op(polys)],p->map(vars,u->coeff(p,u,1))); KoeffMat:=Dom::Matrix()(l);   u3 − u1 0 0 u3 − u5 u4 − u6 −u3 + u5  0 u2 − u6 −u1 + u5 Deren Determinante ist ein Polynom mit der Faktorzerlegung factor(linalg::det(KoeffMat)); (u1 − u3 ) (u1 u4 − u2 u3 − u1 u6 + u2 u5 + u3 u6 − u4 u5 ) Der zweite Faktor kodiert die geometrische Nichtdegenerationsbedingung is collinear(A,B,C) und ließ sich in obiger Formel sol offensichtlich herausk¨ urzen. Der erste Faktor kodiert die Nichtdegenerationsbedingung u1 6= u3 , denn aus u1 = u3 folgt zwingend u7 = u9 , so dass in diesem Fall die unabh¨ angigen“ Variablen nicht mehr unabh¨angig belegt werden k¨onnen. ” F¨ ur D(u) 6= 0 erhalten wir universelle Formeln xi (u) f¨ ur die abh¨angigen Variablen, die wir wie im Fall der S¨ atze vom konstruktiven Typ in die Behauptung g(x, u) einsetzen k¨onnen. Die so entstehende rationale Funktion g(x(u), u) in den Variablen u k¨onnen wir vereinfachen und erhalten ¨ahnliche Alternativen: 1) F¨ uhrt die Simplifikation auf das Nullpolynom, so ist f¨ ur alle zul¨assigen Spezifikationen der unabh¨angigen Variablen (d.h. solche, f¨ ur die D(u) 6= 0 gilt) der Satz richtig. P (u) 2) Ergibt die Simplifikation eine nicht verschwindende rationale Funktion Q(u) 6= 0, so ist der Satz f¨ ur fast alle Spezifikationen falsch und h¨ochstens unter der zus¨atzlichen Voraussetzung P (u) = 0

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

51

richtig. Er gilt also dann nur, wenn zwischen den als unabh¨angig angenommenen Variablen eine Abh¨angigkeit besteht. 3) Ist schließlich bereits D(u) identisch Null, so gibt es eine k(u)-lineare Kombination der Zeilen der Koeffizientenmatrix zum Nullvektor X αi (u)cij (u) = 0, j = 1, . . . , m i

P

Dann ist entweder i αi (u)ci0 (u) 6= 0 eine nichttriviale algebraische Relation zwischen den unabh¨angigen Variablen oder aber auch die erweiterte Koeffizientenmatrix hat u ¨ ber k(u) einen Rang kleiner als m, d.h. eine der abh¨ angigen Variablen xi kann frei gew¨ahlt werden. In beiden F¨allen sind die Voraussetzungen nicht eingehalten. ¨ Satz 16 (Uber das mechanisierte Beweisen geometrischer S¨atze vom linearen Typ): Sei (F ⇒ g) ein Satz vom linearen Typ und (u, x) eine Aufteilung der Variablen der universellen Realisierung O in bgzl. F unabh¨angige und abh¨angige. Ist D(u) nicht identisch Null, so ist u eine maximale Menge unabh¨angiger Variablen und der Satz gilt unter der Nichtdegenerationsbedingung D(u) 6= 0 genau dann, wenn g(x(u), u) als rationale Funktion in k(u), die durch Substitution der eindeutig bestimmten L¨osung x = x(u) ∈ k(u)m von F in g(x, u) entsteht, identisch Null ist. F¨ ur S¨atze vom linearen Typ ist die Nichtdegenerationsbedingung nicht Teil der Formulierung des Satzes und damit der G¨ ultigkeitsbereich des Satzes nicht vorgegeben. Dies ist typisch f¨ ur geometrische S¨ atze vom Gleichungstyp: Definition 12 Ein geometrischer Satz vom Gleichungstyp (F ⇒ g) heißt im Allgemeinen g¨ ultig, wenn es eine polynomiale Nichtdegenerationsbedingung h ∈ R gibt, so dass (F/h ⇒ g) g¨ ultig ist. Wie im Beispiel des Satzes von Desargue kann es sein, dass die Bedingung D(u) 6= 0 eine Reihe geometrisch relevanter F¨ alle ausschließt. Die Ausnahmemenge wird jedoch durch eine algebraische Bedingung auf die unabh¨ angigen Variablen beschrieben, ist also klein“. Oft kann durch ein wei” teres geometrisches Argument der Satz f¨ ur einen relevanten Teil der Ausnahmemenge auf einen nicht degenerierten Fall zur¨ uckgef¨ uhrt werden. Sind etwa in der obigen Formulierung des Satzes von Desargues die Geraden AB und P Q parallel zur y-Achse, aber A, B, C nicht kollinear, so kann durch eine Drehung die Realisierung der Konfiguration in eine andere Realisierung u uhrt ¨ berf¨ werden, die sich nicht in einer Ausnahmelage befindet. Aufgabe 15 Beweisen Sie auf diesem Weg den Satz des Apollonius: In einem rechtwinkligen Dreieck liegen die drei Seitenmitten und der H¨ohenfußpunkt auf die Hypotenuse auf einem gemeinsamen Kreis. Aufgabe 16 Beweisen Sie auf diese Weise den Satz von Pappus.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

5 5.1

52

Gr¨ obnerbasen und generisch gu ¨ ltige Geometrietheoreme Ideale und Nullstellenmengen. Korrespondenzsatz und Zerlegungssatz

Zur Untersuchung der Nullstellenmengen (nicht linearer) polynomialer Gleichungssysteme F = {f1 (x), f2 (x), . . . , fm (x)} geht man – ¨ahnlich zum Untervektorraum, der von den Zeilenvektoren der Koeffizientenmatirx eines linearen Gleichungssystems erzeugt wird – zu invarianten Objekten, den Idealen im Ring R = k[x], u ¨ ber. Definition 13 Als von den Polynomen f ∈ F erzeugtes Ideal Id(F ) bezeichnet man die Menge aller polynomialen Linearkombinationen   X  Id(F ) = rf f : rf ∈ R   f ∈F

von Elementen aus F .

Da R ein Ring ist, kann man alle angegebenen Operationen ausf¨ uhren. Es entsteht eine Menge, die abgeschlossen ist bzgl. Addition, Subtraktion und Vervielfachung mit Elementen r ∈ R. Diese Eigenschaft charakterisiert Ideale zugleich. Zur Bestimmung der Nullstellenmenge ist es unerheblich, ob man von der Menge F oder aber vom Ideal Id(F ) ausgeht. Auf den Idealen eines Ringes R sind folgende Operationen m¨oglich: Summe zweier Ideale I1 , I2 ∈ I(R): I1 + I2 = {a + b ∈ R : a ∈ I1 , b ∈ I2 } Produkt zweier Ideale I1 , I2 ∈ I(R): X I1 · I2 = { ak · bk ∈ R : ak ∈ I1 , bk ∈ I2 } k

Durchschnitt I1 ∩ I2 zweier Ideale I1 , I2 ∈ I(R). Idealquotient eines Ideals I ∈ I(R) bzgl. eines Polynoms f ∈ R: I : f = {g ∈ R : f · g ∈ I} Stabiler Idealquotient eines Ideals I ∈ I(R) bzgl. eines Polynoms f ∈ R: I : f ∞ = {g ∈ R : ∃ n f n · g ∈ I} Eine Menge, die sich als Nullstellengebilde V (F ) = V (Id(F )) = { a = (a1 , . . . , an ) ∈ Cn : ∀ f ∈ F f (a) = 0 } eines Sytems von Polynomen F darstellen l¨asst, bezeichnen wir als affine Variet¨at. Im Gegensatz zur linearen Algebra k¨ onnen verschiedene Ideale dieselbe affine Variet¨at definieren. Das h¨angt damit zusammen, dass Ideale eigentlich Nullstellenmengen mit deren Vielfachheiten verk¨orpern. So besteht etwa aus Sicht der Nullstellen kein Unterschied zwischen den Mengen F1 = {x + 1, y − 1} und F2 = {(x + 1)2 , (y − 1)3 }, aus Sicht der Ideale schon. Sei deshalb rad(I) das gr¨ oßte Ideal, welches dieselbe Nullstellenmenge V (I) wie I (¨ uber einem algebraisch

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

53

abgeschlossenem K¨ orper) hat. Dieses Ideal bezeichnet man auch als das Radikal von I. Ideale, die mit ihrem Radikal u ¨bereinstimmen, bezeichnen wir auch als Radikalideale. Nach dem Hilbertschen Nullstellensatz gilt rad(I) = {f ∈ R : ∃ k > 0 f k ∈ I}. Der Hilbertsche Nullstellensatz behandelt den in gewissem Sinne prototypischen Spezialfall, dass V (I) = ∅ gilt: Satz 17 (Hilberts Nullstellensatz) Ist K ein algebraisch abgeschlossener K¨orper und V (I) = ∅, so gilt 1 ∈ I, d.h., I ist das triviale Eins-Ideal. Dieser Satz verallgemeinert den Fundamentalsatz der Algebra, dass jedes nicht triviale Polynom in eine Nullstelle besitzt.

C

Ist umgekehrt Z ⊂ An eine Teilmenge des affinen Raums, so bezeichnen wir mit I(Z) = {f ∈ R : ∀ z ∈ Z f (z) = 0} das Radikalideal der Polynome, die auf Z verschwinden. Zwischen affinen Variet¨ aten und Radikalidealen besteht eine eineindeutige inklusionsumkehrende Korrespondenz, die in der Vorlesung “Gr¨obnerbasen und deren Anwendungen” als Korrespondenzsatz bewiesen wird: Satz 18 (Korrespondenzsatz) V und I sind zueinander inverse, inklusionsumkehrende Korrespondenzen zwischen den affinen Variet¨aten im An und den Radikalidealen in R, die Durchschnitte der Nullstellenmengen in Idealsummen und Vereinigungen der Nullstellenmengen in Idealdurchschnitte uberf¨ uhren, d.h. ¨ 1. die Bilder unter V sind genau die affinen Variet¨aten im An , 2. die Bilder unter I sind genau die Radikalideale in R, 3. f¨ ur jede Teilmenge W ∈ An ist V (I(W )) die kleinste affine Variet¨at, die W umfasst (deren affiner Abschluss), 4. f¨ ur jedes Ideal J ⊂ R gilt I(V (J)) = rad(J), 5. I1 ⊆ I2 ⇒ V (I1 ) ⊇ V (I2 ), 6. V1 ⊆ V2 ⇒ I(V1 ) ⊇ I(V2 ). T 7. V (I1 + I2 ) = V (I1 ) V (I2 ) und T S 8. V (I1 · I2 ) = V (I1 I2 ) = V (I1 ) V (I2 ).

Ohne Beweis. Siehe Vorlesung “Gr¨ obnerbasen und deren Anwendungen”. Definition 14 Eine affine Variet¨at V heißt irreduzibel, wenn sie sich nicht als Vereinigung zweier echt kleinerer Variet¨aten darstellen l¨asst, d.h. wenn V = V1 ∪ V2 ⇒ V = V1 oder V = V2 gilt. Ist V eine solche irreduzible Variet¨ at und verschwindet das Produkt f g auf ganz V , so muss bereits einer der Faktoren auf V verschwinden. In der Tat, wegen (V ∩ V (f )) ∪ (V ∩ V (g)) = V ∩ (V (f ) ∪ V (g)) = V ∩ V (f g) = V w¨are das eine Zerlegung in kleinere Variet¨aten. Das Verschwindungsideal I = I(V ) ist also ein Primideal.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

54

Satz 19 In einem Polynomring l¨asst sich jedes Radikalideal als Durchschnitt endlich vieler Primideale darstellen. Jede affine Variet¨at V ist die Vereinigung von endlich vielen irreduziblen Variet¨aten V = ∪Vi . Ohne Beweis. Siehe Vorlesung “Gr¨ obnerbasen und deren Anwendungen”. Die Teilvariet¨ aten Vi bezeichnet man auch als die irreduziblen Komponenten von V . Wird etwa die Variet¨ at V = V (f ) durch eine Gleichung f gegeben und ist f = pa1 1 · . . . · pakk die Zerlegung dieses Polynoms in Primfaktoren, so l¨ asst sich V zerlegen als V (f ) =

k [

V (pi ).

i=1

Es kann sein, dass geometrische S¨ atze nur auf einigen Komponenten eines Nullstellengebildes g¨ ultig sind, w¨ahrend andere Komponenten degenerierten Lagen entsprechen. Eine vollst¨ andige Zerlegung in irreduzible Komponenten ist meist schwierig. Oft gen¨ ugt eine teilweise Zerlegung in degenerierte und nicht degenerierte Teile.

5.2

Idealtest, Normalformen und Gr¨ obnerbasen

Die Frage, ob ein Polynom g auf den gemeinsamen Nullstellen der Polynome f ∈ F verschwindet, l¨asst sich also als Idealenthaltenseinsproblem g ∈ Id(F )?“ umformulieren, da Ideale Id(F ), die ” aus geometrischen Fragestellungen entstehen, meist bereits Radikalideale sind. Bei der algorithmischen Umsetzung solcher Idealenthaltenseinstests spielen Normalformen und Gr¨obnerbasen eine zentrale Rolle. Fixieren wir dazu zun¨achst wieder die erforderliche Begrifflichkeit: Sei R = k[x1 , . . . , xn ] = k[x] ein Polynomring und T := T (x) = T (x1 , . . . , xn ) das zugeh¨orige Termmonoid, welches mit einer Termordnung, also einer linearen, monotonen, noetherschen OrdPN αi ∈ R seien so nungsrelation versehen ist. Die Terme eines Polynoms 0 6= f (x) = i=0 ci x ur i < j gilt. Bezeichne weiter angeordnet, dass in der fixierten Termordnung xαi > xαj f¨ T (f ) := {xαi , i = 0, . . . , N } die Menge der in der Darstellung von f auftretenden Terme. Dann k¨onnen wir die folgenden Begriffe definieren: • • • •

den Leitterm lt(f ) := xα0 , den Leitkoeffizienten lc(f ) := c0 , das Leitmonom lm(f ) := lc(f ) · lt(f ), das Reduktum red(f ) := f − lm(f ).

F¨ ur eine Menge B ⊂ R von Polynomen bilden die Vielfachen der Leitterme lt(b), b ∈ B, das Monoid-Ideal Σ(B) := (lt(b) : b ∈ B) ⊂ T . Mit diesen Begriffen kann man eine Erweiterung der Division mit Rest von Polynomen einf¨ uhren, indem ein Polynom f ∈ R so lange reduziert wird, so lange einer der Terme durch den Leitterm eines der Polynome b ∈ B teilbar ist. Das Ergebnis dieser Reduktion bezeichnet man als (vollst¨andige) Normalform r = N F (f, B) des Polynoms f bzgl. B. Die Terme t ∈ Σ(B) bezeichnet man dabei auch als Nichtstandardterme, da sie weiter reduziert werden k¨ onnen. Die Terme t ∈ N (B) = T \ Σ(B) heißen Standardterme. Satz 20 Sei R = k[x1 , . . . , xn ] ein Polynomring u ¨ber einerm K¨orper k, < eine Termordnung auf T (x1 , . . . , xn ) und B = {b1 , . . . , bm } ⊂ R eine endliche Menge von Polynomen. Dann gibt es einen Algorithmus, der f¨ ur jedes Polynom f ∈ R nach endlich vielen Schritten eine Darstellung f = v1 b1 + . . . + vm bm + r mit v1 , . . . , vm , r ∈ R produziert, in der r = 0 gilt oder r eine Linearkombination von Standardtermen bzgl. B ist und lt(f ) ≥ lt(vi bi ) f¨ ur alle i gilt.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

55

Dieser Normalform-Algorithmus ist in den verschiedenen CAS (oft nur f¨ ur eine eingeschr¨ankte Auswahl von Termordnungen) implementiert. In MuPAD muss dazu in den Datentyp poly umgewandelt werden. F¨ ur weitere Anwendungen setzen wir dabei gleich den Koeffizientenbereich auf einen sehr allgemeinen Wert und die Termordnung auf LexOrder. DEF:=Dom::ExpressionField(normal): NF:=proc(f,polys,vars) begin expr(groebner::normalf(poly(f,vars,DEF), map(polys,u->poly(u,vars,DEF)), LexOrder)); end_proc: Bei der Berechnung einer Normalform wird f nur um ein Element aus dem Ideal I = Id(B) abge¨andert. Daf¨ ur k¨ onnen wir die aus der Zahlentheorie bekannte Notation der Restklassen verallgemeinern: Definition 15 Zwei Polynome f, g ∈ R heißen kongruent modulo dem Ideal I, wenn f − g ∈ I gilt. Wir schreiben in diesem Fall f ≡ g (mod I). Mit Kongruenzen kann man genauso rechnen, wie wir das von Restklassen ganzer Zahlen gewohnt sind. Insbesondere gilt f ∈ Id(B), wenn wir N F (f, B) = 0 nachweisen k¨onnen. Die Umkehrung dieser Aussage gilt nicht allgemein, da f¨ ur beliebige B eine solche Normalform nicht eindeutig bestimmt ist, sondern vom Reduktionsweg abh¨angen kann. Diese Mehrdeutigkeit wird beseitigt, wenn man von B zu einer Gr¨obnerbasis G = GBasis(B) u obnerbasen zeichnen sich durch eine Reihe zueinander a¨quivalenter Eigenschaften ¨ bergeht. Gr¨ aus: Satz 21 (Charakterisierungssatz f¨ ur Gr¨ obnerbasen) Folgende Bedingungen an eine Basis G eines Ideals I ⊂ R sind ¨aquivalent: 1. G ist eine Gr¨obnerbasis von I, d.h. es gilt Σ(I) = Σ(G). 2. F¨ ur jedes Element f ∈ I und jede Reduktionsstrategie gilt N F (f, G) = 0. 3. Jedes Element f ∈ I hat eine Darstellung X f= hi gi mit ∀ i (lt(f ) ≥ lt(hi gi )). gi ∈G

4. Die Standardterme N (G) bilden eine Vektorraumbasis des Faktorrings R/I, d.h. jedes Element f ∈ R besitzt eine eindeutige Darstellung X cm m (mod I) f≡ m∈N (G)

mit cm ∈ k. Ohne Beweis. Siehe Vorlesung “Gr¨ obnerbasen und deren Anwendungen”. F¨ ur derartige Basen gilt also N F (f, G) = 0 ⇔ f ∈ I und das Ergebnis der Normalformberechnung ist unabh¨ angig vom gew¨ ahlten Reduktionsweg. Die Berechnung von Gr¨ obnerbasen ist ebenfalls in den verschiedenen CAS (f¨ ur eine eingeschr¨ankte Auswahl von Termordnungen) implementiert. Wir wollen den in MuPAD verf¨ ugbaren allgemeinen Algorithmus groebner f¨ ur unsere Zwecke konfigurieren (Grundbrereich ExpressionField und Termordnung LexOrder – beides aus Effizienzgr¨ unden nicht die Defaulteinstellung).

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

56

DEF:=Dom::ExpressionField(normal): GBasis:=proc(polys,vars) begin expr(groebner::gbasis(map(polys,u->poly(u,vars,DEF)),LexOrder)); end_proc: F¨ ur geometrische S¨ atze vom Gleichungstyp k¨onnen wir damit das folgende hinreichende Beweiskriterium formulieren: Satz 22 Gilt N F (g · h, GBasis(F )) = 0, so ist der Satz [F/h ⇒ g] g¨ ultig. Wenden wir dieses hinreichende Kriterium zum Beweis eines geometrischen Satzes vom Gleichungstyp an. Beispiel 1 Arnon-Beispiel ([1, S. 267]): Gegeben sei ein Quadrat ABCD und der Punkt P auf der Parallelen zu BD durch C mit |BP | = |BD|. Sei ferner Q der Schnittpunkt von CD und BP . Man zeige, dass dann |DP | = |DQ| gilt. Eine L¨osung in einem speziellen Koordinatensystem geht von drei Variablen aus: unprotect(D): A:=Point(0,0); B:=Point(1,0); C:=Point(1,1); D:=Point(0,1); P:=Point(x1,x2); Q:=varpoint(C,D,x3); polys:={ on_line(P,par_line(C,pp_line(B,D))), sqrdist(B,D)-sqrdist(B,P), on_line(Q,pp_line(B,P))}; con:=sqrdist(D,Q)-sqrdist(D,P); Wir erhalten als Idealbasis  polys = x1 + x2 − 2, −x1 2 + 2 x1 − x2 2 + 1, 1 − x2 x3 − x1

und als Behauptung

con = −x1 2 − x2 2 + 2 x2 + x3 2 − 2 x3 Die folgende Rechnung zeigt den Unterschied zwischen der Verwendung der Ausgangspolynome und einer Gr¨ obnerbasis: vars:=[x1,x2,x3]; NF(con,polys,vars); x23 − 2 x3 + 4 x2 − 5 da bzgl. der lexikografischen Termordnung im Ausgangssystem polys nur Vielfache von x1 als Leitterme auftreten. Mit der zugeh¨ origen Gr¨obnerbasis gb:=GBasis(polys,vars);  2 x3 − 4 x3 + 1, 2 x2 + x3 − 3, 2 x1 − x3 − 1

liefert die entsprechende Normalform NF(con,gb,vars);

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

57

Null und damit einen Beweis der Behauptung. Allerdings ist es schwierig, die genauen Koordinaten der Punkte P und Q zu bestimmen, denn das Polynom x3 2 + 2 x3 − 2 aus der Gr¨obnerbasis hat zwei Nullstellen f¨ ur x3 (aus denen sich dann jeweils x1 und x2 aus den beiden folgenden Gleichungen eindeutig ergibt). Hat diese zweite L¨osung eine geometrische Bedeutung oder ist sie degeneriert? Ein genauerer Blick auf die geometrische Konfiguration zeigt, dass wir die zweite L¨osung schlichtweg u ¨bersehen haben. Allerdings war dieses Beispiel besonders einfach, weil in ihm alle Variablen durch Gleichungen gebunden waren. F¨ ur allgemeinere Beweisschemata l¨auft der vorgestellte Ansatz meist nicht so glatt durch. Beispiel: Betrachten wir noch einmal den Satz vom Schnittpunkt der Winkelhalbierenden. In dessen Beweisschema treten vier Variable auf. A:=Point(0,0); B:=Point(1,0); C:=Point(c1,c2); P:=Point(x1,x2); polys:={on_bisector(P,A,B,C), on_bisector(P,B,C,A)}; con:=on_bisector(P,C,A,B); Die Gr¨obnerbasis (bzgl. der lexikografischen Termordnung) vars:=[x1,x2,c1,c2]; gb:=GBasis(polys,vars); enth¨alt vier Polynome. Leider kann damit nicht bewiesen werden, dass der Satz gilt, denn die Normalform von con reduziert nicht zu Null. NF(con,gb,vars); 2 x2 − c2 − 2 c1 x2 − 2 x1 x2 + 2 c2 x1 Allerdings reduziert das folgende Produkt zu Null: NF(((c1-1)^2+c2^2)*con,gb,vars); Damit gilt der Satz [F/h ⇒ g] unter der Nichtdegenerationsbedingung h = (c1 − 1)2 + c22 . Deren ¨ Herkunft bleibt an dieser Stelle nat¨ urlich im Dunkeln. Uber den reellen Zahlen entspricht h = 0 dem Fall c1 = 1, c2 = 0, also der degenerierten Situation B = C, in welcher die Gerade BC als Schenkel der beiden Winkel in polys entartet. ¨ Eine spezielle Anwendung von Gr¨ obnerbasen ergibt sich aus folgender Uberlegung: Ist g(x) ein Polynom, das auf allen gemeinsamen Nullstellen von F (x) verschwindet und t eine neue Variable, so hat offensichtlich das System F = 1 − t · g = 0 keine gemeinsamen L¨osungen. Das ist aber nach dem Hilbertschen Nullstellensatz genau dann der Fall, wenn das von diesen Polynomen erzeugte Ideal das Einsideal ist, was wiederum durch eine Gr¨obnerbasisberechnung gepr¨ uft werden kann. Dieser indirekte Beweisansatz ergibt f¨ ur obiges Beispiel mit vars:=[t,x1,x2,c1,c2]; gb:=GBasis([op(polys),1-t*con],vars); jedoch nicht das Einsideal, sondern eine Gr¨obnerbasis mit sechs Elementen. Diese enth¨alt aber wenigstens das Polynom h = (c1 − 1)2 + c22 , so dass f¨ ur gemeinsame L¨osungen von F = 1 − t · g = 0 stets h = 0 gilt. Das kann durch h als Nichtdegenerationsbedingung ausgeschlossen werden, so dass wieder (F/h ⇒ g) bewiesen ist. Diesen Zugang k¨onnen wir zu folgendem hinreichenden Kriterium verallgemeinern:

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

58

Satz 23 Ist t eine neue Variable und h(x) ∈ J = I(F, 1 − t · g), so ist [F/h ⇒ g] g¨ ultig. Aufgabe 17 Diskutieren Sie dieselben Fragen bzgl. des folgenden Beweisansatzes: A:=Point(0,0); B:=Point(1,0); C:=Point(c1,c2); P:=Point(x1,x2); polys:={on_bisector(P,A,B,C), on_bisector(P,C,A,B)}; con:=on_bisector(P,B,C,A); Hinweis: Durch die spezielle Wahl der Koordinaten von A und B kann der degenerierte Fall A = B hier nicht auftreten und [polys ⇒ con] ist ohne weitere Voraussetzungen g¨ ultig.

5.3

Eliminationsideale und Gr¨ obnerbasen

Zur Berechnung eines solchen Polynoms h(x) muss ein t-freies Polynom in J gefunden werden. Meist fordert man, dass h g¨ anzlich nur unabh¨angige“ Variablen enth¨alt. Beide Fragen f¨ uhren auf ” ein Eliminationsproblem: Gegeben ist ein Polynomring R = k[u, x] und ein Ideal J ⊂ R. Gesucht sind alle Polynome in J, die keine der Variablen x ∈ x enthalten, also die Menge J ′ = J ∩ k[u]. Es stellt sich heraus, dass diese Menge ein Ideal im Ring k[u] ist, welches als Eliminationsideal bezeichnet wird. Basen f¨ ur Eliminationsideale k¨ onnen aus Gr¨obnerbasen f¨ ur spezielle Eliminationstermordnungen abgelesen werden. Als Eliminationsordnung f¨ ur u bezeichnet man jede Termordnung, f¨ ur welche t1 ∈ T (u), t2 ∈ T (x ∪ u) \ T (u) ⇒ t1 < t2 gilt. Insbesondere ist die lexikographische Termordnung eine Eliminationsordnung f¨ ur jedes Anfangssegment von Variablen. Satz 24 (Eliminationssatz f¨ ur Gr¨ obnerbasen) Ist G = GBasis(F ) eine (min. reduzierte) Gr¨obnerbasis des Polynomsystems F ⊂ R = k[u, x] bzgl. einer Eliminationsordnung f¨ ur u, so ist G′ = {g ∈ G : lt(g) ∈ T (u)} eine (min. reduzierte) Gr¨obnerbasis des Eliminationsideals J ′ = Id(F )

T

k[u].

Ohne Beweis. Siehe Vorlesung “Gr¨ obnerbasen und deren Anwendungen”.

5.4

Unabh¨ angige und abh¨ angige Variablen

In obigen Beispielen haben wir bereits begonnen, auf einer heuristischen Basis zwischen unabh¨angigen und abh¨ angigen Variablen zu unterscheiden. Dies wollen wir nun pr¨azisieren. Im konstruktiven Fall war eine wesentliche Voraussetzung f¨ ur die G¨ ultigkeit des entsprechenden Mechanisierungssatzes die algebraische Unabh¨ angigkeit der Variablen gewesen. Ist J ⊂ R = k[x1 , . . . , xn ] = R[x] ein Relationenideal, so wollen wir eine Teilmenge u ⊂ x als unabh¨angig modulo J bezeichnen, wenn J ∩ k[u] = (0)

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

59

gilt, d.h. wenn es keine polynomiale Relation in J zwischen den ausgew¨ahlten Variablen gibt. Der Nachweis, dass eine vorgegebene Variablenmenge unabh¨angig ist, wird somit auf ein Eliminationsproblem reduziert, das mit der Berechnung einer Gr¨obnerbasis beantwortet werden kann: Ist G eine Gr¨ obnerbasis von J bzgl. einer Eliminationsordnung f¨ ur u und {lt(g), g ∈ G} ∩ T (u) = ∅, so ist u eine modulo J unabh¨ angige Variablenmenge. Ist J ein Primideal, so haben alle maximalen unabh¨angigen Variablenmengen die gleiche Kardinalit¨at. Diese Anzahl (der unabh¨ angigen Parameter) bezeichnet man auch als die Dimension des Ideals J bzw. der Nullstellenmenge V (J). Ist u eine solche maximale unabh¨angige Variablenmenge ur alle und xi eine weitere Variable, so h¨ angt xi u ¨ ber J algebraisch von den Variablen u ab, d.h. f¨ xi existieren Polynome X cij (u)xji ∈ J fi (xi , u) = j

xi kann man dann zwar im Allgemeinen nicht rational durch die unabh¨angigen Parameter ausdr¨ ucken, jedoch ergibt sich f¨ ur fast alle Parameterbelegungen (genauer: solche, f¨ ur die es ein j mit cij (u) 6= 0 gibt) eine Bestimmungsgleichung f¨ ur xi und damit nur endlich viele zul¨assige Parameterspezifikationen (x0 , u0 ) f¨ ur eine vorgegebene Spezifikation u 7→ u0 . Wenn wir u0 so w¨ahlen, ur alle i gilt, l¨asst sich auch die Anzahl dass sogar lc(fi )(u0 ) 6= 0, also deg(fi ) = deg(fi |u=u0 ) f¨ dieser L¨ osungen voraussagen. Dazu unten mehr.

5.5

Generisch gu ¨ltige Geometrietheoreme

Im Fall der Geometrietheoreme vom konstruktiven und vom linearen Typ haben wir lineare Algebra u orper k(u) der rationalen Funktionen in den unabh¨angigen Parametern getrieben. ¨ ber dem K¨ Wir wollen deshalb nun auch f¨ ur den allgemeinen Fall im Ring S = k(u)[x] der Polynome in x mit rationalen Funktionen in u als Koeffizienten rechnen statt wie bisher im Ring R = k[u, x]. Wir wollen dabei voraussetzen, dass u eine maximale unabh¨angige Vairaiblenmenge modulo J = Id(F ) ist. Betrachten wir zun¨ achst einige Beispiele. Beispiel 1: Satz vom Miquelschen Punkt A:=Point(0,0); B:=Point(1,0); C:=Point(u1,u2); R:=varpoint(B,C,u3); S:=varpoint(A,C,u4); T:=varpoint(A,B,u5); P:=Point(x1,x2); polys:={ is_concyclic(A,S,T,P), is_concyclic(B,R,T,P)}; con:= is_concyclic(C,R,S,P); Wir wollen die Gr¨ obnerbasis von J = Id(polys) im Ring S = k(u)[x1 , x2 ] berechnen: vars:=[x1,x2]; gb:=GBasis(polys,vars); Diese Gr¨ obnerbasis hat eine recht einfache Struktur {x22 − p1 (u) x2 , x1 − p2 (u) x2 − u5 }, so dass das zugeh¨ orige Gleichungssystem zwei L¨osungen (x1 , x2 ) ∈ A2k(u) mit x2.1 = 0 und x2.2 = p1 (u) besitzt. Eine L¨ osung entspricht dem Schnittpunkt F der beiden Kreise, die andere dem Punkt P und erf¨ ullt die Gleichung con: sol:=solve(gb,vars,IgnoreSpecialCases); map(sol,u->normal(subs(con,u)));

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

60

Die L¨osung besteht in diesem Fall also aus zwei Komponenten, wobei der Satz auf einer Komponente gilt, auf der zweiten (aus nahe liegenden Gr¨ unden) dagegen nicht. Es handelt sich dabei jedoch nicht um eine degenerierte Lage wie in fr¨ uheren Beispielen, sondern um einen essentiell auszuschließenden Fall. Beispiel 2: Satz vom Schnittpunkt der Winkelhalbierenden A:=Point(0,0); B:=Point(1,0); C:=Point(u1,u2); P:=Point(x1,x2); polys:={on_bisector(P,B,A,C), on_bisector(P,C,B,A)}; con:= on_bisector(P,A,C,B); gb:=GBasis(polys,vars); NF(con,gb,vars); Als Gr¨obnerbasis erhalten wir hier h 4 u1 2 − 4 u1 + 2 u2 2 2 2 u1 2 − 2 u1 + 2 u1 − 1 2 x2 3 + x2 + x2 − , x1 − 2 2 u2 − 2 u1 u2 u2 − 2 u1 u2 u2 − 2 u1 u2 2 u1 − 1
i 2 u1 2 − 2 u1 + 2 u2 2 3 u2 2 2 x2 4 − x2 − x2 + u2 x2 − −u1 2 + u1 − u2 2 + 1 u2 4

In S = k(u)[x1 , x2 ] ist das davon erzeugte Ideal nulldimensional und hat genau vier Nullstellen in A2K , dem zweidimensionalen affinen Raum u ¨ ber K = k(u), dem algebraischen Abschluss von k(u). Diese entsprechen den vier ( generischen“) Schnittpunkten der m¨oglichen Auswahlen der ” Halbierenden von Innen- und Außenwinkel von ∠ ABC und ∠ BCA. Jeder von ihnen liegt auf der ( generischen“) Halbierenden entweder des Innen- oder des Außenwinkels von ∠ CAB, da ” NF(con, gb) = 0 und folglich con ∈ Id(polys) · S gilt. Die Probleme mit der degenerierten Situation B = C treten nicht auf. Es bleibt zu untersuchen, was das mit der urspr¨ unglichen geometrischen Fragestellung zu tun hat. Beispiel 3: Die Simsonsche Gerade M:=Point(0,0); A:=Point(0,u1); B:=Point(u2,x2); C:=Point(u3,x3); P:=Point(u4,x4); R:=varpoint(A,B,x5); S:=varpoint(B,C,x6); T:=varpoint(A,C,x7); polys:={ is_orthogonal(pp_line(A,B),pp_line(P,R)), is_orthogonal(pp_line(A,C),pp_line(P,T)), is_orthogonal(pp_line(B,C),pp_line(P,S)), sqrdist(M,A)-sqrdist(M,P), sqrdist(M,B)-sqrdist(M,P), sqrdist(M,C)-sqrdist(M,P)}; con:= is_collinear(R,S,T); vars:=[x5,x6,x7,x2,x3,x4]; gb:=GBasis(polys,vars); NF(con,gb,vars); Auch in diesem Fall ist das Ideal Id(polys) ⊂ k(u)[x] nulldimensional. Aus der Gr¨obnerbasis { x22 − (u21 − u22 ), x23 − (u21 − u23 ), x24 − (u21 − u24 ), (2 u1 u3 ) x7 − u3 x4 + u4 x3 − (u1 u3 − u1 u4 ), (2 u1 u2 ) x5 − u2 x4 + u4 x2 − (u1 u2 − u1 u4 ), (2 u21 u2 − 2 u21 u3 ) x6 + u2 x4 x3 + u3 x4 x2 − u4 x3 x2 − (u21 u2 − u21 u3 + u21 u4 − u2 u3 u4 ) }

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

61

lesen wir ab, dass dieses System 8 generische“ L¨osungen besitzt und con auf allen diesen Punk” ten verschwindet, d.h. der Satz von der Simsonschen Geraden generisch“ (d.h. in A2K ) gilt. ” Gr¨obnerbasisberechnungen bzgl. des kompletten Satzes von Variablen dauern deutlich l¨anger und liefern u ¨ berdies keinen Beweis des Satzes, weil degenerierte Komponenten mitgeschleppt worden sind. Der Gr¨ obnerfaktorisierer zerlegt das Beispiel in 9 Komponenten, wovon 8 degenerierten Situationen entsprechen und auf zwei dieser Komponenten con nicht verschwindet (Rechnungen mit Reduce). In allen bisher betrachteten Beispielen besteht die Gr¨obnerbasis aus Gleichungen vom Grad 1 und 2 in den abh¨ angigen Variablen und erlaubt es, die abh¨angigen Variablen durch die unabh¨angigen auszudr¨ ucken, auch wenn es im Gegensatz zum linearen Fall mehrere, aber stets endlich viele L¨osungen f¨ ur x gibt, die sich durch komplizierte universelle Formeln in den Parametern u ausdr¨ ucken lassen. Diese Formeln leben“ nicht mehr in k(u), sondern in einer algebraischen Erweiterung dieses ” Funktionenk¨ orpers. In manchen F¨ allen, wie etwa beim Miquelschen Punkt, ist dar¨ uber hinaus der Satz nicht in allen diesen generischen L¨osungen“ richtig, sondern einige m¨ ussen ausgeschlossen ” werden. Wenn u eine maximale unabh¨ angige modulo J Variablenmenge ist, so ist in jedem Fall das Erweiterungsideal J ′ = J · S ein nulldimensionales Ideal und S/J ′ ein endlichdimensionaler k(u)Vektorraum. Dessen Dimension gibt an, wie viele L¨osungen x es u ¨ ber dem generischen“ Tupel u ” gibt. Beides kann man aus einer Gr¨ obnerbasis G′ = GBasisS (F ) ablesen: Dimension Null liegt vor, wenn die Anzahl der Standardterme Ω = NS (G′ ) endlich ist, die Vektorraumdimension stimmt dann mit dieser Anzahl u ¨berein, da Ω eine k(u)-Vektorraumbasis von S/J ′ ist. Untersuchen wir zun¨ achst den Fall, dass der geometrische Satz auf allen diesen generischen ” L¨osungen“ gilt. Um dies zu testen, haben wir N FS (con, G′ ) = 0 f¨ ur die u ¨ ber S berechnete Gr¨obnerbasis G′ gepr¨ uft. Der folgende Satz gibt eine erste Auskunft, was dieses Ergebnis mit unserer urspr¨ unglichen geometrischen Fragestellung zu tun hat. Satz 25 (Spezialisierungssatz) Sei F ⊂ S = k[u, x] eine Menge von Polynomen, J = Id(F ) das von ihnen erzeugte Ideal, u eine maximal unabh¨angige modulo J Variablenmenge, S = k(u)[x] und G′ = GBasisS (F ) die Gr¨obnerbasis des nulldimensionalen Ideals J ′ = J · S. Dann gilt f¨ ur fast alle Spezifikationen u 7→ u0 der Parameter mit speziellen Werten: • F0 = F |u=u0 ist ein nulldimensionales algebraisches Gleichungssystem, uber S0 = S|u=u0 = k[x] und • G0 = G′ |u=u0 ist dessen Gr¨obnerbasis ¨ • N FS (g(x, u), G′ ) = 0 impliziert N FS0 (g(x, u0 ), G0 ) = 0. Fast alle“ bedeutet in diesem Zusammenhang die Existenz eines Polynoms h(u), so dass die ” Aussage h¨ochstens f¨ ur u0 mit h(u0 ) = 0 nicht gilt. Dieser Satz folgt sofort aus der Existenz des Buchbergeralgorithmus zur Berechnung der Gr¨obnerbasis G′ . W¨ ahlt man die Spezifikation u 7→ u0 so, dass keiner der Faktoren t(u) ∈ k(u), durch die Koeffizienten w¨ ahrend der Rechnungen geteilt wurden, und keiner der Leitkoeffizienten der g ∈ G′ verschwindet, so ergibt der Gr¨ obnertrace der Berechnung von G′ aus F bei Spezialisierung einen Gr¨obnertrace f¨ ur die Berechnung von G0 aus F0 . Als h(u) kann man nun einfach das Produkt all dieser polynomialen Bedingungen nehmen. Angewendet auf Beweisschemata vom Gleichungstyp ergibt sich folgender Satz: Satz 26 (G¨ ultigkeit geometrischer S¨ atze vom Gleichungstyp “im Allgemeinen”) Sei [F (x, u) ⇒ g(x, u)] ein Satz vom Gleichungstyp, u eine f¨ ur diesen Satz maximale unabh¨angige Teilmenge der Variablen und S = k(u)[x]. Gilt N FS (g, GBasisS (F )) = 0, so gibt es eine (effektiv konstruierbare) Nichtdegenerationsbedingung h(u), so dass g auf allen gemeinsamen Nullstellen (x0 , u0 ) von F mit h(u0 ) 6= 0 verschwindet, also der Satz [F/h ⇒ g] gilt.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

62

Auch die Frage, ob u wirklich eine maximale unabh¨angige Teilmenge der Variablen ist, kann an Hand der Gr¨ obnerbasis G′ entschieden werden. Ist G′ = {1} (bzw. enth¨alt ein Polynom aus k[u]), ′ so ist J = IdS (F ) das triviale Ideal und u war in Wirklichkeit algebraisch abh¨angig modulo J. Ansonsten ist u algebraisch unabh¨ angig modulo J und maximal genau dann, wenn S/J ′ nulldi′ mensional ist, d.h. G zu jeder x-Variablen ein Polynom enth¨alt, dessen Leitterm eine reine Potenz in dieser Variablen ist. h(u) im Rahmen fertiger Gr¨ obnerpakete aufzusammeln ist schwierig. Allerdings folgt allein aus der Existenz von h ∈ k[u], dass eine zuf¨allige“ Wahl von u0 normalerweise“ zul¨assig ist. Deshalb ” ” auch G¨ ultigkeit im Allgemeinen“. ” Es ist auch plausibel, dass wenigstens f¨ ur ein Radikalideal J ′ aus dem Nichtverschwinden von N FS (g, GBasisS (F )) folgt, dass g auf wenigstens einer der allgemeinen“ Nullstellen von F nicht ” verschwindet und folglich nicht allgemeing¨ ultig ist.

5.6

Eine geometrische Interpretation des Spezialisierungssatzes

Um den Zusammenhang zwischen diesen allgemeinen“ Nullstellen und dem (uns eigentlich interes” sierenden) Nullstellengebilde VR (F ) besser zu verstehen, m¨ ussen wir den Zusammenhang zwischen Nullstellen VR (F ) von F u ¨ ber R = k[x, u] und VS (F ) u ¨ber S = k(u)[x] genauer studieren. Der Polynomring S enth¨ alt R als Unterring. Das von F in S erzeugte Ideal J ′ = IdS (F ) = J · S bezeichnet man als das Erweiterungsideal von J. Umgekehrt k¨onnen wir mit einem Ideal J ′ ⊂ S das Kontraktionsideal J ′ ∩ R in R verbinden, das aus allen rationalen Kombinationen der Erzeugenden besteht, in denen sich die Nenner wegk¨ urzen“. Sicherlich ist J ⊂ J ′ ∩ R. ” Die Elemente des Rings S sind Polynome in den Variablen x mit rationalen Funktionen in u als Koeffizienten. Durch Hauptnennerbildung u ¨ berzeugt man sich leicht, dass man jedes Element mit z ∈ R und n ∈ U = k[u] \ {0} darstellen kann. Die Menge U ist aus S in der Form z(x,u) n(u) multiplikativ, d.h. n1 , n2 ∈ U impliziert n1 n2 ∈ U , womit die u ur Br¨ uche ¨ blichen Rechenregeln f¨ Anwendung finden k¨ onnen. Wir schreiben deshalb auch o nz : z ∈ R, n ∈ U S = U −1 R := n und nennen den Ring S die Lokalisierung von R nach der multiplikativen Menge U .

Zun¨achst wollen wir das Erweiterungsideal J ′ = J ·S genauer beschreiben. Dessen Elemente lassen sich in der Form P X zf hf f u= f= nf n f ∈F P mit zf , hf ∈ R, nf , n ∈ U darstellen. Da hf f genau die Elemente aus J sind, erkennen wir, dass J ′ aus genau den Elementen von S besteht, die sich in der Form nz mit z ∈ J, n ∈ U darstellen lassen. Entsprechend besteht das Kontraktionsideal J ′ ∩ R aus allen solchen Elementen, die außerdem noch polynomial auch in u sind, d.h. f¨ ur die zus¨atzlich z vollst¨andig durch n teilbar ist: J ′ ∩ R = {r ∈ R : ∃ n ∈ U (n · r ∈ J)}. Das erinnert an die Definition des Idealquotienten. Allerdings kommen die Kofaktoren hier nicht aus einem Ideal. Wir hatten gesehen, dass jedes Radikalideal J als Durchschnitt endlich vieler Primideale J = ∩ Pα darstellbar ist. Eine bzgl. J unabh¨ angige Variablenmenge u muss allerdings bzgl. einer dieser Primkomponenten, die ja gr¨ oßer sind als J, nicht mehr unabh¨angig sein. Wir erkennen das daran, ob Pα ∩ U = ∅ gilt (in diesem Fall bleibt die Variablenmenge unabh¨angig) oder nicht (in diesem Fall gibt es eine algebraische Beziehung hα (u) ∈ Pα zwischen den eigentlich unabh¨angigen Variablen u).

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

63

Komponenten der ersten Art nennen wir generisch, Komponenten der zweiten Art speziell. Zerlegen wir das Nullstellengebilde der Voraussetzungen eines Geometrietheorems in seine Komponenten, so entsprechen letztere gewissen, durch hα (u) = 0 beschriebenen, degenerierten Situationen. Satz 27 (1) Sei J ein Radikalideal und J = ∩ Pα dessen Zerlegung in Primkomponenten. Dann gilt \ J′ = J · S = (Pα · S) . (2) Pα · S =

(

ein Primideal Qα ⊂ S mit Qα ∩ R = Pα (1)

wenn Pα ∩ U = ∅ wenn Pα ∩ U 6= ∅

Beweis : (1) Wegen J ⊂ ∩ Pα folgt J · S ⊂ ∩ (Pα · S). Sei umgekehrt u ∈ ∩ (Pα · S). Nach geeigneter Hauptnennerbildung hat es eine Darstellung der Form u = nz mit z ∈ ∩ Pα = J, n ∈ U , also u ∈ J · S. (2) Sei 0 6= s ∈ Pα ∩ U . Dann ist 1 =

s s

∈ Pα · S.

Sei Pα ∩ U = ∅ und Qα := Pα · S. Qα ist ein Primideal: Aus u1 u2 =

p1 p2 p = ∈ Qα n1 n2 n

mit p1 , p2 ∈ R, p ∈ Pα , n, n1 , n2 ∈ U folgt n · p1 p2 ∈ Pα und wegen n 6∈ Pα und dessen Primidealeigenschaft schließlich p1 p2 ∈ Pα . Qα ∩ R = {u ∈ R : ∃ n ∈ U (n · u ∈ Pα )}. Wie eben folgt dann bereits u ∈ Pα .



Folgerung 1 J ′ ∩ R = ∩{Pα : Pα ∩ U = ∅} Ist insbesondere g ein Polynom in R, F ⊂ R eine Menge von Polynomen und G′ = GBasisS (F ), so gilt N FS (g, G′ ) = 0 genau dann, wenn g auf allen generischen Komponenten von VR (F ) verschwindet. Wir sagen in diesem Fall, dass der geometrische Satz bzgl. der unabh¨angigen Variablenmenge u generisch richtig ist, was folgendes heißt: Satz 28 (Generische G¨ ultigkeit geometrischer S¨ atze vom Gleichungstyp) Sei [F (x, u) ⇒ g(x, u)] ein Satz vom Gleichungstyp, u eine f¨ ur diesen Satz maximale unabh¨angige Teilmenge der Variablen und S = k(u)[x]. Gilt N FS (g, GBasisS (F )) = 0, so ist [F ⇒ g] auf allen generischen Komponenten von VR (F ) richtig. Die Aussage g = 0 ist h¨ ochstens auf speziellen Komponenten von V (F ) falsch, auf denen aber die Variablen u nicht mehr unabh¨ angig sind. Jede solche Komponente enth¨alt im definierenden Ideal ein Polynom hα (u). Das Produkt dieser Polynome k¨onnen wir als Nichtdegenerationsbedingung nehmen. Ist umgekehrt N FS (g, G′ ) 6= 0, so verschwindet g auf einer der generischen Komponenten nicht, d.h. kann durch keine Nichtdegenerationsbedingung, die nur die unabh¨angigen Parameter enth¨alt, gerettet werden. Generell, wenn N FS (g, G′ ) nicht verschwindet, wie oben im Beispiel Miquelscher Punkt, liefern uns Untersuchungen in S Aussagen, die das Verhalten auf speziellen Komponenten ausblenden.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

64

In diesem Beispiel hat V (J) zwei generische Komponenten. Eine entspricht dem Schnittpunkt F der Kreise durch A, F, E und B, F, D, die andere dem gesuchten Schnittpunkt P . Auf der ersteren Komponente gilt der Satz nicht, auf der zweiteren sehr wohl. Der Gr¨obnerfaktorisierer zeigt, dass V (J) daneben noch eine weitere spezielle Komponenten hat, welche die Bedingung c1 = 0 enth¨alt und einer degenerierten Lagen entspricht. In einem solchen Fall ist aber der Kreis und damit auch der Schnittpunkt P nicht mehr eindeutig bestimmt, so dass wir auch nicht pr¨ ufen k¨onnen, ob er auf dem dritten Kreis liegt.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

6 6.1

65

Beispiele Die Tangente an einen Kreis c in einem Punkt P ∈ c

Diese ergibt sich als Senkrechte im Punkt P auf dem Ber¨ uhrungsradius. Die homogenen Koordinaten dieser Geraden k¨ onnen also wie folgt berechnet werden: P:=Point(x1,x2); c:=[c1,c2,c3,c4]; l:= ortho_line(P,pp_line(circle_center(c),P)); 

c2 + 2 x1 c1 , 2 x2 c1 + c3 , −2 x2 2 c1 − x2 c3 − x1 c2 − 2 x1 2 c1



Wegen on circle(P,c)=0 kann die dritte Komponente weiter vereinfacht werden: l[3]+2*on_circle(P,c); x2 c3 + x1 c2 + 2 c4 Diese Formel k¨ onnen wir in eine neue Prozedur gießen. tangent_line:=proc(P,c) if on_circle(P,c)0 then error("Point not on the circle") fi; [2*c[1]*P[1]+c[2],2*c[1]*P[2]+c[3],c[2]*P[1]+c[3]*P[2]+2*c[4]]; end; Eine ¨ahnliche Formel gilt auch f¨ ur Tangenten an allgemeine Quadriken. Mit dieser Funktion l¨ asst sich ein konstruktives Beweisschema f¨ ur den Satz von Brian¸ con f¨ ur einen Kreis erstellen: Sind t1 , . . . , t6 sechs Tangenten an einen Kreis c und Qi = ti ∩ ti+1 jeweils die Schnittpunkte benachbarter“ Tangen” ten (mit t7 = t1 ), so gehen die drei Geraden Q1 Q4 , Q2 Q5 und Q3 Q6 durch einen gemeinsamen Punkt.

Satz von Brian¸con

delete P, t, Q, l; M:=Point(0,0); P[1]:=Point(1,0); c:=pc_circle(M,P[1]); (P[i]:=circle_slider(M,P[1],u[i]))$i=2..6; (t[i]:=tangent_line(P[i],c))$i=1..6; t[7]:=t[1]; (Q[i]:=intersection_point(t[i],t[i+1]))$i=1..6; (l[i]:=pp_line(Q[i],Q[i+3]))$i=1..3; is_concurrent(l[1],l[2],l[3]);

6.2

Wann beru ¨hrt eine Gerade l einen Kreis c?

Wir stellen zun¨ achst die Gleichungen auf, aus denen sich die Koordinaten der Schnittpunkte X = (x1 , x2 ) ∈ l ∩ c bestimmen lassen polys:={c1*(x1^2+x2^2)+c2*x1+c3*x2+c4, l1*x1+l2*x2+l3};

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

66

und berechnen dazu eine Gr¨ obnerbasis gb:=GBasis(polys,[x1,x2]); 

c3 l 1 2 − c2 l 2 l 1 + 2 c1 l 2 l 3 l3 l2 x2 c4 l 1 2 − c2 l 1 l 3 + c1 l 3 2 + x2 x1 + + , x2 2 + l1 l1 c1 l 1 2 + c1 l 2 2 c1 l 1 2 + c1 l 2 2



Aus der einen Gleichung, welche die Form x22 + C + Bx2 hat, k¨onnen die beiden Koordinaten f¨ ur x2 berechnet werden; der zugeh¨ orige Wert von x1 ergibt sich dann eindeutig aus der anderen Gleichung. Zwischen l und c liegt genau dann eine Ber¨ uhrsituation vor, wenn die beiden Nullstellen der Gleichung f¨ ur x2 zusammenfallen, d.h. wenn B 2 − 4 A C verschwindet. cc:=[coeff(poly(gb[2],[x2]))]; con:=numer(factor(cc[2]^2-4*cc[1]*cc[3])); Dieses Polynom enth¨ alt noch einen geometrisch irrelevanten Faktor −l12 , so dass wir als Ber¨ uhrbedingung (nach einiger Termumformung) gerade 4 c1 ((−c1 l3 + c2 l1 + c3 l2 ) l3 − c4 (l12 + l22 )) + (c2 l2 − c3 l1 )2 erhalten. Dieses Polynom stimmt mit der Bedingung u ¨ berein, die sich aus einer mehr geometrischen Argumentation ergibt: Eine Ber¨ uhrsituation liegt genau dann vor, wenn der Fußpunkt des Lots aus dem Kreismittelpunkt von c auf die Gerade l (im Allgemeinen ist das die Mitte der Sehne, die c aus l ausschneidet) selbst auf dem Kreis liegt: c:=[c1,c2,c3,c4]; l:=[l1,l2,l3]; on_circle(pedalpoint(circle_center(c),l),c); Diese Bedingung k¨ onnen wir ebenfalls in eine neue Prozedur gießen. is_cl_tangent:=proc(c,l) local c1,c2,c3,c4,l1,l2,l3; c1:=c[1]; c2:=c[2]; c3:=c[3]; c4:=c[4]; l1:=l[1]; l2:=l[2]; l3:=l[3]; normal(4*c1*((-c1*l3+c2*l1+c3*l2)*l3-c4*(l1^2+l2^2))+(c2*l2-c3*l1)^2); end;

Damit k¨ onnen wir folgenden Satz beweisen: Seien A, B, C, D vier Punkte auf einem Kreis c, E der Schnittpunkt von AB und CD, F der Schnittpunkt von BC und der Parallelen zu AD durch E und G der Ber¨ uhrpunkt der Tangente aus F an den Kreis c. Dann ist |EF | = |F G|. Hier ist ein entsprechendes Beweisschema

// Points unprotect(O); unprotect(D); unprotect(E); O:=Point(0,0); A:=Point(1,0); // coordinates B:=circle_slider(O,A,u2); C:=circle_slider(O,A,u3);

E B

C F

A G D

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

67

D:=circle_slider(O,A,u4); E:=intersection_point(pp_line(B,A),pp_line(C,D)); F:=intersection_point(par_line(E,pp_line(A,D)), pp_line(B,C)); G:=circle_slider(O,A,x1); // polynomials p:=is_cl_tangent(pc_circle(O,A),pp_line(F,G)); // conclusion con:=eq_dist(E,F,F,G); Der folgende Vergleich zeigt, dass das Polynom p im Wesentlichen das Quadrat des Polynoms con ist, woraus sich unmittelbar die G¨ ultigkeit des Satzes ergibt: factor(p/4); numer(con)/4; Wir k¨onnen auch den Satz vom Brocardschen Punkt beweisen: Zum Dreieck ABC betrachten wir den Kreis durch A, der BC in C ber¨ uhrt, den Kreis durch B, der AC in A ber¨ uhrt und den Kreis durch C, der AB in B ber¨ uhrt. Diese drei Kreise gehen durch einen gemeinsamen Punkt, den Brocardschen Punkt. Ein Beweisschema sieht wie folgt aus:

C

A B

Satz vom Brocardschen Punkt

A:=Point(0,0); B:=Point(1,0); C:=Point(u1,u2); M1:=Point(x1,x2); M2:=Point(x3,x4); M3:=Point(x5,x6); P:=Point(x7,x8); // coordinates c1:=pc_circle(M1,A); c2:=pc_circle(M2,B); c3:=pc_circle(M3,C); // polynomials polys:=[ is_cl_tangent(c1,pp_line(A,C)), on_circle(B,c1), is_cl_tangent(c2,pp_line(A,B)), on_circle(C,c2), is_cl_tangent(c3,pp_line(B,C)), on_circle(A,c3), on_circle(P,c1), on_circle(P,c2)]; // conclusion con:= on_circle(P,c3); Die Beweisidee geht wieder vom Schnittpunkt P zweier der Kreise aus und versucht zu zeigen, dass P auch auf dem dritten Kreis liegt. Allerdings haben die beiden Kreise c1 und c2 neben P noch den Punkt B gemeinsam, so dass a¨hnliche Probleme zu u ¨ berwinden sind wie beim Satz von Miquel. Gr¨ obnerbasen helfen nicht so recht vars:=[x.i$i=1..8]; gb:=GBasis(polys,vars); sol:=solve(polys,vars,IgnoreSpecialCases); MuPAD kommt hier gar nicht durch, mit Maple geht es teilweise.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

68

TO:=plex(x1,x2,x3,x4,x5,x6,x7,x8); gb:=gbasis(polys_,TO); Erst mit dem Gr¨ obnerfaktorisierer (Maple) kommt man weiter gbs:=convert(gsolve(polys_,{op(TO)}),list); map(u->normalf(con_,u[1],u[2]),gbs); Das Ergebnis zeigt, dass der Satz auf einer der beiden Komponenten richtig ist. Die andere Komponente entspricht dem Schnittpunkt P = B: map(u->normalf(sqrdist(B_,P_),u[1],u[2]),gbs); Spaltet man die Komponente P = B ab, so bleibt ein Satz vom linearen Typ u ¨brig: sol:=solve({op(polys_)},{op(TO)}); map(u->normal(subs(u,con_)),[sol]); Zu diesem Satz existiert auch ein konstruktives Beweisschema. Dazu u ¨ berlegen wir uns, wie die Kreise ci konstruiert werden k¨ onnen (das ist auch erforderlich, um ein Bild zum Satz zu zeichnen). A, B, C haben dieselben Koordinaten wie oben (Rechnungen wieder mit MuPAD) // coordinates M1:=intersection_point(altitude(A,A,C),p_bisector(A,B)); M2:=intersection_point(altitude(B,B,A),p_bisector(B,C)); M3:=intersection_point(altitude(C,C,B),p_bisector(A,C)); c1:=pc_circle(M1,A); c2:=pc_circle(M2,B); c3:=pc_circle(M3,C); P:=other_cc_point(B,c1,c2); // conclusion on_circle(P,c3);

6.3

Schnittpunkts¨ atze und die Potenzgerade zweier Kreise

Bestimmen wir die Koordinaten der Schnittpunkte zweier Kreise: M1:=Point(0,0); A1:=Point(0,r1); M2:=Point(d,0); A2:=Point(d,r2); P:=Point(x1,x2); polys:={on_circle(P,pc_circle(M1,A1)), on_circle(P,pc_circle(M2,A2))}; sol:=solve(polys,{x1,x2},IgnoreSpecialCases); Wir sehen, dass sich die x1 -Koordinate rational ausdr¨ ucken l¨asst. Im Fall sich schneidender Kreise verl¨auft die Gerade x = x1 offensichtlich durch die beiden Schnittpunkte der Kreise. Schneiden sich die beiden Kreise nicht, so ergeben sich imagin¨are x2 -Koordinaten. Gleichwohl ist x = x1 noch immer eine (reelle) Gerade durch diese beiden (imagin¨aren) Schnittpunkte. Diese Gerade, die auf der Mittellinie der beiden Kreise senkrecht steht, bezeichnet man als Potenzgerade der beiden Kreise. Sie spielt eine wichtige Rolle in verschiedenen geometrischen Situationen. ¨ Zun¨achst jedoch ergibt sich aus unseren Uberlegungen, dass sich die Koordinaten der Potenzgeraden aus denen der beiden Kreise rational berechnen lassen, wir also Potenzgeraden in S¨atzen vom konstruktiven Typ verwenden k¨ onnen. Eine solche lineare Gleichung ist im Ideal enthalten, das

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

69

von den beiden Kreisgleichungen p1 = c1 (x21 + x22 ) + c2 x1 + c3 x2 + c4 p2 = d1 (x21 + x22 ) + d2 x1 + d3 x2 + d4 erzeugt wird, die Linearform d1 p1 − c1 p2 . F¨ ur die Berechnung der Koordinaten der Potenzgeraden ergibt sich damit folgende Formel: radical_axis:=proc(c::Circle,d::Circle) Line(seq(normal(c[1]*d[i]-c[i]*d[1]), i=2..4 )) end; Haben die sich schneidenden Kreise ci die Radien ri , so k¨onnen wir die L¨angen der Abschnitte di zwischen Mittelpunkt Mi und dem Schnittpunkt D der Potenzgeraden mit der Mittellinie bestimmen: d2i = ri2 − x2 , wobei x die L¨ange der Strecke zwischen D und einem der Schnittpunkte der beiden Kreise ist. Ist P ein beliebiger Punkt auf der Potenzgeraden mit Abst¨anden ri′ von den Kreismittelpunkten und x′ von D, so gilt ri′2 = d2i + x′2 und folglich r1′2 − r12 = r2′2 − r22 . Den Wert r1′2 − r12 bezeichnet man auch als die Potenz des Punktes P bzgl. des Kreises c1 . Die Potenz ist genau dann positiv, wenn P außerhalb von c1 liegt. In diesem Fall kann man diese Gr¨oße als Quadrat der L¨ ange eines der Tangentenabschnitte von P an c1 interpretieren. Die Punkte auf der Potenzgeraden zweier Kreise lassen sich damit als geometrischer Ort all der Punkte charakterisieren, die bzgl. der beiden Kreisen gleiche Potenz (d.h. gleichlange Tangentenabschnitte, wenn außerhalb der Kreise gelegen) haben. Diese Charakterisierung h¨angt nicht davon ab, ob die Kreise sich schneiden.

Zu drei Kreisen kann man drei verschiedene Kreispaare und damit auch drei verschiedene Potenzgeraden bilden. Aus der eben gefundenen geometrischen Charakterisierung folgt sofort, dass diese drei Potenzgeraden durch einen gemeinsamen Punkt gehen. Diesen Satz (vom konstruktiven Typ) k¨onnen wir nat¨ urlich auch mechanisiert beweisen: Drei sich schneidende Potenzgeraden c:=[c1,c2,c3,c4]; d:=[d1,d2,d3,d4]; e:=[e1,e2,e3,e4]; is_concurrent(radical_axis(c,d), radical_axis(c,e), radical_axis(d,e)); Dieser Satz liefert auch eine einfache M¨oglichkeit, die Potenzgerade zweier sich nicht schneidender Kreise zu konstruieren: Zeichne einen dritten Kreis, der die beiden anderen Kreise schneidet. Die Potenzgeraden mit dem dritten Kreis (also die Verbindungsgeraden der Kreisschnittpunkte) schneiden sich in einem Punkt, der auf der Potenzgerade der beiden urspr¨ unglichen Kreise liegt. Wir k¨onnen diese Potenzgerade nun konstruieren, denn sie steht noch auf der Mittellinie ihrer beiden Kreise senkrecht. Falls sich die beiden Kreise ber¨ uhren, so ist die Potenzgerade genau die gemeinsame Tangente. Also k¨onnen wir die Ber¨ uhrbedingung zweier Kreise auf die von Kreis und Gerade zur¨ uckf¨ uhren: is_cc_tangent(c1,c2)==is_cl_tangent(c1,radical_axis(c1,c2))

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

70

Damit k¨ onnen wir ein Beweisschema f¨ ur eine interessante Eigenschaft des Feuerbaschen Kreises formulieren: Der Feuerbachkreis ber¨ uhrt den Inkreis und die drei Ankreise des Dreiecks. Wir vereinbaren zun¨ achst die Punkte, die zur Spezifikation der Aufgabenstellung erforderlich sind. A:=Point(0,0); B:=Point(2,0); C:=Point(u1,u2); // coordinates M:=intersection_point(p_bisector(A,B), p_bisector(B,C)); H:=intersection_point(altitude(A,B,C),altitude(B,C,A)); N:=midpoint(M,H); c1:=pc_circle(N,midpoint(A,B)); F¨ ur den Inkreis und die drei Ankreise starten wir mit dem jeweiligen Mittelpunkt P , dessen Koordinaten (x1 , x2 ) die Bedingungen erf¨ ullt, dass P auf zwei der Winkelhalbierendenpaare liegt (und damit automatisch auf dem dritten Paar). Zur Definition des Kreises brauchen wir noch einen Punkt Q auf der Peripherie, wof¨ ur wir das Lot aus P auf AB verwenden. Zwar h¨atten wir auch gleich Q = (x1 , 0) schreiben k¨ onnen, aber das ist nur f¨ ur die spezielle Wahl der Koordinaten richtig und damit das Beweisschema nicht f¨ ur andere Zwecke verwendbar. P:=Point(x1,x2); Q:=pedalpoint(P,pp_line(A,B)); // polynomials polys:=[on_bisector(P,A,B,C), on_bisector(P,B,C,A)]; // conclusion con:=is_cc_tangent(pc_circle(P,Q),c1); Den Beweis k¨ onnen wir nun u uhren: ¨ ber den Gr¨obnerbasisansatz leicht f¨ vars:=[x1,x2]; gb:=GBasis(polys,vars); NF(con,gb,vars);

Literatur [1] S.-C. Chou. Proving elementary geometry theorems using Wu’s algorithm. In Contemp. Math., volume 19, pages 243 – 286. AMS, Providence, Rhode Island, 1984. [2] H.S.M. Coxeter and S.L. Greitzer. Geometry revisted. Toronto – New York, 1967. [3] The GeoProver package for mechanized (plane) geometry theorem proving, version 1.3a, 2003. see http://www.informatik.uni-leipzig.de/∼graebe. [4] The SymbolicData project, 2000–2002. see http://www.symbolicdata.org. [5] W.-T. Wu. Mechanical Theorem Proving in Geometries. Number 1 in Texts and Monographs in Symbolic Computation. Springer, Wien, 1994.

Prof. Gr¨abe: Geometrie mit dem Computer – Vorlesungsnotizen (July 18, 2007)

7

71

Aufgaben

Beweisen Sie die folgenden Geometrietheoreme durch Zur¨ uckf¨ uhrung auf S¨atze vom konstruktiven Typ oder vom Gleichungstyp. Versuchen Sie, ob sie auch elementargeometrische Beweise finden k¨onnen. 1. Beweisen Sie den Satz vom H¨ ohenfußpunktdreieck: Ist ∆ ABC ein Dreieck mit den H¨ohenfußpunkten D, E, F , so wird der Winkel ∠ DEF von der H¨ohe durch E halbiert. Finden Sie auch die entsprechenden Nicht-Degenerations-Bedingungen. 2. Zeigen Sie, dass die 6 Fußpunkte der Lote von den H¨ohenfußpunkten D, E, F auf die gegen¨ uberliegenden Dreiecksseiten (oder deren Verl¨angerungen) auf einem gemeinsamen Kreis, dem Taylorkreis, liegen. 3. Beweisen Sie die Umkehrung des Satzes von der Simsonschen Geraden: Sind die Lotfußpunkte R, S, T von einem Punkt P auf die Seiten des Dreiecks ∆ ABC oder deren Verl¨angerungen kollinear, so liegt P auf dem Umkreis des Dreiecks. 4. Beweisen Sie auch folgende Verallgemeinerung: Ist M der Umkreismittelpunkt des Dreiecks ∆ ABC und P, R, S, T wie eben, so h¨angt der Fl¨ acheninhalt F (∆ RST ) nur von |M P | ab. Finden Sie eine genaue Formel f¨ ur diesen Fl¨acheninhalt. 5. Beweisen Sie die Fl¨ acheninhaltsformel F (∆ ABC) =

abc , 4R

wobei a, b, c die Seitenl¨ angen und R der Umkreisradius ist. 6. Beweisen Sie die Fl¨ acheninhaltsformel F (∆ ABC) = ρ ·

a+b+c , 2

wobei a, b, c die Seitenl¨ angen und ρ der Inkreisradius ist. Wie ist die Formel f¨ ur die Ankreisradien ρA , ρB und ρC zu modifizieren? 7. Gegeben sei ein Kreis k, die Tangente von B an diesen Kreis, A der Ber¨ uhrungspunkt, M der Mittelpunkt von AB und D ein Punkt auf dem Kreis k. C sei der Schnittpunkt von DM mit k, E der Schnittpunkt von BD mit k und F der Schnittpunkt von BC mit k. Zeigen Sie, dass EF parallel zu AB ist. 8. Beweisen Sie, dass die Lote durch die drei Ankreiszentren auf die jeweilige Dreiecksseite durch einen gemeinsamen Punkt gehen.