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 Preis für Arbeit über autonomes Fahren
11.09.2018 | Julius-Maximilians-Universität Würzburg

nachricht Mit der Getränkedose hoch hinaus – Minisatellitenwettbewerb vom 17. bis 21. September in Bremen
10.09.2018 | Zentrum für angewandte Raumfahrttechnologie und Mikrogravitation (ZARM)

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: Der Truck der Zukunft

Lastkraftwagen (Lkw) sind für den Gütertransport auch in den kommenden Jahrzehnten unverzichtbar. Wissenschaftler und Wissenschaftlerinnen der Technischen Universität München (TUM) und ihre Partner haben ein Konzept für den Truck der Zukunft erarbeitet. Dazu zählen die europaweite Zulassung für Lang-Lkw, der Diesel-Hybrid-Antrieb und eine multifunktionale Fahrerkabine.

Laut der Prognose des Bundesministeriums für Verkehr und digitale Infrastruktur wird der Lkw-Güterverkehr bis 2030 im Vergleich zu 2010 um 39 Prozent steigen....

Im Focus: Extrem klein und schnell: Laser zündet heißes Plasma

Feuert man Lichtpulse aus einer extrem starken Laseranlage auf Materialproben, reißt das elektrische Feld des Lichts die Elektronen von den Atomkernen ab. Für Sekundenbruchteile entsteht ein Plasma. Dabei koppeln die Elektronen mit dem Laserlicht und erreichen beinahe Lichtgeschwindigkeit. Beim Herausfliegen aus der Materialprobe ziehen sie die Atomrümpfe (Ionen) hinter sich her. Um diesen komplexen Beschleunigungsprozess experimentell untersuchen zu können, haben Forscher aus dem Helmholtz-Zentrum Dresden-Rossendorf (HZDR) eine neuartige Diagnostik für innovative laserbasierte Teilchenbeschleuniger entwickelt. Ihre Ergebnisse erscheinen jetzt in der Fachzeitschrift „Physical Review X“.

„Unser Ziel ist ein ultrakompakter Beschleuniger für die Ionentherapie, also die Krebsbestrahlung mit geladenen Teilchen“, so der Physiker Dr. Thomas Kluge vom...

Im Focus: Bio-Kunststoffe nach Maß

Zusammenarbeit zwischen Chemikern aus Konstanz und Pennsylvania (USA) – gefördert im Programm „Internationale Spitzenforschung“ der Baden-Württemberg-Stiftung

Chemie kann manchmal eine Frage der richtigen Größe sein. Ein Beispiel hierfür sind Bio-Kunststoffe und die pflanzlichen Fettsäuren, aus denen sie hergestellt...

Im Focus: Patented nanostructure for solar cells: Rough optics, smooth surface

Thin-film solar cells made of crystalline silicon are inexpensive and achieve efficiencies of a good 14 percent. However, they could do even better if their shiny surfaces reflected less light. A team led by Prof. Christiane Becker from the Helmholtz-Zentrum Berlin (HZB) has now patented a sophisticated new solution to this problem.

"It is not enough simply to bring more light into the cell," says Christiane Becker. Such surface structures can even ultimately reduce the efficiency by...

Im Focus: Mit Nano-Lenkraketen Keime töten

Wo Antibiotika versagen, könnten künftig Nano-Lenkraketen helfen, multiresistente Erreger (MRE) zu bekämpfen: Dieser Idee gehen derzeit Wissenschaftler der Universität Duisburg-Essen (UDE) und der Medizinischen Hochschule Hannover nach. Zusammen mit einem führenden US-Experten tüfteln sie an millionstel Millimeter kleinen Lenkraketen, die antimikrobielles Silber zielsicher transportieren, um MRE vor Ort zur Strecke zu bringen.

In deutschen Krankenhäusern führen die MRE jährlich zu tausenden, teils lebensgefährlichen Komplikationen. Denn wer sich zum Beispiel nach einer Implantation...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

VideoLinks
Industrie & Wirtschaft
Veranstaltungen

Internationale Experten der Orthopädietechnik tagen in Göttingen

19.09.2018 | Veranstaltungen

Von den Grundlagen bis zur Anwendung - Internationale Elektrochemie-Tagung in Ulm

18.09.2018 | Veranstaltungen

Unbemannte Flugsysteme für die Klimaforschung

18.09.2018 | Veranstaltungen

VideoLinks
Wissenschaft & Forschung
Weitere VideoLinks im Überblick >>>
 
Aktuelle Beiträge

Internationale Experten der Orthopädietechnik tagen in Göttingen

19.09.2018 | Veranstaltungsnachrichten

Der Truck der Zukunft

19.09.2018 | Verkehr Logistik

Fehlersuche in der Quantenwelt

19.09.2018 | Physik Astronomie

Weitere B2B-VideoLinks
IHR
JOB & KARRIERE
SERVICE
im innovations-report
in Kooperation mit academics