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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Activity Report 1996

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. (seit 1. April 1996)

  2. Wissenschaftliche Mitarbeiter (Doktoranden mit Arbeitstitel der Dissertation):
    - Andrzejak, Artur (seit 1. Oktober 1996) -- Das k-Mengenproblem für Punktmengen.
    - Blömer, Johannes, Dr. (seit 1. April 1996, Oberassistent)
    - Giesen, Joachim (seit 1. Mai 1996) -- Oberflächenrekonstruktion.
    - Hoffmann, Michael (seit 1. Dezember 1996, CGAL)
    - Kettner, Lutz (seit 1. April 1996) -- Konturkanten-basiertes Entfernen verdeckter Flächen.
    - von Stengel, Bernhard, PD Dr. (seit 1. April 1996, Heisenberg-Stipendium)
    - Will, Hans-Martin (seit 1. April 1996) -- Algorithmen zu Problemen der Molekülgeometrie.

  3. Sekretariat:
    - Krenn, Tanja (seit 24. Mai 1996)


Gäste und Vorträge

PANKA AGARWAL, Duke University, Durham, USA (16. Mai bis 18. Mai 1996).
Multiresolution Representation for Surfaces and Curves.

JIRI MATOUSEK, Karlsuniversität Prag, Tsch. Republik (1. Mai bis 30. Juni 1996).
Approximation by zonotopes, numerical integration, and discrepancy.
Constants for Cuttings.

HELMUT ALT, Freie Universität Berlin, Deutschland (23. August bis 2. September 1996).

JÜRGEN RICHTER-GEBERT, Technische Universität Berlin, Deutschland (21. September bis 24. September 1996).
Cinderella, a Program for Geometric Drawing.

BERND GÄRTNER, Freie Universität Berlin, Deutschland (22. September bis 4. Oktober 1996).

MICHA SHARIR, Tel Aviv University, Israel (30. September bis 31. Oktober 1996).
K-sets: panem et circences.
Davenport-Schinzel Sequences, Lower Envelopes.

MICHAEL LUBY, DEC SC R, Palo Alto and Computer Science Division UC, Berkeley, USA (14. November bis 17. November 1996).
Fast, Practical, Randomized Erasures-Resilient Codes.

ULRICH KORTENKAMP, Technische Universität Berlin, Deutschland (15. Dezember bis 18. Dezember 1996).
Extremale Eigenschaften von 0/1-Polytopen.


Drittmittel


