Institut für Theoretische Informatik
Departement Informatik
ETH Zürich
CH-8092 Zürich

1. Professor:
   - Welzl, Emo, Dr.

2. Wissenschaftliche Mitarbeiter (Doktoranden mit Arbeitstitel der Dissertation):
   - Adamy, Udo (seit 1. März 1999)
   - Ambühl, Christoph
   - Andrzejak, Artur - Das k-Mengenproblem für Punktmengen.
   - Blömer, Johannes, Dr.
   - Gärtner, Bernd, Dr.
   - Giesen, Joachim - Kurvenrekonstruktion.
   - Hoffmann, Michael
   - John, Matthias (seit 1. Mai 1999)
   - Kettner, Lutz - Konturkanten-basiertes Entfernen verdeckter Flächen. (bis 30. September 1999)
   - May, Alexander (seit 1. September 1999)
   - Pedroni, Samuele (seit 1. Oktober 1999)
   - Trachsler, Beat - Ausfalltolerante Codes und sichere Datenübertragung auf dem Internet. (bis 28. Februar 1999)
   - Tschirschnitz, Falk
   

3. Sekretariat:
   - Krenn, Tanja
   

4. Hilfsassistenten
   - Fischer, Kaspar
   - Wagner, Uli

JEAN-PIERRE SEIFFERT, Johann Wolfgang Goethe-Universität Frankfurt, Deutschland (25. Februar 1999).
Extending Wieners attack in the presence of many decrypting exponents

GÜNTER ZIEGLER, Technische Universität Berlin, Deutschland (8. April bis 10. April 1999).
Cubical polytopes.

MEIR KATCHASLKI, Technion - Israel Institute of Technology, Israel (26. April bis 2. Juni 1999).
Common Transversals.

JEAN-PIERRE SEIFFERT, Johann Wolfgang Goethe-Universität Frankfurt, Deutschland (1. Mai bis 31. Juli 1999 ).

JÍRI MATOUSEK, Charles University Prag, Tschechische Republik (3. Juni bis 16. Juli 1999).
Discrepancy - A Tutorial, part I.
Embedding trees in Euclidean space.
Discrepancy - A Tutorial, part II.

IMRE BARANY, Hungarian Academy of Sciences, Budapest, Ungarn (23. Juni bis 27. Juni 1999).

HERBERT EDELSBRUNNER, Duke University, USA (24. Juni bis 27. Juni 1999).
Sliver Exudation.

SHOSHANA WODAK, University Libre de Bruxelles, Belgium and EMBL-EBI, Wellcome Trust Genome Campus, Cambridge, UK (24. Juni bis 26. Juni 1999).
Knowledge based potentials for the prediction of protein 3D structure.

CHEE YAP, Courant Institute of Mathematical Sciences, New York University, USA (25. Juni bis 27. Juni 1999).
Universal Construction for the FKS Scheme.

BORIS ARONOV, Polytechnic University, Brooklyn, USA (2. Juli bis 17. Juli 1999).

DIETER FELLNER, Technische Universität Braunschweig, Deutschland (16. Dezember - 20. Dezember 1999).
Web Aware Graphics .

Drittmittel

• Projekt "Priority Encoding Transmission - Codes and mulitmedia applications", finanziert durch den Schweizerischen Nationalfonds zur Förderung der wissenschaftlichen Forschung.
  Förderungszeitraum: 1. April 1997 - 31. März 1999.
  Projektleiter: J. Blömer; Mitarbeiter: B. Trachsler.
  Im Projekt wird das Problem betrachtet, hierarchisch codierte Nachrichten über Netzwerke zu senden. Hierbei wird angenommen, dass die Netze beliebige Teile der Nachricht verlieren können. Dies ist z.B. beim Internet der Fall. Priority Encoding Transmission (PET) erlaubt es dem Benutzer, verschiedene Prioritäten den Teilen einer hierarchisch codieren Nachricht zu geben. Bei einer mit PET codierten Nachricht können die Teile der Nachricht stets in Reihenfolge ihrer Priorität decodiert werden. Eine erste Implementierung von PET wurde in ein Videokonferenztool integriert, das den Videokompressionsstandard MPEG benutzt. Die verschiedenen Prioritäten werden hierbei gemäss den verschiedenen Frametypen von MPEG zugeordnet. Da MPEG die diskrete Kosinustransformation benutzt, existieren in MPEG allerdings auch intraframe Abhängigkeiten. Im Projekt soll untersucht werden, wie diese Abhängigkeiten bei der Vergabe von Prioritäten ausgenutzt werden können.
  Die wichtigsten Hilfsmittel bei PET sind sogenannte ausfalltolerante Codes. Das zweite Ziel des Projektes ist es, effiziente ausfalltolerante Codes zu entwerfen. Im günstigsten Fall sind dies Codes, die in linearer Zeit codiert und decodiert werden können.

