Vorgehen:

Das hier vorgestellte Verfahren ist optimiert. Alle überflüssigen Hyperebenen werden in ihm ignoriert.

0 Initialisiere die Hyperebenen ($K$ und $E$) mit dem Hyperkörper der maximalen Lösungsmenge (eventuell unter Zuhilfenahme von $v_{max}$)

1 Prüfe $i$:

1.1 Fall 1: Wenn $i$ größer $n$, setze $i$ auf $n$ und gehe zu "8. Lösung ermitteln"

1.2 Sonst: Nehme nächste Ungleichung $U_i$

1.2.1 Erstelle eine orientierte Hyperfläche $H$ für aktuelle Ungleichung $U_i=U[i]$ als Normalgleichung, mit dem Normalenvektor $N$ in Richtung der zulässigen Lösungen. Aus der Ungleichung $U_i$ in der Form $y_i \leq a_1 * x_{i.1} + a_2 * x_{i.2} + \ldots + a_d * x_{i.d}$ wird die Normalengleichung $\vec{x_i} \cdot \vec{a} - y_i = 0$ mit $\vec{x_i} = (x_{i.1}, \ldots, x_{i.d})^T$ und $\vec{a} = (a_{1}, \ldots, a_{d})^T$

2. Prüfe für alle Punkte auf welcher Seite der Hyperflache $H$ sie liegen

2.1 Fall 1: alle Eckpunkte $E_k$ liegen in Richtung des Normalenvektors $N$ oder auf der Hyperebene -> erhöhe Zähler $i$ und gehe zu 1. (die Hyperfläche $H$ schränkt die Lösungsmenge nicht weiter ein, d. h. $H$ ist nicht relevant)

2.2 Fall 2: alle Eckpunkte $E_k$ liegen nicht in Richtung des Normalenvektors $N$ -> erniedrige Zähler $i$ und gehe zu "8. Lösung ermitteln" (durch die Hinzunahme der Ungleichung $U_i$ gäbe es keine Lösungen mehr, bzw. die Ungleichung $U_i$ macht das bisherige Gleichungsystem unlösbar)

2.3 Sonst: einige Eckpunkte $E_k$ liegen in Richtung des Normalenvektors $N$, andere nicht -> gehe zu Schritt 3., bzw. integriere die Hyperfläche $H$ in den konvexer Hyperkörper der möglichen Lösungen

3. Für jede Hyperfläche $H_e$ mit der Dimensionalität $n-1$ (diese entsprechen den Ungleichungen) aus $K$ (konvexer Hyperkörper der möglichen Lösungen):

3.1 Berechne die Schnittebene (Dimensionalität ist $n-2$) von $H_e$ und $H$

3.1.1 Fall 1: wenn keine Schnittebene existiert -> gehe zu 3.1 und prüfe die nächste Hyperfläche $H_e$

3.1.2 Sonst: wenn eine Schnittebene $S$ existiert:

3.1.2.1 Wenn eine identische Hyperfläche wie die Schnittebene $S$ in den Hyperflächen $K$ existiert (bzw. es existiert keine neue Hyperfläche)

3.1.2.1.1 Vermerke zu der gefundenen Schnittebene als Verweise die Hyperfläche $H$ als die enthaltende Hyperfläche

3.1.2.1.2 Füge zu der Hyperfläche $H$ als Verweise die Schnittebene $S$ als eine enthaltende Hyperflächen hinzu

3.1.2.1.3 gehe zu 3.1 und prüfe die nächste Hyperfläche $H_e$

3.1.2.2 Vermerke zu der Schnittebene $S$ als Verweise die Hyperflächen $H$ und $H_e$ als die enthaltenden Hyperflächen

3.1.2.3 Füge zu den Hyperflächen $H$ und $H_e$ als Verweise die Schnittebene $S$ als eine enthaltende Hyperflächen hinzu

3.1.2.4 Füge Schnittebene $S$ zu der Liste $LS_{n-2}$ mit noch zu prüfenden Schnittebene hinzu

3.1.2.5 Füge die Schnittebene $S$ zu den Hyperflächen $K$ hinzu

3.1.2.6 Gehe zu 3.1 und prüfe die nächste Hyperfläche $H_e$

4. Füge Schnittebenen der Schnittebenen hinzu: für $d_s={n-2}$ bis $d_s={1}$ ($d_s$ ist die Dimensionalität der geprüften Schnittebenen)

4.1 Nehme und entferne die letzte Schnittebene $S$ von der List $LS_{d_s}$ (mit den noch zu prüfenden Schnittebene der Dimensionalität $d_s$):

4.1.1 Für jede Hyperfläche $HS$ die $S$ enthält:

4.1.1.1 Für jede Hyperfläche $HU$ die in $HS$ enthalten ist ($HU$ hat Dimensionalität $d_s$)

4.1.1.1.1 Berechne Schnittebene $SU$ (hat Dimensionalität $d_s-1$) von $S$ und $HU$

4.1.1.1.1 Fall 1: wenn keine Schnittebene $SU$ existiert -> gehe zu 4.1.1.1 und prüfe die nächste Hyperfläche $HU$

4.1.1.1.1 Sonst: wenn eine Schnittebene $SU$ existiert:

4.1.1.1.1.1 Wenn eine identische Hyperfläche (diese sollte in $HU$ schon enthalten sein) wie die Schnittebene $SU$ in den Hyperflächen $K$ existiert (bzw. es existiert keine neue Schnitthyperfläche)

