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 Wirtschaftsmagazin Capital: Platz 1 für wohngesundes Bauen geht an das Ökohaus-Unternehmen Baufritz
18.06.2018 | Bau-Fritz GmbH & Co. KG, seit 1896

nachricht Muskelaufbau im Computer: Internationales Team will Entstehung von Myofibrillen enträtseln
13.06.2018 | Technische Universität Dresden

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: Temperaturgesteuerte Faser-Lichtquelle mit flüssigem Kern

Die moderne medizinische Bildgebung und neue spektroskopische Verfahren benötigen faserbasierte Lichtquellen, die breitbandiges Laserlicht im nahen und mittleren Infrarotbereich erzeugen. Wissenschaftlerinnen und Wissenschaftler des Leibniz-Instituts für Photonische Technologien Jena (Leibniz-IPHT) zeigen in einer aktuellen Veröffentlichung im renommierten Fachblatt Optica, dass sie die optischen Eigenschaften flüssigkeitsgefüllter Fasern und damit die Bandbreite des Laserlichts gezielt über die Umgebungstemperatur steuern können.

Das Besondere an den untersuchten Fasern ist ihr Kern. Er ist mit Kohlenstoffdisulfid gefüllt - einer flüssigen chemischen Verbindung mit hoher optischer...

Im Focus: Temperature-controlled fiber-optic light source with liquid core

In a recent publication in the renowned journal Optica, scientists of Leibniz-Institute of Photonic Technology (Leibniz IPHT) in Jena showed that they can accurately control the optical properties of liquid-core fiber lasers and therefore their spectral band width by temperature and pressure tuning.

Already last year, the researchers provided experimental proof of a new dynamic of hybrid solitons– temporally and spectrally stationary light waves resulting...

Im Focus: Revolution der Rohre

Forscher*innen des Instituts für Sensor- und Aktortechnik (ISAT) der Hochschule Coburg lassen Rohrleitungen, Schläuchen oder Behältern in Zukunft regelrecht Ohren wachsen. Sie entwickelten ein innovatives akustisches Messverfahren, um Ablagerungen in Rohren frühzeitig zu erkennen.

Rückstände in Abflussleitungen führen meist zu unerfreulichen Folgen. Ein besonderes Gefährdungspotential birgt der Biofilm – eine Schleimschicht, in der...

Im Focus: Überdosis Calcium

Nanokristalle beeinflussen die Differenzierung von Stammzellen während der Knochenbildung

Wissenschaftlerinnen und Wissenschaftler der Universitäten Freiburg und Basel haben einen Hauptschalter für die Regeneration von Knochengewebe identifiziert....

Im Focus: Overdosing on Calcium

Nano crystals impact stem cell fate during bone formation

Scientists from the University of Freiburg and the University of Basel identified a master regulator for bone regeneration. Prasad Shastri, Professor of...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

VideoLinks
Industrie & Wirtschaft
Veranstaltungen

DFG unterstützt Kongresse und Tagungen im August 2018

20.06.2018 | Veranstaltungen

Hengstberger-Symposium zur Sternentstehung

19.06.2018 | Veranstaltungen

LymphomKompetenz KOMPAKT: Neues vom EHA2018

19.06.2018 | Veranstaltungen

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

DFG unterstützt Kongresse und Tagungen im August 2018

20.06.2018 | Veranstaltungsnachrichten

Breitbandservices von DNS:NET erweitert

20.06.2018 | Unternehmensmeldung

Mit Parasiten infizierte Stichlinge beeinflussen Verhalten gesunder Artgenossen

20.06.2018 | Biowissenschaften Chemie

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