• Projekt "Kombinatorische Schranken für geometrische und abstrakte Optimierungsprobleme", finanziert durch den Schweizerischen Nationalfonds zur Förderung der wissenschaftlichen Forschung.
  Förderungszeitraum: 2 Jahre, ab 1. August 1998.
  Projektleiter: B. Gärtner; Mitarbeiter: F. Tschirschnitz.
  Das Projekt beschäftigt sich mit beweisbar effizienten Algorithmen für das Problem der linearen Programmierung und anderer, verwandter Optimierungsprobleme. In der algorithmischen Geometrie treten eine Reihe solcher Probleme auf (z.B. kleinste Kugel um eine gegebene Punktmenge, Abstand zweier Polytope). Diese Probleme können in einem abstrakten Rahmen formuliert und gelöst werden, wobei die resultierenden Algorithmen ähnlich funktionieren wie der Simplex- Algorithmus für die lineare Programmierung.
  Die theoretischen Fragen, die sich stellen, betreffen insbesondere die Komplexität simplexartiger Verfahren. Offen ist, ob es polynomielle Schranken gibt. Die besten bekannten Resultate geben immerhin subexponentielle Laufzeiten für eine randomisierte Variante an. Andere natürliche randomisierte Varianten konnten bisher nicht analysiert werden. Ziel des Projekts ist es, einerseits die bekannten Schranken zu verbesseren, andererseits aber auch neue obere und untere Schranken für die Laufzeit verschiedener randomisierter Verfahren zu finden.

• Projekt "GALIA" (Geometric Algorithms for Industrial Application) , finanziert durch die Europäische Gemeinschaft bzw. das Bundesamt für Bildung und Wissenschaft im Rahmen des ESPRIT IV Long Term Research Program 28155 (an der ETH mit der Arbeitsgruppe von Prof. P. Widmayer).
  Förderungszeitraum: 15. November 1998 - 14. Mai 2000
  Projektleiter: E. Welzl; Mitarbeiter: M. Hoffmann.
  Ziel des Projekts ist der weiter Aufbau einer Geometrie-Bibliothek (von Algorithmen), die Implementierung von geometrischen Algorithmen, sowie allgemeine Untersuchungen solcher Implementierungen. Der Schweizer Projektteil befasst sich vor allem mit Algorithmen zur geometrischen Optimierung (B-3) und geometrischen Suchstruckturen (B-4).
  

Veröffentlichungen und Vorträge

1. Veröffentlichungen in Zeitschriften (mit Auswahlverfahren)
   

   B. GÄRTNER, Exact arithmetic at low cost - A case study in linear programming, Computational Geometry - Theory and Applications 13, (1999) 121-139.

   L. KETTNER, Using generic programming for designing a data structure for polyhedral surfaces, Computational Geometry - Theory and Applications 13, (1999) 65-90.

   
   

