Activity Report 2001

Theory of Combinatorial Algorithms
Teaching and Research Group Emo Welzl

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

Personnel

---

• Professors

  Fukuda Komei (also IFOR at ETH, and Dep. Math. at EPFL)
  Sharir Micha (visiting Apr 1 - July 31; Tel Aviv)
  Welzl Emo

• Research Associates and Ph.D. Students

  Adamy Udo
  Ambühl Christoph
  Below Alexander (since Aug 1)
  Gärtner Bernd, Dr. (until Sep 16; on leave Apr 1 - Jun 30)
  Giesen Joachim, Dr. (since Mar 1)
  Hoffmann Michael
  John Matthias
  Pedroni Samuele (until Sep 30)
  Pfeifle Julian (Mar 12 - Jul 31, visiting, Graduate Program CGC from Berlin)
  Lange Carsten (Oct 1 - Dec 31, visiting, Graduate Program CGC from Berlin)
  Samal Robert (Nov 1, 2001 - Feb 10, 2002, visiting, Graduate Program CGC from Prague)
  Schurr Ingo (Graduate Program CGC since April 1)
  Schönherr Sven (until Apr 15)
  Solymosi József, Dr. (Graduate Program CGC until Mar 31; Post-Doc Apr 1 - Sep 16)
  Speckmann Bettina, Dr. (Post-Doc in Graduate Program CGC since Oct 1)
  Szabó Tibor, Dr. (Post-Doc in Graduate Program CGC)
  Tóth Csaba Dávid (Graduate Program CGC)
  Tschirschnitz Falk
  Wagner Uli
  

• Administration

  Hefti-Widmer Franziska
  

Guests

---

• GYULA KAROLYI, Eötvös University, Budapest, Hungary (Jan 4 - 31),
  An Erdös-Szekeres Type Problem in the Plane (Noon Seminar, Jan 11),
  On the Existence of a Convex Polygon with a Specified Number of Interior Points (Noon Seminar, Jan 23),
  Transversals of Additive Latin Squares (Number Theory Seminar, Jan 26).

• JOHANNES BLÖMER, Paderborn University, Paderborn, Germany (Jan 24 - 27 and Feb 7 - 10),
  Security of Low Secret Key RSA (Noon Seminar, Feb 8).

• JED MIHALISIN, Washington University, Seattle, Washington, USA (Feb 12 - Mar 16),
  Polytopal Digraphs (Noon Seminar, Feb 13).

• JÁNOS PACH, Courant Institute, New York University, New York City, USA (Feb 28 - Mar 3),
  Inevitable Intersections (Noon Seminar, Mar 1)

• GÜNTER ROTE, Berlin Free University, Germany (Mar 2 - 4),
  Integer Programming in Low Dimensions (Noon Seminar, Mar 2).

• LUTZ KETTNER, UNC Chapel Hill, Chapel Hill, North Carolina, USA (Mar 5 - 13),
  4D Voxel Data Visualization (Noon Seminar, Mar 6).

• BETTINA SPECKMANN, University of British Comlumbia, Vancouver, British Columbia, Canada (Mar 14 - 18),
  Kinetic Collision Detection for Simple Polygons, (Noon Seminar, Mar 16).

• MICHA SHARIR, Tel Aviv University, Tel Aviv, Israel (Feb 28 - Mar 1, Apr 1 - Jul 31),
  Geometric Arrangements and their Applications (Course, Fridays 10-12, Apr 6 - Jul 6),
  The Union of Geometric Objects and Generalized Voronoi Diagrams (CGC colloquium, Apr 30),
  New Bounds on Incidences (CGC workshop, May 15).

• STEFAN LANGERMAN, Rutgers University, New Brunswick, New Jersey, USA (Apr 2 - 4),
  Geometric Medians (Noon Seminar, Apr 3).

• GYÖRGY ELEKES, Eötvös University, Budapest, Hungary (Apr 6 - May 6),
  Many Collinear Triples on Algebraic Curves (Noon Seminar, May 3),
  Combinatorial Geometry and Additive Number Theory (Noon Seminar, Apr 24).

