Campus Event Calendar
Event Entry
New for: D3
What and Who
Praxisorientierte Theorie -- ein Fallbeispiel aus dem CAD
Prof. Dr. Karsten Weihe
Forschungsinstitut für Diskrete Mathematik Bonn
Informatik-Kolloquium
AG 1, AG 2, AG 3, AG 4
Expert Audience
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 11 December 2000
16:00
-- Not specified --
45 - FR 6.1
HS 001
Saarbrücken
Abstract
Forschungsinstitut für Diskrete Mathematik Bonn
Wir betrachten CAD-Netze, die Hohlkoerper oder Oberflaechen von Festkoerpern approximieren und aus raeumlich
gebogenen Polygonen (Freiformflaechen) bestehen. Ein solches Netz soll automatisch in ein engeres, konformes
Vierecksnetz verfeinert werden, so dass gewisse Bedingungen erfuellt werden. Dieses Problem konnte in verschiedenen
Variationen als stark NP-schwer klassifiziert werden.
Der Vortrag wird auf zwei konstruktive Resultate eingehen:
1.Die verschiedensten Varianten des Problem lassen sich uniform als ein diskretes Netzwerkflussproblem
modellieren. Dieser Ansatz erlaubt es, reale Daten effizient zu bearbeiten und dabei diverse Kriterien und
Zusatzaspekte flexibel zu beruecksichtigen.
Das Problem, die Anzahl der Vierecke im Ergebnis zu minimieren, ist von praktischer Bedeutung, aber mangels
geeigneter theoretischer Ansaetze in der Literatur noch nicht betrachtet worden. Auch die Reduktion des
Problems auf diesen einzelnen Aspekt ist immer noch stark NP-schwer. Vorgestellt wird ein neuer Ansatz, der es
erlaubt, die minimale Anzahl bis auf einen kleinen konstanten Faktor zu approximieren.
Wir betrachten CAD-Netze, die Hohlkoerper oder Oberflaechen von Festkoerpern approximieren und aus raeumlich
gebogenen Polygonen (Freiformflaechen) bestehen. Ein solches Netz soll automatisch in ein engeres, konformes
Vierecksnetz verfeinert werden, so dass gewisse Bedingungen erfuellt werden. Dieses Problem konnte in verschiedenen
Variationen als stark NP-schwer klassifiziert werden.
Der Vortrag wird auf zwei konstruktive Resultate eingehen:
1.Die verschiedensten Varianten des Problem lassen sich uniform als ein diskretes Netzwerkflussproblem
modellieren. Dieser Ansatz erlaubt es, reale Daten effizient zu bearbeiten und dabei diverse Kriterien und
Zusatzaspekte flexibel zu beruecksichtigen.
Das Problem, die Anzahl der Vierecke im Ergebnis zu minimieren, ist von praktischer Bedeutung, aber mangels
geeigneter theoretischer Ansaetze in der Literatur noch nicht betrachtet worden. Auch die Reduktion des
Problems auf diesen einzelnen Aspekt ist immer noch stark NP-schwer. Vorgestellt wird ein neuer Ansatz, der es
erlaubt, die minimale Anzahl bis auf einen kleinen konstanten Faktor zu approximieren.
Contact
Christian Schulte
--email hidden
passcode not visible
logged in users only