Distance Computation for Extended Quadratic Complexes

Euklidischen Abstands nicht-deformierbarer Objekte vor, deren
Oberflächen sich aus gekrümmten Flächenstücken zusammensetzen.
Jedes Flächenstück ist eingebettet auf einer algebraischen Oberfläche
der Ordnung höchstens zwei oder auf einem Torus.
Als Begrenzungskanten erlauben wir Geraden- oder Kegelschnittsegmente.
Objekte, die dieser Randdarstellung genügen, heißen quadratische Komplexe.
Wir führen das Abstandsberechnungsproblem auf drei Typen von Basisanfragen zurück, die auf den Objekträndern operieren.
Dabei handelt es sich um Enthaltenseins-, Schnitt und Abstandstests.
Wir zeigen, dass alle Anfragen durch Lösen von univariaten oder bivariaten Gleichungssystemen beantwortet werden können.
Die vorgestellten Algorithmen bestimmen ein Paar nahester Punkte für jede Konfiguration der Eingabeobjekte, und zwar selbst in degenerierten Fällen.
Eliminationsmethoden erlauben es, die Lösungsmenge der auftretenden Gleichungssysteme durch Nullstellensuche univariater Polynome
zu bestimmen.
Für dieses Problem sind effiziente und robuste Algorithmen bekannt.
Da deren Laufzeitverhalten und numerische Stabilität sehr stark von den Graden der betrachteten Polynome abhängen, halten wir diese so gering wie möglich.
So zeigen wir, dass das Abstandsproblem zweier quadratischer
Komplexe in allen nicht-degenerierten Fällen auf die Bestimmung der
Nullstellen univariater Polynome vom Grad höchstens 24 zurückgeführt werden kann.
Für Objekte einer wichtigen Unterklasse beweisen wir eine Gradschranke
von 8, die zudem in allen degenerierten Fällen gilt.