• SHMUEL ONN, Technion - Israel Institute of Technology, Haifa, Israel (Apr 9-12),
  Vector Partitions (CGC colloquium, Apr 9),
  Corner Cut Polyhedra and Groebner Bases of Point Configurations (Noon Seminar, Apr 11).

• RAIMUND SEIDEL, Saarland University, Saarbrücken, Germany (Apr 17 - 22).

• PANKAJ AGARWAL, Duke University, Durham, North Carolina, USA (May 12 - 19),
  On the Number of Congruent Simplices in a Point Set (Noon Seminar, May 17).

• VLADLEN KOLTUN, Tel Aviv University, Tel Aviv, Israel (May 12 - Jul 13),
  Segment Intersection Searching Problems in General Settings (Noon Seminar, Jun 19).

• OLEG PIKHURKO, Cambridge University, Cambridge, UK (May 22),
  Size Ramsey Numbers and Integer Programming (Noon Seminar, May 22).

• LEONID KHACHIYAN, Rutgers University, New Brunswick, USA (Jun 11 - 13),
  Generating Dual Bounded Hypergraphs (CGC colloquium, Jun 11).

• MARC VAN KREVELD, Utrecht University, Utrecht, The Netherlands (Jun 25 - 19),
  Smooth Generalization for Continuous Zooming (Noon Seminar, Jun 26),
  Cutting and Packing a Country (Noon Seminar, Jun 28).

• JIRI MATOUSEK, Charles University, Prague, Czech Republic (Aug 21-31, Oct - Nov),
  Topological Methods in Combinatorics and Geometry (Pre-Doc Course, Thursdays and Fridays, Oct 22 - Nov 23).

• MICHAEL KRIVELEVICH, Tel Aviv University, Tel Aviv, Israel (Sep 8-14),
  Deciding k-Colorability in Expected Polynomial Time (Noon Seminar, Sep 11).

• MANUEL BODIRSKY, Humboldt University in Berlin, Berlin, Germany (Oct 21 - Nov 24, visiting, Graduate Program CGC),

• KATHARINA LANGKAU, Berlin University of Technology, Berlin, Germany (Oct 18 - Nov 24, visiting, Graduate Program CGC),
  Introduction to Dynamic Network Flows (Noon Seminar, Nov 20).

• SHI LINGSHENG, Humboldt University in Berlin, Berlin, Germany (Oct 21 - Nov 24, visiting, Graduate Program CGC),

• HEIKO SCHILLING, Berlin University of Technology, Berlin, Germany (Oct 21 - Nov 23, visiting, Graduate Program CGC),

• ARNOLD WASSMER, Berlin University of Technology, Berlin, Germany (Oct 18 - Nov 28, visiting, Graduate Program CGC),
  Cyclic Polytopes and their Symmetries (Noon Seminar, Nov 6).

• NOGA ALON, Tel Aviv University, Tel Aviv, Israel (Nov 25 - 28),
  Graph Property Testing (CGC colloquium, Nov 26),
  Polynomials in Discrete Mathematics (Noon Seminar, Nov 27).

• INGO WEGENER, Dortmund University, Germany (Dec 16 - 18),
  Theoretical Aspects of Evolutionary Algorithms (CGC colloquium, Dec 17),
  Approximations by OBDDs (Noon Seminar, Dec 18).

Grants

---

• Effective Computational Geometry for Curves and Surfaces (ECG)

  (European Project.) The project intends to revisit the field of computational geometry in order to understand how structures that are well-known for linear objects behave when defined on curves and surfaces. We will consider the main geometric structures like Voroni diagrams, arrangements and Minkowski sums, study their mathematical properties, and design algorithms to construct such structures. To ensure the effectiveness of our algorithms, we will precisely specify what are the basic numerical primitives that need to be performed, and consider tradeoffs between the complexity of the algorithms (i.e. the number of primitive calls) and the complexity of the primitives and their numerical stability. Working out carefully the algebraic and robustness issues are two central objectives of the project. Another major objective is to integrate the various techniques developed in the project (e.g. algebra, arithmetics), to compare experimentally various approaches (e.g. exact versus approximate), and to provide complete solutions for some fundamental problems.
  At site Zurich we focus on surface reconstruction and several aspects of optimization within the project.

