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 Über zwei Millionen für bessere Bordnetze
28.04.2017 | Friedrich-Alexander-Universität Erlangen-Nürnberg

nachricht Innovationspreis 2017 der Deutschen Hochschulmedizin e.V.
24.04.2017 | Deutsche Hochschulmedizin e.V.

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: TU Chemnitz präsentiert weltweit einzigartige Pilotanlage für nachhaltigen Leichtbau

Wickelprinzip umgekehrt: Orbitalwickeltechnologie soll neue Maßstäbe in der großserientauglichen Fertigung komplexer Strukturbauteile setzen

Mitarbeiterinnen und Mitarbeiter des Bundesexzellenzclusters „Technologiefusion für multifunktionale Leichtbaustrukturen" (MERGE) und des Instituts für...

Im Focus: Smart Wireless Solutions: EU-Großprojekt „DEWI“ liefert Innovationen für eine drahtlose Zukunft

58 europäische Industrie- und Forschungspartner aus 11 Ländern forschten unter der Leitung des VIRTUAL VEHICLE drei Jahre lang, um Europas führende Position im Bereich Embedded Systems und dem Internet of Things zu stärken. Die Ergebnisse von DEWI (Dependable Embedded Wireless Infrastructure) wurden heute in Graz präsentiert. Zu sehen war eine Fülle verschiedenster Anwendungen drahtloser Sensornetzwerke und drahtloser Kommunikation – von einer Forschungsrakete über Demonstratoren zur Gebäude-, Fahrzeug- oder Eisenbahntechnik bis hin zu einem voll vernetzten LKW.

Was vor wenigen Jahren noch nach Science-Fiction geklungen hätte, ist in seinem Ansatz bereits Wirklichkeit und wird in Zukunft selbstverständlicher Teil...

Im Focus: Weltweit einzigartiger Windkanal im Leipziger Wolkenlabor hat Betrieb aufgenommen

Am Leibniz-Institut für Troposphärenforschung (TROPOS) ist am Dienstag eine weltweit einzigartige Anlage in Betrieb genommen worden, mit der die Einflüsse von Turbulenzen auf Wolkenprozesse unter präzise einstellbaren Versuchsbedingungen untersucht werden können. Der neue Windkanal ist Teil des Leipziger Wolkenlabors, in dem seit 2006 verschiedenste Wolkenprozesse simuliert werden. Unter Laborbedingungen wurden z.B. das Entstehen und Gefrieren von Wolken nachgestellt. Wie stark Luftverwirbelungen diese Prozesse beeinflussen, konnte bisher noch nicht untersucht werden. Deshalb entstand in den letzten Jahren eine ergänzende Anlage für rund eine Million Euro.

Die von dieser Anlage zu erwarteten neuen Erkenntnisse sind wichtig für das Verständnis von Wetter und Klima, wie etwa die Bildung von Niederschlag und die...

Im Focus: Nanoskopie auf dem Chip: Mikroskopie in HD-Qualität

Neue Erfindung der Universitäten Bielefeld und Tromsø (Norwegen)

Physiker der Universität Bielefeld und der norwegischen Universität Tromsø haben einen Chip entwickelt, der super-auflösende Lichtmikroskopie, auch...

Im Focus: Löschbare Tinte für den 3-D-Druck

Im 3-D-Druckverfahren durch Direktes Laserschreiben können Mikrometer-große Strukturen mit genau definierten Eigenschaften geschrieben werden. Forscher des Karlsruher Institus für Technologie (KIT) haben ein Verfahren entwickelt, durch das sich die 3-D-Tinte für die Drucker wieder ‚wegwischen‘ lässt. Die bis zu hundert Nanometer kleinen Strukturen lassen sich dadurch wiederholt auflösen und neu schreiben - ein Nanometer entspricht einem millionstel Millimeter. Die Entwicklung eröffnet der 3-D-Fertigungstechnik vielfältige neue Anwendungen, zum Beispiel in der Biologie oder Materialentwicklung.

Beim Direkten Laserschreiben erzeugt ein computergesteuerter, fokussierter Laserstrahl in einem Fotolack wie ein Stift die Struktur. „Eine Tinte zu entwickeln,...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

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

Internationaler Tag der Immunologie - 29. April 2017

28.04.2017 | Veranstaltungen

Kampf gegen multiresistente Tuberkulose – InfectoGnostics trifft MYCO-NET²-Partner in Peru

28.04.2017 | Veranstaltungen

123. Internistenkongress: Traumata, Sprachbarrieren, Infektionen und Bürokratie – Herausforderungen

27.04.2017 | Veranstaltungen

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

Über zwei Millionen für bessere Bordnetze

28.04.2017 | Förderungen Preise

Symbiose-Bakterien: Vom blinden Passagier zum Leibwächter des Wollkäfers

28.04.2017 | Biowissenschaften Chemie

Wie Pflanzen ihre Zucker leitenden Gewebe bilden

28.04.2017 | Biowissenschaften Chemie