Veröffentlichungen und Vorträge

  1. Veröffentlichungen in Zeitschriften (mit Auswahlverfahren)

    A. ALBANESE J. BLÖMER, J. EDMONDS, M. LUBY, M. SUDAN, Priority Encoding Transmission, IEEE Transactions on Information Theory 42, 1996, 1737-1744.

    R. AVENHAUS, M. D. CANTY, D. M. KILGOUR, B. VON STENGEL, S. ZAMIR, Invited review: ``Inspection games in arms control'', European Journal of Operational Research 90, 1996, 383-394.

    B. VON STENGEL, Efficient computation of behavior strategies, Games and Economic Behavior 14, 1996, 220-246.

    D. KOLLER, N. MEGIDDO, B. VON STENGEL, Efficient computation of equilibria for extensive two-person games, Games and Economic Behavior 14, 1996, 247-259.

    J. MATOUSEK, M. SHARIR, E. WELZL, A subexponential bound for linear programming, Algorithmica 16, 1996, 498-516.


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

    ANDREAS FABRI, GEERT-JAN GIEZEMAN, LUTZ KETTNER, STEFAN SCHIRRA, SVEN SCHÖNHERR, The CGAL Kernel: A Basis for Geometric Computation, ACM Workshop on Applied Computational Geometry, Philadelphia, Pennsylvenia, 27.-28. Mai 1996, ed. M. C. Lin and D. Manocha, 1996, 191-202 (Lecture Notes in Computer Science 1148).

    MICHA SHARIR, EMO WELZL, Rectilinear and Polygonal p-Piercing and p-Center Problems, ``Proc. 12th Annual ACM Symposium on Computational Geometry'', 1996, 122-132.


  3. Sonstige Veröffentlichungen

    B. VON STENGEL, A. H. VAN DENELZEN, A. J. J. TALMAN Tracing equilibria in extensive games by complementary pivoting. Discussion paper Nr. 9686, Center for Economic Research, Universität Tilburg, 1996, 30 Seiten.

    EMO WELZL, BERND GÄRTNER, Linear Programming - Randomization and Abstract Frameworks, ``Proc. 13th Annual Symp. on Theoretical Aspects of Computer Sci.'', 1996, 669-688 (Lecture Notes in Computer Science 1046).

    EMO WELZL, Suchen und Konstruieren durch Verdoppeln, in Highlights der Informatik (Ingo Wegener, Hrsg.), Springer, 1996, 221-228.


  4. Berichte

    253
    B. VON STENGEL, Computing equilibria for two-person games (1996), 62 Seiten. Eingeladener Beitrag zum Handbook of Game Theory, erscheint in Band 3, Hrsg. R. J. Aumann und S. Hart, North-Holland, Amsterdam.

    257
    J. BLÖMER, R. KARP, E. WELZL, The Rank of Sparse Random Matrices over Finite Fields.

    258
    LUTZ KETTNER, EMO WELZL, Contour Edge Analysis for Polyhedron Projections.


  5. Vorträge

    A. ANDRZEJAK
    - ``Relations between numbers of k-sets and numbers of j-facets'', Kolloquium über Kombinatorik 1996, Braunschweig, Deutschland (14.-16. November 1996).

    J. BLÖMER
    - ``Priority Encoding Transmission - Wie man mit Paketverlusten aus dem Internet umgehen kann'', Informatik Kolloquium, Zürich, Schweiz (1. November 1996).

    L. KETTNER
    - ``Contour Edge Based Polyhedron Visualization'', Kolloquium des Graduiertenkollegs Algorithmische Diskrete Mathematik, Berlin, Deutschland (3. Juni 1996).
    - ``Tools for the CGAL Kernel User Manual'', CGAL Startup Meeting, Zürich, Schweiz (23. September 1996).
    - ``3D Polyhedrons in a Halfedge Data Structure'', CGAL Startup Meeting, Zürich, Schweiz (24. September 1996).
    - ``Contour Edge Analysis for Polyhedron Projections'', Proc. Int. Conf. Theory and Practice of Geometric Modeling, Blaubeuren, Deutschland (18. Oktober 1996).

    B. VON STENGEL
    - ``Effiziente Lösung von Spielbäumen'', Fakultät für Mathematik und Informatik, Universität Leipzig, Deutschland (11. Juni 1996).
    - ``Computation of Equilibria in Games'', Institut für Operations Research, ETH Zürich, Schweiz (4. Juli 1996).
    - ``Computation of Equilibria for Normal and Extensive Form Games'', eingeladener Hauptvortrag, International Conference on Game Theory, Stony Brook, New York, USA (15. Juli 1996).
    - ``Tracing Equilibria in Extensive Games by Complementary Pivoting'', International Conference on Game Theory, Stony Brook, New York, USA (16. Juli 1996).
    - ``Efficient Computation of Equilibria for Extensive Games'', Center for Mathematical Studies in Economics and Management Science, Northwestern University, Evanston, Illinois, USA (24. Juli 1996).
    - ``Effiziente Lösung von Spielbäumen'', Kolloquium Informatik, ETH Zürich, Schweiz (2. November 1996).
    - ``Efficient Solution of Game Trees'', Colloquium Optimization, Games and Applications, Ecole Polytechnique, Paris, Frankreich (5. Dezember 1996).

    E. WELZL
    - ``Geometrie und Zufall - Algorithmen und Kombinatorik'', Vortragsreihe Informatik, Universität Dortmund, Deutschland (30. Januar 1996).
    - ``Linear Programming - Randomized Algorithms and Abstract Frameworks'', eingeladener Hauptvortrag, 13th Symposium on Theoretical Aspects of Computer Science (STACS `96), Grenoble, Frankreich (24. Februar 1996).
    - ``Abstractions of Linear and Convex Programming - Quest for Lower Bounds'', eingeladener Hauptvortrag, Annual Meeting of the Dutch Society for Theoretical Computer Science, Utrecht, Niederlande (1. März 1996).
    - ``Contour edges of polyhedron projections'', DREI Workshop on Hot Topics in Computational Geometry, Princeton, USA (12. Juli 1996).
    - ``Algorithmen'', Sommerakademie der Studienstiftung des Deutschen Volkes, Molveno, Italien (9. September 1996).
    - ``Rectilinear p-centers in the plane'', Workshop on Combinatorial Optimization, Mathematisches Forschungszentrum Oberwolfach, Deutschland (18. Oktober 1996).
    - ``CGAL - A European Project: From Geometry Algorithms to Geometry Programs'', Algorithms - The Bridge From Theory to Practice, ETH Zürich, Schweiz (25. Oktober 1996).
    - ``Suchen und Konstruieren durch Verdoppeln'', Gemeinsames Kolloquium Mathematik und Informatik, Universität Konstanz, Deutschland (22. November 1996).
    - ``Konfigurationen von Liniensegmenten in der Ebene und Dreiecken im Raum - neue Analysen'', Vorlesung des Graduiertenkollegs Alrgorithmische Diskrete Mathematik, Freie Universität Berlin, Deutschland (2. Dezember 1996).

    M. WILL
    - ``Implementing Johnson-Mehl Diagrams for Applications in Molecular Biology'', CGAL-Startup Meeting, ETH Zürich, Schweiz (24. September 1996).
    - ''Effizientes und Tolerantes Retrieval in Terminologiedatenbanken'', Trados-Entwickler-Treffen, Stuttgart, Deutschland (9. Oktober 1996).


Vorlesungen und Seminare (WS 96/97)

J. BLÖMER
- Berechnungskomplexität kombinatorischer Probleme (Vorlesung und Übungen WS 96/97)

B. VON STENGEL
- Logik (Vorlesung und Übungen WS 96/97)

E. WELZL
- Informatik I für III B (Abteilung Elektrotechnik)(Vorlesung und Übungen WS 96/97)


Organisation von wissenschaftlichen Veranstaltungen

CGAL Start-Up Meeting, ETH Zürich, Schweiz, 23.-24. September 1996 (Organisation: Lutz Kettner, Tanja Krenn und Emo Welzl).

Arbeitsgruppenleitung ``Zufall statt Notwendigkeit - Randomisierte Algorithmen'', Sommerakademie der Studienstiftung des Deutschen Volkes, Molveno, Italien (2.-15. September 1996; Helmut Alt und Emo Welzl).


Sonstiges

A. ANDRZEJAK
- Konferenzbesuch: 12th European workshop on computational geometry, Münster, Deutschland, (28.-29. März 1996)
- Assistent für die Vorlesung Informatik I für die Abt. IIIb im WS 96/97

J. BLÖMER
- Gutachter für Computational Complexity

J. GIESEN
- Assistent für die Vorlesung Informatik I für die Abt. IIIb im WS 96/97

L. KETTNER
- Gutachter für das ACM Solid Modeling Symposium 1997
- Besuch der ACM SIGGRAPH'96 Konferenz in New Orleans
- Assistent für die Vorlesung Informatik II für die Abt. IIIc im SS 96
- Chefassistent für die Vorlesung Informatik I für die Abt. IIIb im WS 96/97

B. VON STENGEL
- Gutachter für Computing, Games and Economic Behavior, Management Science
- Rezensent für Mathematical Reviews
- Teilnahme am 1. Berlin-Trierer Workshop zur Algorithmischen Diskreten Mathematik und Mathematischen Optimierung, Trier (1.-2. April 1996)

E. WELZL
- Mitglied des Editorial Boards von

- Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI)
- Mitglied der Computational Geometry Steering Committee (Vorsitz: Prof. Joseph S. B. Mitchell, SUNY Stony Brook, USA)
- Mitglied des Gödel Prize Committee (SIGACT ACM und EATCS, Vorsitz: Prof. Grzegorz Rozenberg, Universität Leiden, Niederlande)
- Mitglied der Kommission Leistungsklassen in der Analysis I und II (ETH Zürich, Vorsitz: Prof. Max-Albert Knus)
- Herausgeber eines Sonderbandes in Discrete and Computational Geometry, 16:4, Dezember 1996, 317-479
- Referent und Betreuer in den Promotionsverfahren Torsten Thiele (Freie Universität Berlin, gem. mit Prof. Martin Aigner), David Alberts (Freie Universität Berlin), und Barbara Wolfers (Freie Universität Berlin)
- Koreferent in den Promotionsverfahren Boaz Taganski (Universität Tel Aviv), und Viet-Hai Nguyen (ETH Zürich)

M. WILL
- Teilnahme am DMV-Seminar ``Probability and Algorithms'' bei R. Karp, A. Sinclair & M. Steele, Oberwolfach, 26. Mai bis 1. Juni 1996
- Assistent für die Vorlesung Informatik II für die Abt. IIIc im SS 96
- Assistent für die Vorlesung Informatik I für die Abt. IIIb im WS 96/97


Tanja Krenn
Fri Jun 20 16:31:27 MET DST 1997