• Berlin-Zurich Graduate Program Combinatorics, Geometry, and Computation (CGC)

  (Financed by ETH Zurich and German Research Society, DFG.) Successful scientific interaction between discrete mathematics, algorithms, and application areas in computer science is increasing. In particular, combinatorics and discrete geometry provide the foundations for algorithms in general, and for combinatorial optimization and computational geometry in particular. These fields, in turn, either have direct applications or provide algorithmic concepts for many application areas such as optimization, computer graphics and vision, geographic information systems, robotics, molecular modeling and computer aided design. This initiative focuses on educating graduate students in the area where these fields interact. The Pre-Doc Program constitutes a one-semester exposure to an active research environment with dedicated research-oriented courses. The Graduate Program is a joint initiative of the departments Computer Science, Mathematics and Electrical Engineering at ETH Zurich with the three universities in Berlin (and a number of other partner institutions). The goal is to establish international contacts in both research and education, and to create a focused program with completion of a Ph.D. thesis within two and a half years. (Speakers: H. ALT, Berlin, and E. WELZL, Zurich.)

Publications

---

• Journals (with refereeing)

  K. ALLEMAND, K. FUKUDA, Th.M. LIEBLING, E. STEINER, A Polynomial Case of Unconstrained Zero-One Quadratic Optimization. Mathematical Programming Ser. A 91 (2001) 49-52.

  Ch. AMBÜHL, B. GÄRTNER, B. VON STENGEL, A New Lower Bound for the List Update Problem in the Partial Cost Model, Theoretical Computer Science 268 (2001) 3-16.

  E. BABSON, L. FINSCHI, K. FUKUDA, Cocircuit Graphs and Efficient Orientation Reconstruction in Oriented Matroids, European Journal of Combinatorics 22 (2001) 587-600.

  A. BEMPORAD, K. FUKUDA, F.D. TORRISI, Convexity Recognition of the Union of Polyhedra, Computational Geometry - Theory and Applications 18 (2001) 141-154.

  A. DUMITRESCU, B. GÄRTNER, S. PEDRONI, E. WELZL, Enumerating Triangulation Paths, Computational Geometry - Theory and Applications 20 (2001) 3-12.

  K. FUKUDA, Th.M. LIEBLING, C. LÜTOLF, Extended Convex Hull, Computational Geometry - Theory and Applications 20 (2001) 13-13.

  K. FUKUDA, A. PRODON, T. SAKUMA, Notes on Acyclic Orientations and the Shelling Lemma, Theoretical Computer Science 263 (2001) 9-16.

  B. GÄRTNER, E. WELZL, Random Sampling in Geometric Optimization: New Insights and Applications, Discrete & Computational Geometry 25 (2001) 569-590.

  Gy. KÁROLYI, E. WELZL, Crossing-Free Segments and Triangles in Point Configurations, Discrete Applied Mathematics 112 (2001) 77-88.

  J. MATOUSEK, Lower Bound on the Minus-Domination Number, Discrete Mathematics 233 (2001) 361-370.

  J. PACH, J. SOLYMOSI, Crossing Patterns of Line Segments, Journal of Combinatorial Theory Ser. A 96 (2001) 316-325.

  J. SOLYMOSI, Cs. D. TÓTH, Distinct Distances in the Plane, Discrete & Computational Geometry 25 (2001) 629-634.

  B. SPECKMANN, J. SNOEYINK, Easy Triangle Strips for TIN Terrain Models International Journal of Geographical Information Science, 15 (2001) 379-386.

  T. SZABÓ, G. TARDOS, A Multidimensional Generalization of the Erdös-Szekeres Lemma on Monotone Subsequences, Combinatorics, Probability and Computing 10 (2001) 557-565.

  U. WAGNER, E. WELZL, A Continuous Analogue of the Upper Bound Theorem, Discrete & Computational Geometry 26 (2001) 205-219.

  E. WELZL, Entering and Leaving   j-Facets, Discrete & Computational Geometry 25 (2001) 351-364.

