Forum für Wissenschaft, Industrie und Wirtschaft

Hauptsponsoren:     3M 
Datenbankrecherche:

 

Wie der Zufall hilft, Probleme zu lösen

31.03.2010
Raimund Seidel, Professor für Theoretische Informatik an der Universität des Saarlandes und Sprecher der Graduiertenschule für Informatik, ist mit dem "test-of-time-award" der Zeitschrift "Computational Geometry: Theory and Applications" ausgezeichnet worden.

Dieser Preis wird für den Forschungsbeitrag vergeben, der seit seinem Erscheinen vor mindestens zehn Jahren den größten Einfluss auf das ganze Forschungsgebiet hatte. Einen Preis für Nachwuchswissenschaftler erhielt Seidels Doktorand Saurabh Ray.

Raimund Seidel hat 1991 in einem Beitrag eine neue Methode zur automatischen Unterteilung von Polygonen in Dreiecke vorgestellt - und zwar mithilfe eines randomisierten Algorithmus. Polygone sind beliebige Flächen, die durch Teilstücke von Geraden begrenzt sind; sie werden in der geometrischen Modellierung an vielen Stellen eingesetzt und dazu in einfach zu handhabende Dreiecke unterteilt.

Die von Seidel beschriebene neue Methode zur Polygontriangulierung ist einfacher und schneller als die davor bekannten Methoden und hat Eingang in die Lehrbücher der algorithmischen Geometrie und in die Praxis gefunden.

Bei der prämierten Methode ist Randomisierung, also der Einsatz von Zufall, wesentlich. Dabei arbeitet der Algorithmus die Seiten des zu unterteilenden Polygons in einer zufälligen Reihenfolge nacheinander ab. Da bei den meisten Reihenfolgen nur eine sehr kurze Rechenzeit benötigt wird, ist die Methode für eine zufällig gewählte Reihenfolge mit großer Wahrscheinlichkeit schnell.

Dass kontrollierte Zufallsverwendung bei vielen Probleme zu guten Ergebnissen führen kann, erläutert Raimund Seidel an einem einfachen Beispiel: "Wenn mehrere Tausend Menschen einen Fluss überqueren wollen und dafür nur zwei Brücken zur Verfügung stehen, hilft die randomisierte Methode dabei, beide Brücken ähnlich auszulasten. Dazu muss jeder, der den Fluss überqueren will, eine Münze werfen; bei Kopf nutzt er Brücke A, bei Zahl Brücke B. Auf diese Weise erzeugt jeder seinen eigenen Zufall - und es funktioniert: Die Brücken werden ähnlich ausgelastet, ohne dass es zu irgendeinem zentralen Koordinationsaufwand gekommen ist."

Mit einem zweiten Preis, dem "young-researcher award", hat die Fachzeitschrift zwei Nachwuchswissenschaftler für die beste Veröffentlichung des Vorjahres ausgezeichnet. Den Preis erhielten Saurabh Ray, der bis März 2009 Doktorand von Professor Raimund Seidel war, und sein Mitautor Nabil H. Mustafa für ihre Arbeit im Bereich kombinatorische Geometrie.

Ausgezeichnete Veröffentlichungen:
Raimund Seidel: A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons. Comput. Geom. 1: 51-64 (1991).

Nabil H. Mustafa, Saurabh Ray: Weak epsilon-nets have basis of size O(1/epsilon log(1/epsilon)) in any dimension. Comput. Geom. 40(1): 84-91 (2008).

Für weitere Informationen wenden Sie sich bitte an:
Professor Raimund Seidel
Tel. (0681) 302 - 4513,
E-Mail: rseidel@cs.uni-saarland.de

Gerhild Sieber | idw
Weitere Informationen:
http://www.uni-saarland.de

Weitere Berichte zu: Algorithmus Geom Geometrie Nachwuchswissenschaft polygons

Weitere Nachrichten aus der Kategorie Förderungen Preise:

nachricht Gewebe mit Hilfe von Stammzellen regenerieren
16.10.2017 | Albert-Ludwigs-Universität Freiburg im Breisgau

nachricht Dr. Philipp Schommers erhält Förderpreis für Klinische Infektionsforschung
16.10.2017 | Uniklinik Köln

Alle Nachrichten aus der Kategorie: Förderungen Preise >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Smarte Sensoren für effiziente Prozesse

