Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Activity Report 1999

Arbeitsgruppe Prof. Dr. Emo Welzl

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

Mitglieder
  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

Gäste und Vorträge

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


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


Diplomarbeiten


Semesterarbeiten


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

- Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI)
- Mitglied des Gödel Prize Committee (SIGACT ACM und EATCS)
- Mitglied des Programmkommitees of the 3th Annual Workshop on Randomization in Computer Science (RANDOM '99), (Berkeley, USA, 8. - 10. August 1999).
- Mitglied der Prüfungsgruppe des Schwerpunktprogramms "Effiziente Algorithmen für Diskrete Probleme und ihre Anwendungen" der Deutschen Forschungsgemeinschaft (DFG)
- Mitglied der Konferenz der Dozenten der ETH Zürich.
- Vorsteher des Instituts für Theoretische Informatik der ETH Zürich.
- Mitglied der Kommission Pflichtwahlfach der ETH Zürich.
- Korreferent bei Kauffmann, Pierre, "La Construction du Diagramme de Delaunay par Balayage dans le Plan et ses Applications", Universität Mulhouse, Frankreich, Doktorprüfung: 30. November 1999.

Tanja Krenn
Tue, Okt 19, 1999