• Conference Proceedings (with selection process)

  T. K. DEY, J. GIESEN, W. ZHAO, Robustness Issues in Surface Reconstruction, Proc. Intern. Conf. on Computat. Sci. (2001) 658-662.

  T. K. DEY, J. GIESEN, Detecting Undersampling in Surface Reconstruction, Proc. 17th Ann. ACM Symp. on Computational Geometry (2001) 257-263.

  T.K. DEY, J. GIESEN, S. GOSWAMI, J. HUDSON, R. WENGER, W. ZHAO, Undersampling and Oversampling in Sample Based Shape Modeling, Proc. IEEE Visualization (2001) 83-90.

  T.K. DEY, J. GIESEN, J. HUDSON, Delaunay Based Shape Reconstruction from Large Data, Proc. IEEE Symposium in Parallel and Large Data Visualization and Graphics (2001) 19-27.

  T.K. DEY, J. GIESEN, J. HUDSON, Sample Shuffling for Quality Hierarchic Surface Meshing, Proc. 10th International Meshing Roundtable (2001) 143-154.

  A. DEZA, K. FUKUDA, D. PASECHNIK, M. SATO, On the Skeleton of the Metric Polytope, in Discrete and Computational Geometry (J. Akiyama, M. Kano, M. Urabe, eds.), Proc. Japanese Conf. on Discrete and Comput. Geom., Lecture Notes in Computer Science 2098 (2001) 125-136.

  B. GÄRTNER, J. SOLYMOSI, F. TSCHIRSCHNITZ, P. VALTR, E. WELZL, One Line and n Points, Proc. 33rd Ann. ACM Symp. on the Theory of Computing (STOC) (2001) 306-315.

  S. HERT, M. HOFFMANN, L. KETTNER, S. PION, M. SEEL, An Adaptable and Extensible Geometry Kernel, in Proc. 5th Workshop on Algorithm Engineering (WAE), Lecture Notes in Computer Science 2141 (2001) 79-90.

  J. PACH, J. SOLYMOSI, Structure Theorems for Systems of Segments, in Discrete and Computational Geometry (J. Akiyama, M. Kano, M. Urabe, eds.), Proc. Japanese Conf. on Discrete and Comput. Geom., Lecture Notes in Computer Science 2098 (2001) 308-317.

  M. SHARIR, E. WELZL, Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem, Proc. 17th Ann. ACM Symp. on Computational Geometry (2001) 315-318.

  J. SOLYMOSI, Cs.D. TÓTH, On the Distinct Distances Determined by a Planar Point Set, Proc. 17th Ann. ACM Symp. on Computational Geometry (2001) 29-32.

  T. SZABÓ, E. WELZL, Unique Sink Orientations of Cubes, Proc. 42nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS) (2001) 547-555.

  Cs.D. TÓTH, Illuminating Polygons with Vertex  pi-Floodlights, in Proc. Intern. Conf. on Computational Science, Lecture Notes in Computer Science 2073 (2001) 772-781.

  Cs.D. TÓTH, A Note on Binary Plane Partitions, Proc. 17th Ann. ACM Symp. on Computational Geometry (2001) 151-156.

  Cs.D. TÓTH, Illuminating Both Sides of Line Segments, in Discrete and Computational Geometry (J. Akiyama, M. Kano, M. Urabe, eds.), Proc. Japanese Conf. on Discrete and Comput. Geom., Lecture Notes in Computer Science 2098 (2001) 370-380.