Materialfehler im Endprodukt können in vielen Industriebereichen zu frühzeitigem Versagen führen und den sicheren Gebrauch der Erzeugnisse massiv beeinträchtigen. Eine Schlüsselrolle im Rahmen der Qualitätssicherung kommt daher intelligenten, zerstörungsfreien Sensorsystemen zu, die es erlauben, Bauteile schnell und kostengünstig zu prüfen, ohne das Material selbst zu beschädigen oder die Oberfläche zu verändern. Experten des Fraunhofer IZFP in Saarbrücken präsentieren vom 7. bis 10. November 2017 auf der Blechexpo in Stuttgart zwei Exponate, die eine schnelle, zuverlässige und automatisierte Materialcharakterisierung und Fehlerbestimmung ermöglichen (Halle 5, Stand 5306).

Bei Verwendung zeitaufwändiger zerstörender Prüfverfahren zieht die Qualitätsprüfung durch die Beschädigung oder Zerstörung der Produkte enorme Kosten nach...

Im Focus: Smart sensors for efficient processes

Material defects in end products can quickly result in failures in many areas of industry, and have a massive impact on the safe use of their products. This is why, in the field of quality assurance, intelligent, nondestructive sensor systems play a key role. They allow testing components and parts in a rapid and cost-efficient manner without destroying the actual product or changing its surface. Experts from the Fraunhofer IZFP in Saarbrücken will be presenting two exhibits at the Blechexpo in Stuttgart from 7–10 November 2017 that allow fast, reliable, and automated characterization of materials and detection of defects (Hall 5, Booth 5306).

When quality testing uses time-consuming destructive test methods, it can result in enormous costs due to damaging or destroying the products. And given that...

Im Focus: Cold molecules on collision course

Using a new cooling technique MPQ scientists succeed at observing collisions in a dense beam of cold and slow dipolar molecules.

How do chemical reactions proceed at extremely low temperatures? The answer requires the investigation of molecular samples that are cold, dense, and slow at...

Im Focus: Kalte Moleküle auf Kollisionskurs

Mit einer neuen Kühlmethode gelingt Wissenschaftlern am MPQ die Beobachtung von Stößen in einem dichten Strahl aus kalten und langsamen dipolaren Molekülen.

Wie verlaufen chemische Reaktionen bei extrem tiefen Temperaturen? Um diese Frage zu beantworten, benötigt man molekulare Proben, die gleichzeitig kalt, dicht...

Im Focus: Astronomen entdecken ungewöhnliche spindelförmige Galaxien

Galaxien als majestätische, rotierende Sternscheiben? Nicht bei den spindelförmigen Galaxien, die von Athanasia Tsatsi (Max-Planck-Institut für Astronomie) und ihren Kollegen untersucht wurden. Mit Hilfe der CALIFA-Umfrage fanden die Astronomen heraus, dass diese schlanken Galaxien, die sich um ihre Längsachse drehen, weitaus häufiger sind als bisher angenommen. Mit den neuen Daten konnten die Astronomen außerdem ein Modell dafür entwickeln, wie die spindelförmigen Galaxien aus einer speziellen Art von Verschmelzung zweier Spiralgalaxien entstehen. Die Ergebnisse wurden in der Zeitschrift Astronomy & Astrophysics veröffentlicht.

Wenn die meisten Menschen an Galaxien denken, dürften sie an majestätische Spiralgalaxien wie die unserer Heimatgalaxie denken, der Milchstraße: Milliarden von...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

IHR
JOB & KARRIERE
SERVICE
im innovations-report
in Kooperation mit academics
Veranstaltungen

Meeresbiologe Mark E. Hay zu Gast bei den "Noblen Gesprächen" am Beutenberg Campus in Jena

16.10.2017 | Veranstaltungen

bionection 2017 erstmals in Thüringen: Biotech-Spitzenforschung trifft in Jena auf Weltmarktführer

13.10.2017 | Veranstaltungen

Tagung „Energieeffiziente Abluftreinigung“ zeigt, wie man durch Luftreinhaltemaßnahmen profitieren kann

13.10.2017 | Veranstaltungen

 
VideoLinks
B2B-VideoLinks
Weitere VideoLinks >>>
Aktuelle Beiträge

ESO-Teleskope beobachten erstes Licht einer Gravitationswellen-Quelle

16.10.2017 | Physik Astronomie

Was läuft schief beim Noonan-Syndrom? – Grundlagen der neuronalen Fehlfunktion entdeckt

16.10.2017 | Biowissenschaften Chemie

Gewebe mit Hilfe von Stammzellen regenerieren

16.10.2017 | Förderungen Preise