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 Autonomes Fahren mit Blockchain: Bayreuther Studierende siegen im internationalen MOBI-Wettbewerb
18.02.2019 | Universität Bayreuth

nachricht 350.000 Euro für Forschung zu Genom-Editierung
11.02.2019 | Universität Mannheim

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: Wasser ist homogener als gedacht

Um die bekannten Anomalien in Wasser zu erklären, gehen manche Forscher davon aus, dass Wasser auch bei Umgebungsbedingungen aus einer Mischung von zwei Phasen besteht. Neue röntgenspektroskopische Analysen an BESSY II, der ESRF und der Swiss Light Source zeigen jedoch, dass dies nicht der Fall ist. Bei Raumtemperatur und normalem Druck bilden die Wassermoleküle ein fluktuierendes Netz mit durchschnittlich je 1,74 ± 2.1% Donator- und Akzeptor-Wasserstoffbrückenbindungen pro Molekül, die eine tetrahedrische Koordination zwischen nächsten Nachbarn ermöglichen.

Wasser ist das „Element“ des Lebens, die meisten biologischen Prozesse sind auf Wasser angewiesen. Dennoch gibt Wasser noch immer Rätsel auf. So dehnt es sich...

Im Focus: Licht von der Rolle – hybride OLED ermöglicht innovative funktionale Lichtoberflächen

Bislang wurden OLEDS ausschließlich als neue Beleuchtungstechnologie für den Einsatz in Leuchten und Lampen verwendet. Dabei bietet die organische Technologie viel mehr: Als Lichtoberfläche, die sich mit den unterschiedlichsten Materialien kombinieren lässt, kann sie Funktionalität und Design unzähliger Produkte verändern und revolutionieren. Beispielhaft für die vielen Anwendungsmöglichkeiten präsentiert das Fraunhofer FEP gemeinsam mit der EMDE development of light GmbH im Rahmen des EU-Projektes PI-SCALE auf der Münchner LOPEC (19. bis 21. März 2019), erstmals in Textildesign integrierte hybride OLEDs.

Als Anbieter von Forschungs- und Entwicklungsdienstleistungen auf dem Gebiet der organischen Elektronik setzt sich das Fraunhofer FEP schon lange mit der...

Im Focus: Light from a roll – hybrid OLED creates innovative and functional luminous surfaces

Up to now, OLEDs have been used exclusively as a novel lighting technology for use in luminaires and lamps. However, flexible organic technology can offer much more: as an active lighting surface, it can be combined with a wide variety of materials, not just to modify but to revolutionize the functionality and design of countless existing products. To exemplify this, the Fraunhofer FEP together with the company EMDE development of light GmbH will be presenting hybrid flexible OLEDs integrated into textile designs within the EU-funded project PI-SCALE for the first time at LOPEC (March 19-21, 2019 in Munich, Germany) as examples of some of the many possible applications.

The Fraunhofer FEP, a provider of research and development services in the field of organic electronics, has long been involved in the development of...

Im Focus: Laserverfahren für funktionsintegrierte Composites

Composites vereinen gewinnbringend die Vorteile artungleicher Materialien – und schöpfen damit zum Beispiel Potentiale im Leichtbau aus. Auf der JEC World 2019 im März in Paris präsentieren die Wissenschaftler des Fraunhofer-Instituts für Lasertechnik ILT ein breites Spektrum an laserbasierten Technologien für die effiziente Herstellung und Bearbeitung von Verbundmaterialien. Einblicke zu Füge- und Trennverfahren sowie zur Oberflächenstrukturierung erhalten Besucher auf dem Gemeinschaftsstand des Aachener Zentrums für integrativen Leichtbau AZL, Halle 5A/D17.

Experten des Fraunhofer ILT erforschen und entwickeln Laserprozesse für das wirtschaftliche Fügen, Schneiden, Abtragen oder Bohren von Verbundmaterialien –...

Im Focus: Grüne Spintronik: Mit Spannung Superferromagnetismus erzeugen

Ein HZB-Team hat zusammen mit internationalen Partnern an der Lichtquelle BESSY II ein neues Phänomen in Eisen-Nanokörnern auf einem ferroelektrischen Substrat beobachtet: Die magnetischen Momente der Eisenkörner richten sich superferromagnetisch aus, sobald eine elektrische Spannung anliegt. Der Effekt funktioniert bei Raumtemperatur und könnte zu neuen Materialien für IT-Bauelemente und Datenspeicher führen, die weniger Energie verbrauchen.

In heutigen Datenspeichern müssen magnetische Domänen mit Hilfe eines externen Magnetfeld umgeschaltet werden, welches durch elektrischen Strom erzeugt wird....

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

VideoLinks
Industrie & Wirtschaft
Veranstaltungen

Tagung rund um zuverlässige Verbindungen

20.02.2019 | Veranstaltungen

LastMileLogistics Conference in Frankfurt befasst sich mit Lieferkonzepten für Ballungsräume

19.02.2019 | Veranstaltungen

Bildung digital und multikulturell: Große Fachtagung GEBF findet an der Uni Köln statt

18.02.2019 | Veranstaltungen

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

Eine vulkanische Riesenparty und ihr frostiger Kater danach

20.02.2019 | Geowissenschaften

Lückenlose Weltkarte der Baumarten-Vielfalt: neues statistisches Modell füllt weiße Flächen

20.02.2019 | Biowissenschaften Chemie

Jacobs University Forscher entdecken neue Klasse von heterogenen Katalysatoren auf Edelmetallbasis

20.02.2019 | Biowissenschaften Chemie

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