• Other (including submitted work)

  E.D. DEMAINE, M. HOFFMANN, Pushing Blocks is NP-Complete for Noncrossing Solution Paths, Proc. 13th Canadian Conf. on Computational Geometry (2001) 65-68.

  T.K. DEY, J. GIESEN, J. HUDSON, Decimating Samples for Mesh Simplification, Proc. 13th Canadian Conf. on Computational Geometry (2001) 85-88.

  L. FINSCHI, K. FUKUDA, Complete Combinatorial Generation of Small Point Configurations and Hyperplane Arrangements, Proc. 13th Canadian Conf. on Computational Geometry (2001) 97-100.

  B. GÄRTNER, TH. HERMANN, Computing the Width of a Point Set in 3-Space, Proc. 13th Canadian Conf. on Computational Geometry (2001) 101-104.

  B. GÄRTNER, E. WELZL, Explicit and Implicit Enforcing - Randomized Optimization, in Lectures of the Graduate Program Computational Discrete Mathematics, Lecture Notes in Computer Science 2122 (2001) 26-49.

  S. HERT, M. HOFFMANN, L. KETTNER, S. PION, M. SEEL, An Adaptable and Extensible Geometry Kernel, Technical Report #362, September 2001.

  M. HOFFMANN, Covering Polygons with Few Rectangles, Abstracts of the 17th European Workshop on Computational Geometry (EuroCG) (2001) 39-42.

  M. HOFFMANN, CS. D. TÓTH, Segment endpoint visibility graphs are Hamiltonian, Proc. 13th Canadian Conf. on Computational Geometry (2001) 109-112 (full version in electronic proceedings).

  CS. D. TÓTH, Guarding Disjoint Triangles and Claws in the Plane, Abstracts of the 17th European Workshop on Computational Geometry (EuroCG) (2001) 137-139.

  F. TSCHIRSCHNITZ, Testing Extendability for Partial Chirotopes is NP-complete, Proc. 13th Canadian Conf. on Computational Geometry (2001) 165-168.

Lectures

---

C. AMBÜHL
"List Update and Mean Payoff Games," STICERD Interdisciplinary Seminar in Game Theory, London School of Economics & Political Science, Great Britain (Jun 21, 2001).
"Offline List Update is NP-hard," Upper-Rhine-Region Algorithms Workshop, Mulhouse, France (Dec 7, 2001).

B. GÄRTNER
"n Points and One Line," Dagstuhl Seminar on Computational Geometry, Schloss Dagstuhl, Germany (Mar 21, 2001).
"Unique Sink Orientations from Convex Programs ," Towards the Peak, workshop, La Claustra, Passo del San Gottardo, Switzerland (Aug 25, 2001).
"A New Proof of the Subexponential Bound for Acyclic Unique Sink Orientations," Towards the Peak, workshop, La Claustra, Passo del San Gottardo, Switzerland (Aug 28, 2001).

J. GIESEN
"Disk Induced Flows," Upper-Rhine-Region Algorithms Workshop, Mulhouse, France (Dec 7, 2001).

M. HOFFMANN
"Pushing Blocks is Hard," Oberseminar Theoretische Informatik, Paderborn, Germany (Jan 17, 2001).
"Covering Polygons with Few Rectangles," 17th European Workshop on Computational Geometry (EuroCG), Berlin, Germany (Mar 26, 2001).
"Pushing Blocks is NP-Complete for Noncrossing Solution Paths," 13th Canadian Conference on Computational Geometry, Waterloo, Canada (Aug 15, 2001).
"An Adaptable and Extensible Geometry Kernel," 5th Workshop on Algorithm Engineering (WAE), Aarhus, Denmark (Aug 29, 2001).
"Pusing Block Puzzles," Upper-Rhine-Region Algorithms Workshop, Mulhouse, France (Dec 8, 2001).

J. SOLYMOSI
"Different Distances Between  n Points," Workshop on Combinatorics, Geometry, and Computation, Monte Verità,Centro Stefano Franscini, Ascona, Switzerland (May 15, 2001).

