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 Klimawandel und Ökosystemfunktionen im Bergregenwald
18.12.2017 | Philipps-Universität Marburg

nachricht Spitzenforschung vom Nanodraht bis zur Supernova: Fünf ERC Consolidator Grants für die TU München
14.12.2017 | Technische Universität München

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: „Carmenes“ findet ersten Planeten

Deutsch-spanisches Forscherteam entwirft, baut und nutzt modernen Spektrografen

Seit Januar 2016 nutzt ein deutsch-spanisches Forscherteam mit Beteiligung der Universität Göttingen den modernen Spektrografen „Carmenes“ für die Suche nach...

Im Focus: Fehlerfrei ins Quantencomputer-Zeitalter

Heute verfügbare Ionenfallen-Technologien eignen sich als Basis für den Bau von großen Quantencomputern. Das zeigen Untersuchungen eines internationalen Forscherteams, deren Ergebnisse nun in der Fachzeitschrift Physical Review X veröffentlicht wurden. Die Wissenschaftler haben für Ionenfallen maßgeschneiderte Protokolle entwickelt, mit denen auftretende Fehler jederzeit entdeckt und korrigiert werden können.

Damit die heute existierenden Prototypen von Quantencomputern ihr volles Potenzial entfalten, müssen sie erstens viel größer werden, d.h. über deutlich mehr...

Im Focus: Error-free into the Quantum Computer Age

A study carried out by an international team of researchers and published in the journal Physical Review X shows that ion-trap technologies available today are suitable for building large-scale quantum computers. The scientists introduce trapped-ion quantum error correction protocols that detect and correct processing errors.

In order to reach their full potential, today’s quantum computer prototypes have to meet specific criteria: First, they have to be made bigger, which means...

Im Focus: Search for planets with Carmenes successful

German and Spanish researchers plan, build and use modern spectrograph

Since 2016, German and Spanish researchers, among them scientists from the University of Göttingen, have been hunting for exoplanets with the “Carmenes”...

Im Focus: Immunsystem - Blutplättchen können mehr als bislang bekannt

LMU-Mediziner zeigen eine wichtige Funktion von Blutplättchen auf: Sie bewegen sich aktiv und interagieren mit Erregern.

Die aktive Rolle von Blutplättchen bei der Immunabwehr wurde bislang unterschätzt: Sie übernehmen mehr Funktionen als bekannt war. Das zeigt eine Studie von...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

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

Neue Konfenzreihe in Berlin: Landscape 2018 - Ernährungssicherheit, Klimawandel, Nachhaltigkeit

18.12.2017 | Veranstaltungen

Call for Contributions: Tagung „Lehren und Lernen mit digitalen Medien“

15.12.2017 | Veranstaltungen

Die Stadt der Zukunft nachhaltig(er) gestalten: inter 3 stellt Projekte auf Konferenz vor

15.12.2017 | Veranstaltungen

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

Neue Konfenzreihe in Berlin: Landscape 2018 - Ernährungssicherheit, Klimawandel, Nachhaltigkeit

18.12.2017 | Veranstaltungsnachrichten

„Carmenes“ findet ersten Planeten

18.12.2017 | Physik Astronomie

Fehlerfrei ins Quantencomputer-Zeitalter

18.12.2017 | Physik Astronomie