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 Intelligente Werkstoffe erforschen
18.11.2019 | Carl-Zeiss-Stiftung

nachricht dormakaba mit 4 Architects' Darling in Gold ausgezeichnet
13.11.2019 | dormakaba Deutschland GmbH

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: Neu entwickeltes Glas ist biegsam

Eine internationale Forschungsgruppe mit Beteiligung der Österreichischen Akademie der Wissenschaften hat ein Glasmaterial entwickelt, das sich bei Raumtemperatur bruchfrei verformen lässt. Das berichtet das Team aktuell in "Science". Das extrem harte und zugleich leichte Material verspricht ein großes Anwendungspotential – von Smartphone-Displays bis hin zum Maschinenbau.

Gläser sind ein wesentlicher Bestandteil der modernen Welt. Dabei handelt es sich im Alltag meist um sauerstoffhaltige Gläser, wie sie etwa für Fenster und...

Im Focus: Images from NJIT's big bear solar observatory peel away layers of a stellar mystery

An international team of scientists, including three researchers from New Jersey Institute of Technology (NJIT), has shed new light on one of the central mysteries of solar physics: how energy from the Sun is transferred to the star's upper atmosphere, heating it to 1 million degrees Fahrenheit and higher in some regions, temperatures that are vastly hotter than the Sun's surface.

With new images from NJIT's Big Bear Solar Observatory (BBSO), the researchers have revealed in groundbreaking, granular detail what appears to be a likely...

Im Focus: Veränderungen der Chiralität von Molekülen in Echtzeit beobachten

Chirale Moleküle – Verbindungen, die als Bild und Spiegelbild vorkommen – spielen eine wichtige Rolle in biologischen Prozessen und in der chemischen Synthese. Chemikern der ETH Zürich ist es nun erstmals gelungen, mit Hilfe von Ultrakurzzeit-Laserpulsen Änderungen der Chiralität während einer chemischen Reaktion in Echtzeit zu beobachten.

Manche Moleküle können in zwei spiegelbildlichen Formen existieren, ähnlich wie unsere Hände. Obwohl solche sogenannten Enantiomere fast identische...

Im Focus: Durchbruch in der Malariaforschung

Eine internationale Forschungsgruppe um den Zellbiologen Volker Heussler von der Universität Bern hat hunderte genetische Schwachstellen des Malaria-Parasiten Plasmodium identifiziert. Diese sind in der Medikamenten- und Impfstoffentwicklung dringend erforderlich, um die Krankheit dereinst ausrotten zu können.

Trotz grosser Anstrengungen in Medizin und Wissenschaft, sterben weltweit immer noch mehr als 400'000 Menschen an Malaria. Die Infektionskrankheit wird durch...

Im Focus: Bauplan eines bakteriellen Kraftwerks entschlüsselt

Wissenschaftler der Universität Würzburg und der Universität Freiburg gelang es die komplexe molekulare Struktur des bakteriellen Enzyms Cytochrom-bd-Oxidase zu entschlüsseln. Da Menschen diesen Typ der Oxidase nicht besitzen, könnte dieses Enzym ein interessantes Ziel für neuartige Antibiotika sein.

Sowohl Menschen als auch viele andere Lebewesen brauchen Sauerstoff zum Überleben. Bei der Umsetzung von Nährstoffen in Energie wird der Sauerstoff zu Wasser...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

VideoLinks
Industrie & Wirtschaft
Veranstaltungen

Chemnitzer Linux-Tage 2020: „Mach es einfach!“

18.11.2019 | Veranstaltungen

Humanoide Roboter in Aktion erleben

18.11.2019 | Veranstaltungen

1. Internationale Konferenz zu Agrophotovoltaik im August 2020

15.11.2019 | Veranstaltungen

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

Antibiotika aus dem Meer

18.11.2019 | Biowissenschaften Chemie

Lebende Brücken: Mit alten indischen Bautechniken moderne Städte klimafreundlich gestalten

18.11.2019 | Architektur Bauwesen

„Moonwalk“ für die Wissenschaft zeigt Verzerrungen im räumlichen Gedächtnis

18.11.2019 | Studien Analysen

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