TUM – TUM – Menü

 

 
Computational Convexity - Optimale Containment Probleme

Vorlesung

 

Dozent: Dr. René Brandenberg
Übungsleitung: Dr. René Brandenberg

Aktuelles Termine Was ist Computational Convexity? Was bedeutet Optimales Containment? An wen richtet sich die Vorlesung? Anrechenbarkeit Übungsblätter

Aktuelles

  • 6. März 2009: Vorlesungsskipt: jetzt vollständig.
  • 14. Feb. 2008: Vorlesungsskipt: zunächst Kapitel 1-5. Der Rest folgt demnächst.
  • 11. Dez. 2008: Der Beweis der %$\mathbb{NP}$%-Vollständigkeit von %$\sc{Parmax}[-1,1]_p$% aus der Vorlesung vor 3 Jahren Normmaximierung über Parallelotopen
  • 9. Nov. 2008: %$l_s(K)$% wird es in der nächsten Vorlesung definiert. Diesen Teil von Aufgabe 2.5 bitte auslassen.
  • 31. Okt. 2008: Eine kurze Übersicht zu komplexitätstheoretischen Grundlagen aus der Vorlesung vor 3 Jahren: Komplexitätstheorie
  • 23. Okt. 2008: Die Übungen fangen ab der dritten Woche um 16.00 Uhr an.
  • 29. Sept. 2008: Wir fangen in der ersten Semesterwoche, Donnerstag 16. Oktober, mit zwei Vorlesungen (12-14 Uhr und 16-18 Uhr) an.

Termine

  Tag Uhrzeit Raum Hinweise  
Vorlesung Do 12:30 - 14:00 MI 02.08.011   %SBBANNER%
Übung Do 16:00 - 17:30 MI 02.04.011 zweiwöchig %SBBANNER%

Was ist Computational Convexity?

Obwohl auch als Teil der Algorithmischen Geometrie aufgefasst, stammen ihre Ideen und Techniken eher aus Gebieten wie der Linearen Programmierung, der Polyedrische Kombinatorik und der Algorithmischen Theorie der Konvexen Körper, welche sich alle drei rückwirkend unter den Begriff der Computational Convexity einordnen lassen.

In der Computational Convexity werden zwei in der Algorithmischen Geometrie nicht unbedingt gängige Sachverhalte betont: zum einen werden oftmals allgemeine normierte Räume betrachtet, zum anderen wird die Dimension bei den behandelten Problemstellungen explizit als Teil des Inputs verstanden, wie es in der Linearen Programmierung üblich ist.

Was bedeutet Optimales Containment?

Von Containment Problemen spricht man bei Aufgabenstellungen, deren Ziel die Bestimmung oder Approximation extremaler Körper einer gegebenen Klasse ist, welche in einer gegebenen Menge enthalten sind oder diese enthalten. Beispielhaft betrachte man den folgenden Grundtyp eines allgemeinen Containment Problems (Entscheidungsversion). Sei dazu %$d$% eine natürliche Zahl, %$\\mathcal{C}_d$% eine Familie von abgeschlossenen konvexen Teilmengen des %$\mathbb{R}^d$% und %$\omega_d:\mathcal{C}_d \to \mathbb{R}$% ein nicht-negatives und bezüglich der Mengeninklusion monotones Funktional. Weiter sei %$\Gamma = (\mathcal{C}_d)_{d \in \mathbb{N}}$% und %$\Omega=(\omega_d)_{d \in \mathbb{N}}$%. Damit lässt sich folgendes Problem stellen:

%$(\Gamma, \Omega)$%-INBODY

Eingabe: %$d \in \mathbb{N}$%, %$K \subset \mathbb{R}^d$% ein konvexer Körper und %$\lambda \in \mathbb{Q}_+$%. Frage: Existiert ein %$C \in \mathcal{C}_d$%, sodass %$C \subset K$% und %$\omega_d(C) \ge \lambda$%?

Ein wichtiger Spezialfall der Containment Probleme sind die Radien konvexer Körper. Die Bestimmung der vier Grundradien (In-, Umradius, Dicke und Durchmesser) ist ein klassisches Problem der Konvexgeometrie.

demo10.png
Darstellung der Einbettung einer Kreisscheibe mit maximalem Radius in einen Würfel.

Aufgrund zahlreicher Anwendungen, sowohl in anderen mathematischen Teildisziplinen als auch in der Medizin (z.B. bei der Mustererkennung oder der automatisierten Operationsplanung), Robotik, Visualisierung, Materialwissenschaft oder der Genetik, ist die Radienberechnung in den letzten Jahren in den Fokus vieler wissenschaftlicher Veröffentlichungen gerückt. Auch Verallgemeinerungen der Radienproblematik, die in den Bereich des optimalen Containments fallen, besitzen zahlreiche Anwendungen, wie etwa bei Shape-Fitting-, Clustering- und Datenreduktionsaufgaben. Auch hier gibt es zahlreiche neue Resultate.

An wen richtet sich die Veranstaltung?

An mathematischem Wissen vorausgesetzt wird eine solide Grundausbildung in Analysis, Linearer Algebra und Optimierung 1 (Lineare Programmierung). Kenntnisse im Bereich der Konvexen Analysis und der Kombinatorischen Optimierung helfen, sind aber nicht zwingend notwendig. Damit richtet sich die Vorlesung an alle Mathematiker und Informatiker (mit Nebenfach Mathematik) ab dem fünften Fachsemester.

Anrechenbarkeit

Für die Studierenden der Mathematik können Vorlesung und Übung als 3 SWS für eine Hauptdiplomsprüfung im Bereich der Angewandten Mathematik oder Vertiefungsfach anerkannt werden.

Die Anrechenbarkeit wurde mit Prof. Gritzmann und Prof. Taraz abgesprochen. Beide sind bereit Studierende über die Inhalte der Veranstaltung zu prüfen. Sollten Sie die Veranstaltung bei einem anderen Prüfer einbringen wollen, so klären Sie bitte im voraus, ob dieser dazu bereit ist.

Übungsblätter

Übungsblatt Hinweise
Blatt 01  
Blatt 02  
Blatt 03  
Blatt 04  
Blatt 05  
Blatt 06  

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.