2. Veröffentlichungen in Konferenzbänden (mit Auswahlverfahren)
   

   A. ANDRZEJAK, K. FUKUDA, Optimization over k-set polytopes and efficient k-set enumeration, in Proc. Workshop on Algorithms And Data Structures, Lecture Notes in Computer Science 1663, (1999) 1-12.
   

   J. BLÖMER, J.-P. SEIFERT, On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice, in Proc. 31 Annual ACM Symposium on Theory of Computing, (1999) 711-720.
   

   M. HOFFMANN, A Simple Linear Algorithm for Computing Rectangular 3-Centers, in Proc. 11th Canadian Conference on Computational Geometry, (1999) 72-75.
   

   B. GÄRTNER, Fast and robust smallest enclosing balls, in Proc. of 7th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 1643, (1999) 325-338.
   

   J. GIESEN, Curve Reconstruction in Arbitrary Dimension and the Traveling Salesman Problem, in Proc. of 8th Discrete Geometry and Computational Imagery, Lecture Notes in Computer Science 1568, (1999) 164-176.
   

   J. GIESEN, Curve Reconstruction, the Traveling Salesman Problem and Menger's Theorem on Length, in Proc. of 15th ACM Symposium on Computational Geometry, (1999) 207-216.

   
   

3. Sonstige Veröffentlichungen
   

   A. ANDRZEJAK, Kryptoregulierung, in Rechtsfragen der Informationsgesellschaft, Thomas Hoeren und Robert Queck (Hrsg), (Grundlagen und Praxis des Wirtschaftsrechts Band 17), Erich Schmidt Verlag Berlin, (1999) 132-145.
   

   B. GÄRTNER, Ein Reinfall mit Computer-Zufallszahlen, Mitteilungen der DMV, 1999, Ausgabe 2, (1999) 56-60.
   

   G. KAROLYI, E. WELZL, Crossing-free segments and triangles in point configurations, in Proc. 1st Japanese-Hungarian Symp. on Discrete Math. and Its Appl., (1999) 265-272.
   

   
   

4. Berichte
   

   
   