T. SZABÓ
"k-Wise Intersection Theorems," Workshop on Combinatorics, Geometry, and Computation, Monte Verità,Centro Stefano Franscini, Ascona, Switzerland (May 15, 2001).
"Unique Sink Orientations of Cubes," Combinatorics Seminar, University of Illinois, Urbana-Champaign, USA (May 30, 2001).
"k-Wise Intersection Theorems," Workshop and Conference on Hypergraphs (Gyula O.H. Katona is 60) , Budapest, Hungary (Jun 9, 2001)
"Unique Sink Orientations of Cubes," The 10th International Conference on Random Structures and Algorithms, Poznan, Poland (Aug 8, 2001).
"Introduction to Unique Sink Orientations," Towards the Peak, workshop, La Claustra, Passo del San Gottardo, Switzerland (Aug 25, 2001).
"Unique Sink Orientations of Cubes," 42nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS), Las Vegas, Nevada, USA (Oct 17, 2001)
"Triangle factors in Pseusorandom Graphs," The Fifteenth Midwest Conference on Combinatorics, Cryptography and Computing, Las Vegas, Nevada, USA (0ct 18, 2001)

B. SPECKMANN
"Kinetic Data Structures for Collision Detection," guest lecture, graduate course Computational Geometry, University of British Columbia, Vancouver, Canada (Nov 23, 2001).

