Beweise

In den vorangegangenen Kapiteln wurden die Beweise, dass der vorgestellte Min-Schritt die bestmögliche Bézierkurve berechnet, nicht aufgeführt, um den Lesefluss nicht zu stören. Daher sollen sie in diesem Kapitel Berücksichtigung finden.

Die Lösungsmenge eines linearen Gleichungssystems ist ein linearer Unterraum¹⁸. Durch die Einschränkung, dass die Einträge der Lösungen alle positiv und beschränkt sind, wird die Lösungsmenge auf einen Polyeder eingeschränkt¹⁹. Dies soll im Folgenden erläutert werden.

Es sei eine gültige elementare Bézierkurve an der Kante eines Polygonzuges gegeben, welche die Punkte $P1$ und $P2$ verbindet (siehe Abbildung 18). Wenn der Punkt $Pt1$ auf der Winkelhalbierenden $Vt1$ nun soweit ins Innere des Polygonzuges verschoben wird, bis die Tangente $V1$ in diesem Punkt durch den Punkt $P2$ verläuft, muss der mittlere Kontrollpunkt auf der Tangente liegen und ist mit dem Punkt $P2$ identisch. Da nun alle drei Kontrollpunkte auf einer Geraden liegen, liegt die Bézierkurve ebenfalls auf der Geraden. Der Parameter $d_1$ müsste nun negativ sein, um die Gleichung 9 zu erfüllen, was keiner korrekten Approximation entsprechen würde. Somit muss $t_1$ beschränkt sein.

Abbildung 18: $t_1$ muss beschränkt sein.

Für den Parameter $d_1$ gilt Folgendes. Um den Abstand zwischen Bézierkurve und Polygonzugkante zu vergrößern, muss der Kontrollpunkt von der Kante entfernt werden. Die maximale Entfernung ist diejenige, bei der die Parameter $t_1$ und $t_2$ den Wert Null annehmen. Da der mittlere Kontrollpunkt durch den Schnittpunkt der beiden Tangenten definiert ist, würde ein weiteres Entfernen des mittleren Kontrollpunktes von der Kante, dazu führen, dass der Parameter $t_1$ oder $t_2$ negativ wird, was wiederrum zu einer nicht gültigen Approximation führt. Damit kann der Parameter $d_1$ nicht größer werden, und ist somit beschränkt (siehe Abbildung 19). Da die Parameter alle positiv sein sollen, sind alle Parameter beschränkt und die gültige Lösungsmenge ist ein Polyeder.

Abbildung 19: $d_1$ muss beschränkt sein.

Die Summe der Einträge ist eine Zielfunktion und das Minimum wird in einer Ecke des Polyeders eingenommen²⁰. Jede Ecke des Polyeders entspricht dabei einer Basislösung. Der hier angewendete Min-Schritt ist ein spezieller Austauschschritt, in dem von einer Ecke zu einer günstigeren Ecke, also von einer Basislösung zu einer besseren Basislösung, übergegangen wird²¹. Ein solcher Übergang kann, wenn eine Degenerierung des Gleichungssystems eingetreten ist, nach den oben genannten Kriterien nicht immer durchgeführt werden.

Eine Degenerierung tritt ein, wenn ein Eintrag in der b-Spalte zu dem Wert Null umgeformt wird²². Wenn nun zu keiner günstigeren Ecke übergegangen werden kann, das Gleichungssystem aber degeneriert ist, müssen alle möglichen Formen, die das Gleichungssystem an dieser Ecke haben kann, erzeugt werden und es muss geprüft werden, ob ein Min-Schritt von diesem Gleichungssystem ausgehend möglich ist. Ist von keiner dieser Gleichungssysteme ein Min-Schritt möglich, ist das Minimum erreicht²³.