4.1.1.1.1.1.1 Vermerke zu der gefundenen Schnittebene als Verweise die Hyperfläche $S$ als die enthaltende Hyperfläche

4.1.1.1.1.1.2 Füge zu der Hyperfläche $S$ als Verweis die Schnittebene $SU$ für eine enthaltende Hyperflächen hinzu

4.1.1.1.1.1.3 gehe zu 4.1.1.1 und prüfe die nächste Hyperfläche $HU$

4.1.1.1.1.2 Vermerke zu der Schnittebene $SU$ als Verweise die Hyperflächen $S$ und $HU$ als die enthaltenden Hyperflächen

4.1.1.1.1.3 Füge zu den Hyperflächen $S$ und $HU$ als Verweise die Schnittebene $SU$ für eine enthaltende Hyperflächen hinzu

4.1.1.1.1.4 Füge Schnittebene $SU$ zu der Liste $LS_{d_s-1}$ mit noch zu prüfenden Schnittebene hinzu

4.1.1.1.1.5 Füge die Schnittebene $SU$ zu den Hyperflächen $K$ hinzu

4.1.1.1.1.6 Gehe zu 4.1.1.1 und prüfe die nächste Hyperfläche $HU$

4.2 Wenn $LS_{d_s}$ nicht leer ist, gehe zu 4.1

4.3 Wenn $d_s$ größer $1$ ist ernidrige $d_s$ und gehe zu 4

5. Entferne alle nicht mehr benötigten Eckpunkte:

5.1 Entferne alle Eckpunkte (bzw. Hyperflächen der Dimensionalität 0), inclusive Verweise auf sie, aus $K$ und $E$ die nicht in Richtung des Normalenvektors $N$ der Hyperfläche $H$ von einer Seite von $H$ liegen (bzw. entferne die Eckpunkte, welche die Hyperfläche $H$ aus dem Hyperkörper der möglichen Lösungen $K$ abschneidet)

5.2 Entferne die Überflüssigen Eckpunkte die durch $H$ hinzukamen, nehme und entferne den letzten Eckpunkte $E$ von der List $LS_{0}$ mit noch zu prüfenden Schnittebene der Dimensionalität $0$:

5.2.1 Für jede Hyperfläche bzw. Gerade $G$ die $E$ enthält:

5.2.1.1 Fall 1: Enthält die Gerade $G$ maximal zwei Eckpunkte bzw. Hyperebenen -> gehe zu 5.2.1 und prüfe die nächste Gerade $G$

5.2.1.2 Sonst: Enthält die Gerade $G$ mehr als zwei (bzw. drei) Eckpunkte bzw. Hyperebenen (die Eckpunkte bilden dann keinen konvexen Körper auf $G$ mehr):

5.2.1.2.1 Ermittle den mittleren Punkt $PM$ der drei Schnittpunkte auf $G$ (bzw. enthaltenden Hyperebenen) und die beiden anderen Punkte $P_1$ und $P_2$

5.2.1.2.2 Für jede Hyperfläche $H_e$ mit der Dimensionalität $n-1$ (diese entsprechen den begrenzenden Ungleichungen $U_i$) aus $K$ die den Punkt $PM$ (indirekt) enthält:

5.2.1.2.2.1 Fall 1: beide Punkt $P_1$ und $P_2$ liegen in Richtung des Normalenvektors $N_e$ der Hyperfläche $H_e$ von einer Seite von $H_e$ oder auf $H_e$ (also in der Lösungsmenge) -> gehe zu 5.2.1.2.2 und prüfe die nächste Hyperfläche $H_e$

5.2.1.2.2.2 Sonst: der Punkt $P_r$ liegen nicht in Richtung des Normalenvektors $N_e$ der Hyperfläche $H_e$ von einer Seite von $H_e$ oder auf $H_e$ (also ist er nicht in der Lösungsmenge)

5.2.1.2.2.2.1 Entferne den Punkt $P_r$ aus der Menge der Eckpunkte $E$ (inclusive Verweise auf ihn)

5.2.1.2.2.2.1 Wenn $E$ nicht entfernt wurde ($E \neq P_r$), gehe zu Schritt 5.2.1 und prüfe die nächste Gerade $G$, sonst gehe zu 5.2 und prüfe den nächsten Eckpunkt $E$

6. Entferne alle nicht mehr benötigten Hyperflächen: für $d_h = 1$ bis $d_h = (n-1)$ (Dies sind alle Hyperflächen, die keine Eckpunkte des konvexen Hyperkörper der Lösungen enthalten und damit nicht zu ihm gehören.)

6.1 Entferne alle Hyperflachen, inclusive Verweise zu ihnen, der Dimensionalität $d_h$ die keine Hyperflächen (diese haben Dimensionalität $d_h-1$) mehr enthalten

7. wenn $i < n$: erhöhe Zähler $i$ und gehe zu 1. (sonst 8.)

8. Lösung ermitteln:

8.1. Alternative 1:

8.1.1. Gebe $E$ als Eckpunkte der (konvexen) Lösungsmenge und $i$ als Anzahl der erfüllten Ungleichungen zurück (eine Lösung kann dann aus dem Bereich $E$ ermittelt werden)

8.1. Alternative 2:

8.1.1. Nehme den Mittelpunkt /Schwerpunkt $M$ aller Eckpunkte $E_k$: $M = 1 / \sharp E * \sum_{i=1}^{\sharp E} E_k$

8.1.2. Gebe $M$ als Lösung und $i$ als Anzahl der erfüllten Ungleichungen zurück