Triangulation

[richy]

An die Informatiker der Runde.

Fuer die Delaunay Triangulation hab ich vor Jahren ein neues Kriterium hergeleitet, das effizienter ist als das traditionelle Kriterium von Lawson.
Aus dem einfachen Grund weil ich zu bloed war die Teile und Herrsche Methode auf Lawson praktisch anzuwenden.
Und ohne "Teile und Herrsche" haette die Firma fuer die ich das Programm schrieb ewig auf die Triangulationsergebnisse warten muessen.
Ich habe damals daher ein neues efffizienteres Triangulationskriterium hergeleitet.
Es wuerde mich interessieren ob das von mir entwickelte Kriterium nun widerum mittels der Teile und Herrsche Methode effizienter waere als das von Lawson. Mit Sicherheit ist es um den Faktor N effizienter.
Gibt es hier einen Informatiker, der mit der Anwendung von "Teile und Herrsche" auch im 2 D Fall im Schlaf umgehen kann ?
Mein (etwas komplexeres) Kriterium findet sich hier :
http://home.arcor.de/richardon/richy2001/mathe/delauny/index.htm
speziell :
http://home.arcor.de/richardon/richy2001/mathe/delauny/s74.gif
http://home.arcor.de/richardon/richy2001/mathe/delauny/s75.gif
http://home.arcor.de/richardon/richy2001/mathe/delauny/s76.gif
http://home.arcor.de/richardon/richy2001/mathe/delauny/s77.gif
Schrittdiagramm siehe Hauptseite

Lawson testet alle moeglichen Dreiecke einer Punktmenge anhand eines 4 ten Punktes.
Mein Kriterium verwendet alle moeglichen Verbindungen einer Punktemenge anhand eines 3 ten Punktes.
Besteht die Punktmenge aus 1000 Punkten ist meine Programmversion z.B 1000 mal schneller als die Lawson Version..
Deshalb funktioniert das Programm, das man auf meiner Seite downloaden kann auch uebrhaupt nur in akzeptabler Zeit, obwohl es nicht effizient implementiert ist.

http://home.arcor.de/richardon/richy2001/mathe/delauny/s80.gif
Eine Punktmenge mit 2000 Zufallspunkten werde ich demnaechst vom Dos Screen abphotographieren.
Mein Algo berechnet die Triagulation einer Menge vom 2000 Punkten in etwa 3 Minuten.