CS. D. TÓTH
"The Number of Different Distances Determined by a Point Set," Finite and Infinite Combinatorics, Budapest, Hungary (Jan 6, 2001).
"Illuminating Simple Polygons with Vertex  pi-Floodlights," Algorithmic Discrete Mathematics and Mathematical Optimization (ADiMMO), Trier, Germany (Mar 16, 2001).
"Guarding Disjoint Triangles and Claws in the Plane," 17th European Workshop on Computational Geometry (EuroCG), Berlin, Germany (Mar 28, 2001).
"An Improvement on a Problem of Czyzowicz," Japanese-Hungarian Symp. on Discrete Math. and its Appl., Budapest, Hungary (Apr 23, 2001).
"Guarding Disjoint Triangles and Claws in the Plane," Workshop on Combinatorics, Geometry, and Computation, Monte Verità,Centro Stefano Franscini, Ascona, Switzerland (May 15, 2001).
"Illuminating Simple Polygons with Vertex pi-Floodlights," International Workshop on Computational Geometry and Applications in conjunction with Int. Conf. on Computational Sci. (ICCS'01), San Francisco, USA (May 28, 2001).
"A Note on Binary Plane Partitions," 17th Ann. ACM Symp. on Computational Geometry, Medford, USA (Jun 3, 2001).
"On the Distinct Distances Determined by a Planar Point Set," 17th Ann. ACM Symp. on Computational Geometry, Medford, USA (Jun 4, 2001).
"BSP for Line Segments With Few Distinct Directions," Elbe's Sandstones Geometry Workshop, Rynartice, Czech Republic (Jul 24, 2001).
"Segment Endpoint Visibility Graphs are Hamiltonian," 13th Canadian Conference on Computational Geometry, Waterloo, Canada (Aug 14, 2001).
"Improvements on the Vertex pi-guard Problem," Upper-Rhine-Region Algorithms Workshop, Mulhouse, France (Dec 8, 2001).

F. TSCHIRSCHNITZ
"One Line and n Points," 33rd Annual ACM Symposium on Theory of Computing, Hersonissos, Crete, Greece (Jul 7, 2001).
"Testing Extendability for Partial Chirotopes is NP-complete," 13th Canadian Conference on Computational Geometry, Waterloo, Canada (Aug 14, 2001).
"One Line and n Points," Towards the Peak, workshop, La Claustra, Passo del San Gottardo, Switzerland (Aug 28, 2001).

U. WAGNER
"On the Number of Corner Cuts," Elbe's Sandstones Geometry Workshop, Rynartice, Czech Republic (Jul 28, 2001).

E. WELZL
"Algorithmen: Fluch und Segen der Spitzfindigkeit," Kolloquium Mathematik, Informatik und Unterricht, ETH Zürich, Switzerland (Jan 11, 2001).
"One Line and n Points - Analysis of LP-Related Randomized Processes," La Sapienza, Rome, Italy (Feb 12, 2001).
"Incarnations of the Generalized Lower Bound Theorem," Dagstuhl Seminar on Computational Geometry, Schloss Dagstuhl, Germany (Mar 22, 2001).
Unique Sink Orientations of Cubes, 17th European Workshop on Computational Geometry (EuroCG), Berlin, Germany (Mar 27, 2001; invited lecture).
"Beweise, Bilder und Zufälle," Diplomfeier (Mathematik, Physik und Rechnergestützte Wissenschaften), ETH Zürich, Switzerland (Apr 26, 2001).
"Random vs. Best Choices," Future of Computer Science Symposium, Graz, Austria (Jun 8, 2001)
"Unique Sink Orientations of Cubes," Seminar on Stochastic Processes, Univ. Zürich, Switzerland (Jun 20, 2001).
"Antipodal Orientations and Reach-Maps in Unique Sink Orientations of Cubes," Towards the Peak, workshop, La Claustra, Passo del San Gottardo, Switzerland (Aug 28, 2001).
"Combinatorial Methods for Linear Programming and Related Problems (Part I: A Simple Sampling Lemma and LP-type Problems, Part II: Unique Sink Orientations of Cubes)," 2nd Max-Planck Advanced Course on the Foundations of Computer Science, Saarbrücken, Germany (Sep 4 and 5, 2001).
"Unique Sink Orientations of Cubes," APPLIGRAPH Symposium, Leiden, The Netherlands (Sep 25, 2001).
"Discrete Geometry under the Gale Transform," Fall School on Discrete Geometry - Triangulations from Various Points of View (CGC Graduate program), Alt Ruppin, Germany (Oct 4-6, 2001).
"Unique Sink Orientations of Cubes," Colloquium of the Graduate Program "Effiziente Algorithmen und Mehrskalenmethoden," Kiel, Germany (Dec 7, 2001).

Courses and Seminars

---

Winter 00/01

• Approximation: Theory and Algorithms (Pre-Doc Course), J. Blömer, M. Cochand, B. Gärtner, P. Widmayer.

• Combinatorial Geometry (Pre-Doc Course), K. Fukuda, J. Richter-Gebert.

• Seminar der Theoretischen Informatik (Noon Seminar), B. Gärtner, E. Welzl.

• Randomized Algorithms (Pre-Doc Course), E. Welzl.

• Geometrisches Rechnen, E. Welzl.

Summer 01

• Theoretische Informatik (Kernfach), E. Welzl.

• Algebra II, E. Welzl.

• Geometric Arrangements and their Applications (english), M. Sharir.

• Seminar der Theoretischen Informatik (Noon Seminar), B. Gärtner, T. Szabó, E. Welzl.

Organization of Workshops etc.

---

• Combinatorics, Geometry, and Computation, workshop of the Berlin-Zurich CGC Graduate Program, Centro Stefano Franscini, Monte Verità, Ascona, Switzerland, May 13-15, 2001, (E. Welzl).

• Towards the Peak, workshop, La Claustra, Passo del San Gottardo, Switzerland, Aug 24-30, 2001, (B. Gärtner, E. Welzl)

Dissertations

---

• József Solymosi, Ramsey-Type Results on Planar Geometric Objects
  Advisor: E. Welzl / Co-referees: J. Pach, Courant Inst., NYU, and G. Rote, FU Berlin / Defense: Mar 2, 2001

Diploma Theses

---

• Fischer Kaspar, The Smallest Enclosing Ball of Balls
  Advisor: B. Gärtner / Completed: Apr 3, 2001.
  

• Wessendorp Franciscus, Notes on Morris' Cube Orientations
  Advisor: B. Gärtner / Completed: Mar 18, 2001.
  

Semester Theses and Pre-Doc Projects

---

• Brändle Markus, Flächenvereinfachung
  Advisor: U. Adamy / Completed: Oct 18, 2001.

• Péter Csorba, Finding Transversals with Bounded Components, (Pre-Doc mid term)
  Advisor: T. Szabó / Completed: Dec 20, 2001.

• Eisenring Michael, Decomposition of Masses, (Pre-Doc mid term)
  Advisor: M. Cieliebak, Zs. Lipták, E. Welzl / Completed: Dec 20, 2001.

• Gatto Michael, Enumerating Corner Cuts
  Advisor: U. Wagner / Completed: Mar 30, 2001.

• Gehr Philipp, Delaunay Based Feature Detection in 2D
  Advisors: J. Giesen, U. Adamy / Completed: Oct 11, 2001.

• Pietrzak Krzysztof, Ist OPT=OPTBAR NP-hart?
  Advisor: C. Ambühl / Completed: Mar 30, 2001.

• Stöcklin Michel, Delaunay Based Feature Detection in 3D
  Advisors: J. Giesen, U. Adamy / Completed: Oct 11, 2001.

• Stojakovic Milos, Small Sample Spaces, (Pre-Doc mid term)
  Advisor: E. Welzl / Completed: Dec 20, 2001.

• Wessendorp Franciscus, Optimal Search in Unique Sink Orientations of the 5-Cube, (Pre-Doc mid term)
  Advisor: T. Szabó / Completed: Dec 20, 2001.

Miscellaneous

---

U. ADAMY
Teach. Assistance Logik (WS00/01), Theoretische Informatik (Kernfach; SS01; 2×).

C. AMBÜHL
Teach. Assistance Diskrete Optimierung (WS00/01), Informatik II (SS01).

J. GIESEN
Teach. Assistance Theoretische Informatik (Kernfach, SS01).

M. HOFFMANN
Teach. Assistance Geometrisches Rechnen (WS00/01).

M. JOHN
Coordinator ECG (project: Effective Computational Geomtry for Curves and Surfaces).
Teach. Assistance Logik (WS00/01), Informatik II (SS01).

S. PEDRONI
Teach. Assistance Informatik I (D-MATH/PHYS; WS00/01), Theoretische Informatik (Kernfach, SS01).

S. SCHÖNHERR
Teach. Assistance Informatik I (D-MATH/PHYS; WS00/01).
Design, Realization, and Maintenance of the WWW-Site of the Graduate Program "Combinatorics, Geometry, and Computation".

J. SOLYMOSI
Teach. Assistance Approximation: Theory and Algorithms (WS00/01), Geometric Arrangments and Their Applications (SS01).

T. SZABÓ
Teach. Assistance Randomized Algorithms (WS00/01).

U. WAGNER
Coordinator Noon Seminar.
Teach. Assistance Combinatorial Geometry (WS00/01), Theoretische Informatik (Kernfach; SS01; 2×).

F. TSCHIRSCHNITZ
Board member of VMI (Mittelbauvertretung D-INFK), Information Officer.
Teach. Assistance Logik (WS00/01), Theoretische Informatik (SS01).
Maintenance of the WWW-Site of the Graduate Program "Combinatorics, Geometry, and Computation" and of "Theory of Combinatorial Algorithms" group.

E. WELZL
Editorial Board member of

• 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, (K. Mehlhorn & J.-R. Sack, 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

Program committee member of

• The Australasian Theory Symposium (CATS 2001), (Queensland, Australia, Jan 29 - Feb 2, 2001)

• 5th Hellenic-European Research on Computer Mathematics and its Applications Conference (HERCMA 2001), (Athens, Greece, Sep 20-22, 2001)

Speaker of Graduate Program `Combinatorics, Geometry, and Computation' (Site Zürich).
Member of the EATCS Council (European Association of Theoretical Computer Science).
Coreferee (opponent) of Ph.D. of Juriaan Hage, Leiden University, The Netherlands.
Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI).
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.
Mitglied des Dozentenausschuss der ETH Zürich.
Delegierter für Professorenwahlen an der ETH Zürich.