5. Vorträge

   C. AMBÜHL
   - "A new lower bound for the list update problem", Upper Rhine Region Algorithms Workshop, Bern, Schweiz (15. Januar 1999).
   

   A. ANDRZEJAK
   - "Optimization over k-set polytopes and efficient k-set enumeration", 6th International Workshop, WADS'99, Vancouver, Canada, August 1999.
   

   J. BLÖMER
   - "Gitterprobleme in der Komplexitätstheorie und Kryoptographie", 3. Kasseler Symposium über Computational Mathematics, Universität Kassel, Deutschland (10. März 1999).
   - "Kurze unabhängige Gittervektoren und Komplexitätstheorie, Mathematisches Kolloquium, Johann Wolfgang Goethe-Universität Frankfurt, Deutschland (12. November 1999).
   

   B. GÄRTNER
   - "Combinatorial Linear Programming: Geometry Can Help", Upper Rhine Region Algorithms Workshop, Bern, Schweiz (15. Januar 1999).
   - "Pitfalls with Pseudorandom Matrices", Dagstuhl-Seminar on Computational Geometry, Dagstuhl, Deutschland (10. März 1999).
   - "Fast and robust smallest enclosing balls", 7th Annual European Symposium on Algorithms (ESA), Prag, Tschechien (17. Juli 1999).
   - "Smallest enclosing balls - Optimization in GALIA", GALIA Review Meeting, Brussels, Belgien (23. September 1999).
   

   J. GIESEN
   - "Curve Reconstruction", Upper Rhine Region Algorithms Workshop, Bern, Schweiz (16. Januar 1999).
   - "Curve Reconstruction in Arbitrary Dimension and the Traveling Salesman Problem" (Poster), 8th Discrete Geometry and Computational Imagery, Paris, Frankreich (18. März 1999).
   - "Curve Reconstruction", Vortrag am Max-Planck-Institut für Informatik, Saarbrücken, Deutschland (4. Mai 1999).
   - "Curve Reconstruction, the Traveling Salesman Problem and Menger's Theorem on Length", 15th Annual ACM Symposium on Computational Geometry, Miami, USA (14. Juni 1999).
   - "Curve Reconstruction and TSP", Monte Verità Conference on Discrete and Computational Geometry, Ascona (28. Juni 1999).
   - "Curve Reconstruction: Theory & Practice", GALIA Review Meeting, Brussels, Belgien (23. September 1999).
   

   M. HOFFMANN
   - "A Simple Linear Algorithm for Computing Rectangular 3-Centers", 11th Canadian Conference on Computational Geometry, Vancouver, Canada (17. August 1999).
   

   L. KETTNER
   - "CGAL: The Computational Geometry Algorithms Library", Tel Aviv University, Israel (13. Januar 1999).
   - "One sided error predicates in geometric computing", Tel Aviv University, Israel (17. Januar 1999).
   - "CGAL: Eine Bibliothek geometrischer Algorithmen", Informatik-Forschung konkret! Projektpräsentation, ETH Zürich, Schweiz (25. Januar 1999).
   - "Generic Programming in CGAL, the Computational Geometry Algorithms Library", Dagstuhl Seminar on Component-Based Programming under Different Paradigms, Dagstuhl, Deutschland (21.-26. Februar 1999).
   - "CGAL: The Computational Geometry Algorithms Library", Mini Workshop: Geometric Software, ETH Zürich, Schweiz (26. April 1999).
   - "CGAL: The Computational Geometry Algorithms Library", Duke University, Durham, North Carolina, USA (9. Juni 1999).
   - "CGAL: Tutorial I: Programming with CGAL", Symposium on Computational Geometry SoCG'99, Miami Beach, Florida, USA (14. Juni 1999).
   - "CGAL: The Computational Geometry Algorithms Library", Bell Labs, Lucent Technologies, Murray Hill, New Jersey, USA (21. Juni 1999).
   - "Contour Edge Based Polyhedron Visualization", INRIA, Sophia Antipolis, Frankreich (27. Juli 1999).
   

   E. WELZL
   - "Zufällige Wege zum Ziel", Mathematisches Kolloquium, ETH Zürich, Schweiz (12. Januar 1999).
   - "j-Facets of Finite Point Sets and the Upper Bound Theorem for Polytopes", Colloquium in Combinatorics, Geometric Algorithms and Optimization, ETH Zürich, Schweiz (14. Januar 1999).
   - "On the j-facets of finite point sets", Kolloquium des Graduiertenkollegs Algorithmische Diskrete Mathematik, Freie Universität Berlin, Berlin, Deutschland (15. Februar 1999).
   - "Entering and Leaving j-facets", Dagstuhl-Seminar on Computational Geometry, Dagstuhl, Deutschland (8. März 1999).
   - "On j-facets and k-sets", The Israeli Workshop on Computational Geometry (IWCG'99), Nachsholim, Israel (15. Mai 1999).
   - "On j-facets and k-sets", Paul Erdös and his Mathematics, Budapest, Ungarn (8. Juli 1999, eingeladener Vortrag).
   - "Halbieren von Punktemengen, j-Facetten und das `Upper Bound Theorem' für Polytope", 7. Österreichisches Mathematikertreffen (ÖMG), Graz, Österreich (21. September 1999, eingeladener Hauptvortrag).
   

Vorlesungen und Seminare (WS 98/99 und SS 99)

J. BLÖMER
- Informatik I für IX (Abteilung Mathematik und Physik)(Vorlesung und Übungen WS 98/99)
- Informatik II für IX (Abteilung Mathematik und Physik)(Vorlesung und Übung SS 99)

B. GÄRTNER
- Theoretische Informatik (Grundstudium, Vorlesung und Übung SS 99)

B. GÄRTNER, E. WELZL
- Algorithmische Geometrie (Vorlesung und Übung WS 98/99)

E. WELZL
- Theoretische Informatik (Kernfach, Vorlesung und Übung SS 99)
- Algebra II (Vorlesung und Übung SS 99)

Organisation von wissenschaftlichen Veranstaltungen

- Mini Workshop on Geometric Software, ETH Zürich, Schweiz, 26. April 1999 (A. Below, J. Richter-Gebert, K. Fukuda, E. Welzl).
- GALIA Developer Meeting 2/99, 27.-29. April 1999, ETH Zürich, Schweiz. (B. Gärtner, M. Hoffmann, L. Kettner).
- Monte Verità, Conference on Discrete and Computational Geometry, Ascona, Schweiz, 27. Juni - 2. Juli 1999 (J.E. Goodman, R. Pollack und E. Welzl).
- Leitung der Sektion Geometrie an der Tagung der Deutschen Mathematiker Vereinigung (DMV) in Mainz, 5.-11. September 1999 (R. Scharlau und E. Welzl).
- Late Summer School "Facets of the Polytope World", ETH Zürich, Schweiz, 13.-16. September 1999 (B. Gärtner, J. Richter-Gebert, E. Welzl).

Dissertationen

• Andrzejak, Artur
  "On k-Sets and their Generalizations"
  Betreuer: E. Welzl
  Korreferent: K. Fukuda (Departement Mathematik, ETH)
  Doktorprüfung: 17. Dezember 1999
  

• Kettner, Lutz
  "Software Design in Computational Geometry and Contour-Edge Based Polyhedron Visualization"
  Betreuer: E. Welzl
  Korreferent: J.-D. Boissonnat (INRIA Sophia-Antipolis)
  Doktorprüfung: 24. September 1999
  

• Will, Hans-Martin
  "Computation of Additively Weighted Voronoi Cells for Applications in Molecular Biology"
  Betreuer: E. Welzl
  Korreferenten: H. Edelsbrunner (University of Illinois at Urbana Champaign), S. Wodak (Free Univeristy of Brussels)
  Doktorprüfung: 25. Juni 1999
  

Diplomarbeiten

• Chinellato, Oscar
  "Subexponentielle Algorithmen für das Kürzester Vektor Problem"
  Betreuer: J. Blömer
  Beginn: 16. November 1998
  fertiggestellt am 15. März 1999
  

• Tscherter, Vincent
  "Rekonstruktion von Bahn und Karten aus Scandaten"
  Betreuer: L. Kettner und E. Welzl
  Beginn: 6. April 1999
  fertiggestellt am 5. August 1999
  

• Pedroni, Samuele
  "Aufzählen und Abzählen von Triangulierungen"
  Betreuer: B. Gärtner und E. Welzl
  Beginn: 30. April 1999
  fertiggestellt am 17. August 1999
  

• Andres, Thomas
  "Spezifikation einer Kegelschnitt-Klasse für CGAL"
  Betreuer: B. Gärtner
  Beginn: 1. Mai 1999
  fertiggestellt am 27. August 1999

Semesterarbeiten

• Fischer, Kaspar
  "Eigenschaften und dynamisches Verhalten des "Gale Transform""
  Betreuer: B. Gärtner
  fertiggestellt am 22. Juni 1999
  

• Wessendorp, Franz
  "Abstrakte Zielfunktionen auf dem 4-Würfel"
  Betreuer: B. Gärtner
  fertiggestellt am 1. März 1999
  
  

Sonstiges

U. ADAMY
- Assistent für die Vorlesung Theoretische Informatik der Abt. IIIc im SS 99.
- Teilnahme am Workshop Probabilistische Algorithmen und an der Sommerschule Probabilistische Methoden und Algorithmen, Ploen, Deutschland , 5.-8. Juni 1999.
- Teilnahme an der Late Summer School "Facets of the Polytope World", ETH Zürich, Schweiz, 13.-16. September 1999.

C. AMBÜHL
- Assistent für die Vorlesung Logik der Abt. IIIc im WS 98/99.
- Assistent für die Vorlesung Theoretische Informatik der Abt. IIIc im SS 99.
- Forschungsaufenthalt an der London Scool of Economics, England, 4.-12. September 1999.
- Teilnahme am Workshop Probabilistische Algorithmen und an der Sommerschule Probabilistische Methoden und Algorithmen, Ploen, Deutschland , 5.-8. Juni 1999.
- Teilnahme an der Late Summer School "Facets of the Polytope World", ETH Zürich, Schweiz, 13.-16. September 1999.

A. ANDRZEJAK
- Assistent für die Vorlesung Logik der Abt. IIIc im WS 98/99.
- Assistent für die Vorlesung Theoretische Informatik der Abt. IIIc im SS 99.
- Mitglied in der Hochschulversammlung (als Delegierter der AVETH) in der Arbeitsgruppe "Leistungsauftrag".
- Teilnahme an der Late Summer School "Facets of the Polytope World", ETH Zürich, Schweiz, 13.-16. September 1999.

B. GÄRTNER
- Durchführung eines BRICS-Minikurses "Abstraction and Optimization - Useful Tools for Optimization", BRICS Center, Aarhus University, Dänemark, 6.-7. Juli 1999.
- Teilnahme am GALIA Design and Implementation Meeting, Dagstuhl, Deutschland, 30. August - 3. September 1999.
- Teilnahme am GALIA Developer Meeting 3/99, Berlin, Deutschland, 7.-10. Dezember 1999.

J. GIESEN
- Assistent für die Vorlesung Informatik I der Abt. IX im WS 98/99.
- Assistent für die Vorlesung Theoretische Informatik III der Abt. IIIc im SS 99.

M. HOFFMANN
- Assistent für die Vorlesung Informatik I der Abt. IX im WS 98/99.
- Teilnahme am GALIA Developer Meeting 1/99, Sophia-Antipolis, Frankreich, 27.-29. Januar 1999.
- Teilnahme am GALIA Design and Implementation Meeting, Dagstuhl, Deutschland, 30. August - 3. September 1999.
- Teilnahme am GALIA Developer Meeting 3/99, Berlin, Deutschland, 7.-10. Dezember 1999.

M. JOHN
- Teilnahme am Workshop Probabilistische Algorithmen und an der Sommerschule Probabilistische Methoden und Algorithmen, Ploen, Deutschland , 5.-8. Juni 1999.
- Teilnahme an der Late Summer School "Facets of the Polytope World", ETH Zürich, Schweiz, 13.-16. September 1999.

L. KETTNER
- Assistent für die Vorlesung Informatik I der Abt. IX im WS 98/99.
- Assistent für die Vorlesung Theoretische Informatik III der Abt. IIIc im SS 99.
- Forschungsaufenthalt an der Tel Aviv University, 11.-18. Januar 1999.
- Teilnahme am GALIA Developer Meeting 1/99, Sophia-Antipolis, Frankreich, 27.-29. Januar 1999.
- Teilnahme am GALIA Design and Implementation Meeting, Dagstuhl, Deutschland, 30. August - 3. September 1999.

S. PEDRONI
- Teilnahme an der Late Summer School "Facets of the Polytope World", ETH Zürich, Schweiz, 13.-16. September 1999.

B. TRACHSLER
- Assistent für die Vorlesung Information und Kommunikation I der Abt. IIIc im WS 98/99.

F. TSCHIRSCHNITZ
- Assistent für die Vorlesung Informatik I der Abt. IX im WS 98/99.
- Assistent für die Vorlesung Informatik II der Abt. IX im SS 99.
- Teilnahme am Workshop Probabilistische Algorithmen und an der Sommerschule Probabilistische Methoden und Algorithmen, Ploen, Deutschland , 5.-8. Juni 1999.
- Teilnahme an der Late Summer School "Facets of the Polytope World", ETH Zürich, Schweiz, 13.-16. September 1999.

E. WELZL
- Mitglied des Editorial Boards von

• Journal of Symbolic Computation, (B. Caviness, Ed.), Academic Press
• Discrete and Computational Geometry, (J. Goodman & R. Pollack, Eds.), Springer Verlag
• Computational Geometry - Theory and Applications, (J.-R. Sack & I. Urrutia, Eds.), Elsevier Science Publishers
• Journal for Universal Computer Science, (H. Maurer, Ed.), Springer Verlag (electronic journal)
• Fundamenta Informaticae (Annales Societatis Mathmaticae Polonae, A. Skowron, Ed.), IOS Press
• ORDER, (W.T. Trotter, Ed.), Kluwer Academic Press