Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Institut für Theoretische Informatik Departement Informatik ETH Zürich CH-8092 Zürich |
phone +41-1-632 73 92 fax +41-1-632 11 72 |
Personnel
Adamy Udo
Ambühl Christoph (until Aug 31)
Below Alexander (until Sep 30)
Csorba Péter (Graduate Program CGC,
since April 1)
Fischer Kaspar (Graduate Program CGC,
since May 1)
Gärtner Bernd, Dr. (since Aug 1)
Giesen Joachim, Dr.
Hoffmann Michael
John Matthias
Okamoto Yoshio (Graduate Program CGC,
since April 1)
Schurr Ingo (Graduate Program CGC)
Speckmann Bettina, Dr. (Post-Doc in Graduate Program CGC)
Stojakovic Milos (Graduate Program CGC,
since May 15)
Szabó Tibor, Dr. (Post-Doc in Graduate Program CGC,
until Aug 31)
Tóth Csaba Dávid (Graduate Program CGC, until Aug 31)
Tschirschnitz Falk
Wagner Uli
Hefti-Widmer Franziska
Guests
Samal Robert, Charles University, Prague, Czech Republic (Nov 1, 2001 - Feb 10, 2002, visiting, Graduate Program CGC from Prague)
Heiko Vogler,
Dresden University of Technology, Germany,
(Jan 13 - 20, 2002),
Tree Transducer with Cost Functions
(Noon Seminar, Jan 17, 2002).
Gábor Tardos,
Alfréd Rényi Institute of Mathematics,
Hungarian Academy of Sciences,
Budapest, Hungary (Jan 14 - 25, 2002),
Distinct Sums and Distinct Distances
(Noon Seminar, Jan 22, 2002).
Susanne Albers,
Freiburg University, Germany (Feb 8, 2002),
Caching in Large Networks
(Noon Seminar, Feb 8, 2002).
Bernhard von Stengel, London School of Economics and Political Science (Feb 8-12, 2002),
Coordination in Game Trees
(Noon Seminar, Feb 11, 2002).
Micha Sharir,
Tel Aviv University, Tel Aviv, Israel (Mar 24 - Apr 2, 2002),
Incidences between Points and Circles in Higher Dimensions and Their Applications
(Noon Seminar,
Mar 26, 2002)
What Vladlen and I were working on in Zurich last year
(Noon Seminar,
Mar 28, 2002).
Marc Van Kreveld, Utrecht University, Utrecht, The Netherlands (Mar 26 - Apr 1, 2002),
Sweeping Nicely through Polyhedra and Polygons
(Noon Seminar, Mar 27, 2002).
Günter Rote, Freie Univ. Berlin, Berlin, Germany (May 3-4, 2002),
Locked Linkages and Rigidity of Self-Touching Frameworks
(Noon Seminar, May 3, 2002).
Jiri Matousek,
Charles University, Prague, Czech Republic
(May 20 - Jun 30, 2002).
In Praise of Fractional Helly Theorems,
(CGC Colloquium, Jun 10, 2002).
Imre Bárány, Alfréd Rényi Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Hungary (Jun 21-23, 2002)
Friedhelm Meyer auf der Heide,
Paderborn University, Germany (Jun 17-18, 2002),
Data Management in Networks
(CGC Colloquium, Jun 17, 2002).
The Randomized z-Buffer Algorithm (Noon Seminar, Jun 18, 2002).
Mordecai J. Golin,
Hong Kong University of Science and Technology, Hong Kong, China (Jul 5, 2002),
The Probabilistic Complexity of the Voronoi Diagram of Points on a Polyhedron
(Noon Seminar, Jul 5, 2002).
Martin Kutz, Berlin, Free University, Germany (Oct 21 - Nov 22),
News from Angel and Devil
(Noon Seminar, Nov 14, 2002).
Ferdinando Cicalese, Dipartimento di Informatica ed Applicazioni "Renato M. Capocelli", Università di Salerno, Italy (Oct 21 - Nov 22).
Morten Hegner Nielsen, Department of Mathematics and Computer Science (IMADA), University of Southern Denmark, Denmark (Oct 21 - Nov 22).
Grants
(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.
(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
U. Adamy, J. Giesen, M. John, Surface Reconstruction Using Umbrella Filters, Computational Geometry - Theory and Applications 21 (2002) 63-86.
B. Gärtner, The Random-Facet Simplex Algorithm on Combinatorial Cubes, Random Structures and Algorithms 20 (2002) 353-381.
G. Karolyi, J. Solymosi, Almost Disjoint Triangles in 3-Space, Discrete & Computational Geometry 28 (2002) 577-583.
D. Kirkpatrick, J. Snoeyink, B. Speckmann, Kinetic Collision Detection for Simple Polygons. International Journal of Computational Geometry and Applications 12 (2002) 3-27.
J. Matousek, A Lower Bound for Weak Epsilon-Nets in High Dimension, Discrete & Computational Geometry 28 (2002) 45-48.
J. Solymosi, G. Tardos, Cs. D. Tóth, The k Most Frequent Distances in the Plane, Discrete & Computational Geometry 28 (2002) 639-648.
Cs. D. Tóth, Art Galleries with Guards of Uniform Range of Vision, Computational Geometry - Theory and Applications 21 (2002) 185-192.
Cs. D. Tóth, Illumination in the Presence of Opaque Line Segments in the Plane, Computational Geometry - Theory and Applications 21 (2002) 193-204.
U. Wagner, On the Number of Corner Cuts, Advances in Applied Mathematics 29 (2002) 152-161.
U. Adamy, C. Ambühl, S. Anand, Th. Erlebach, Call Control in Rings, Proc. 29th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science 2380 (2002) 788-799.
P.K. Agarwal, T. Hagerup, R. Ray, M. Sharir, M. Smid, E. Welzl, Translating a Planar Object to Maximize Point Containment, Proc. 10th European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 2461 (2002) 42-53.
Ch. Ambühl, U. Wagner, On the CLIQUE Problem in Intersection Graphs of Ellipses, Proc. 13th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science 2518 (2002) 489-500.
M. Cieliebak, Th. Erlebach, Zs. Lipták, J. Stoye, E. Welzl, Algorithmic Complexity of Protein Identification: Searching in Weighted Strings, Proc. of 2nd IFIP Conference on Theoretical Computer Science, (2002) 143-156, Kluwer Adacemic Publishers.
T. K. Dey, J. Giesen, S. Goswami, W. Zhao, Shape Dimension and Approximation from Samples, Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA) (2002) 772-780.
J. Giesen, M. John, New Diagrams from Disks in the Plane, Proc. 19th International Symp. on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 2285 (2002) 238-249.
J. Giesen, M. John, Duality in Disk Induced Flows, Proc. 2nd Intern. Conf. on Computational Science (ICCS), Intern. Workshop on Computational Geometry and Applications (CGA), Lecture Notes in Computer Science 2331 (2002) 154-163.
J. Giesen, M. John, Surface Reconstruction Based on a Dynamical System, Proc. 23rd Annual Conference of the European Association for Computer Graphics (Eurographics), Computer Graphics Forum 21 (2002) 363-371.
J. Giesen, A. Völker, Requirements Interdependencies and Stakeholder Preferences, Proc. IEEE Joint International Requirements Engineering Conference (RE) (2002) 206-209.
J. Giesen, R. Wattenhofer, A. Zollinger, Towards a Theory of Peer-to-Peer Computability, Proc. 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Proceedings in Informatics 13 (2002) 115-132, Carleton Scientific.
J. Hage, T. Harju, E. Welzl, Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes, Proc. 1st International Conference on Graph Transformation (ICGT), Lecture Notes in Computer Science 2505 (2002) 148-160.
D. Kirkpatrick, B. Speckmann, Kinetic Maintenance of Context-Sensitive Hierarchical Representations of Disjoint Simple Polygons, Proc. 18th Ann. ACM Symp. on Computational Geometry (2002) 179-188.
M. van Kreveld, B. Speckmann, Cutting a Country for Smallest Square Fit, Proc. 13th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science 2518 (2002) 91-102.
M. Laumanns, L. Thiele, E. Zitzler, E. Welzl, K. Deb, Running Time Analysis of Multi-objective Evolutionary Algorithms on a Simple Discrete Optimization Problem, Parallel Problem Solving From Nature, Lecture Notes in Computer Science 2439 (2002) 44-53.
I. Schurr, T. Szabó, Finding the Sink Takes some Time - An almost Quadratic Lower Bound for Finding the Sink of Unique Sink Oriented Cubes, Proc. 10th European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 2461 (2002) 833-844.
M. Sharir, E. Welzl, Point-Line Incidences in Space, Proc. 18th Ann. ACM Symp. on Computational Geometry (2002) 107-115.
Cs. D. Tóth, Binary Space Partition for Line Segments with a Limited Number of Directions, Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA) (2002) 465-471.
O. Aichholzer, F. Aurenhammer, H. Krasser, B. Speckmann, Convexity minimizes Pseudo-Triangulations, Proc. 14th Canadian Conference on Computational Geometry (2002) 158-161.
O. Aichholzer, B. Speckmann, I. Streinu, The Path of a Pseudo-Triangulation, Abstracts of the DIMACS Workshop on Computational Geometry, Piscataway (NJ), USA, (2002), 2 pages.
E. D. Demaine, R. A. Hearn, M. Hoffmann, Push-2F is PSPACE-Complete, Proc. 14th Canadian Conference on Computational Geometry (2002) 31-35.
K. Fischer, B. Gärtner, CGAL-based implementation of smallest enclosing ball of balls, ECG Technical Report No. ECG-TR-121202-01 (2002) 4 pages.
J. Giesen, M. John, The Complexity of flow diagrams in the plane, Proc. 14th Canadian Conference on Computational Geometry (2002) 45-48.
J. Giesen, M. John, How to Add Facet Attributes to CGAL's 3D Geometric Triangulations, Proc. CGAL User Workshop (2002) 4 pages.
M. Hoffmann, Cs. D. Tóth, Alternating Paths through Disjoint Line Segments, Abstracts of the 18th European Workshop on Computational Geometry (EuroCG) (2002) 23-26.
M. Hoffmann, Cs. D. Tóth, Connecting Points in the Presence of Obstacles in the Plane, Proc. 14th Canadian Conference on Computational Geometry (2002) 63-67.
K. Kashiwabara, T. Uno, Y. Okamoto, Representation of clique complexes by stable-set partitions, (in Japanese), Proc. of Ouyou Suugaku Goudou Kenkyuu Shuukai (2002) 49-52.
Y. Okamoto, Traveling salesman games with the Monge property, ICM2002GTA Proceeding Volume (2002) 625-629.
Y. Okamoto, Submodularity of some classes of the combinatorial optimization games, (in Japanese), IPSJ SIGNotes ALgorithms 085 (2002).
Y. Okamoto, Some properties of the core on convex geometries, (in Japanese), "Optimization - Modeling and Algorithms", The Institute of Statistical Mathematics Cooperative Research Report 148 (2002) 28-36.
Y. Okamoto, K. Kashiwabara, M. Nakamura, The affine representation theorem for abstract convex geometries, (in Japanese), Proc. of Ouyou Suugaku Goudou Kenkyuu Shuukai (2002) 43-48.
S. Schönherr, A quadratic programming engine for geometric optimization - Part I: The solver, TR 387 (2002), Department of Computer Science, ETH Zürich.
S. Schönherr, A quadratic programming engine for geometric optimization - Part II: The basis inverse, TR 388 (2002), Department of Computer Science, ETH Zürich.
S. Schönherr, A quadratic programming engine for geometric optimization - Part III: Pricing strategies, TR 389 (2002), Department of Computer Science, ETH Zürich.
B. Speckmann, Cs. D. Tóth, Vertex pi-Guards in Simple Polygons, Abstracts of the 18th European Workshop on Computational Geometry (EuroCG) (2002) 12-15.
Lectures
U. ADAMY
"Call Control in Rings",
Upper Rhine Algorithms Workshop,
ETH Zurich, Switzerland (Oct 18, 2002).
"A Polynomial-Time Algorithm for Call Control in Ring Networks",
Heinz Nixdorf Institut, Paderborn University, Germany
(Dec 4, 2002).
C. AMBÜHL
"Call Control in Rings",
Dagstuhl Seminar on Data Structures,
Schloss Dagstuhl, Germany (Mar 1, 2002).
"Call Control in Rings",
29th International Colloquium on Automata, Languages, and Programming
(ICALP), Malaga, Spain (Jul 10, 2002).
A. BELOW
"Prescribing Properties to Faces of Polytopes",
Symposium Discrete Mathematics 2002,
Dresden, Germany, (Oct 4, 2002).
P. CSORBA
"Note on the Z_2-Index of the Join of Topological Spaces",
2nd General Workshop on Combinatorics, Geometry, and Computation,
Hiddensee, Germany
(Oct 11, 2002).
B. GÄRTNER
"LP-type Problems: Abstrakte Optimierung - Konkrete Anwendung",
Fachbereich Mathematik, Berlin University of Technology, Berlin,
Germany (May 5, 2002).
J. GIESEN
"New Diagrams from Disks in the Plane",
19th International
Symp. on Theoretical Aspects of Computer Science (STACS),
Juan Les Pins, France (Mar 16, 2002).
"Flow diagrams",
INRIA Sophia Antipolis, France (Mar 18, 2002).
"The flow complex: A datastructure for geometric modeling",
MPI Saarbrücken (Jul 15, 2002).
"The Complexity of flow diagrams in the plane", 14th
Canadian Conference on Computational Geometry, Lethbridge(AB), Canada
(Aug 12, 2002).
"Requirements Interdependencies and Stakeholders Preferences",
IEEE Joint Requirements Engineering Conference, Essen, Germany
(Sep 12, 2002).
"The Flow Complex and Applications",
Upper Rhine Algorithms Workshop,
ETH Zurich, Switzerland (Oct 19, 2002).
"The flow complex",
ECG workshop on computational topology,
INRIA Sophia Antipolis, France (Oct 23, 2002).
"The flow complex: A datastructure for geometric modeling",
Working group Topology and Robotics
(M. Farber, E.M. Feichtner, D. Kozlov), Departement Mathematik,
ETH Zurich (Dec 4, 2002)
"Delaunay Triangulations - a guided tour",
Graphics Lunch, Departement Informatik, ETH Zurich
(Dec 11, 2002)
"Delaunay Triangulations - a guided tour" im Freitagskolloquium
Computer-Grafik, Wilhelm Schickard Institut für Informatik,
Universität Tuebingen (Dec 13, 2002)
M. HOFFMANN
"On the Complexity of Block Pushing Puzzles", Dagstuhl
Seminar on Algorithmic Combinatorial Game Theory, Schloss Dagstuhl,
Germany (Feb 19, 2002).
"Alternating Paths through Disjoint Line Segments", 18th European
Workshop on Computational Geometry (EuroCG), Warszawa, Poland (Apr 10,
2002).
"Push-2F is PSPACE-Complete", 14th Canadian Conference on
Computational Geometry, Lethbridge(AB), Canada (Aug 12, 2002).
"Segment Endpoint Visibility Graphs",
Upper Rhine Algorithms Workshop,
ETH Zurich, Switzerland (Oct 19, 2002).
M. JOHN
"Duality in Disk Induced Flows",
2nd Intern. Conf. on Computational Science (ICCS),
Intern. Workshop on Computational Geometry and Applications (CGA),
Amsterdam, The Netherlands (Apr 24, 2002).
"Flow diagrams",
ECG General Workshop,
ETH Zurich, Switzerland (May 23, 2002).
"How to Add Facet Attributes to CGAL's 3D Geometric Triangulations",
CGAL User Workshop,
Barcelona, Spain (Jun 4, 2002).
"Flow Diagrams for Surface Reconstruction and Protein Analysis",
Computer Science Colloquium: Project Presentations, ETH Zurich,
Zurich,
(Jul 1, 2002).
"Surface Reconstruction Based on a Dynamical System",
23rd Annual Conference of the European Association for Computer Graphics
(Eurographics),
Saarbrücken, Germany (Sep 5, 2002).
"The Flow Complex and Applications",
Upper Rhine Algorithms Workshop,
ETH Zurich, Switzerland (Oct 19, 2002).
"Surface Reconstruction Based on the Flow Complex -
Experimental results" (short talk at Demos session),
Workshop on Computational Topology,
INRIA, Sophia Antipolis, France (Oct 23, 2002).
Y. OKAMOTO
"Greedy edge-disjoint paths in complete graphs",
RIMS Workshop: Optimization Theory and Algorithms,
Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japan (Jul 19, 2002)
"Submodularity of some classes of the combinatorial optimization games",
IPSJ SIGAL, Tokyo Institute of Technology, Tokyo, Japan
(Jul 25, 2002)
"Traveling salesman games with the Monge property",
Game Theory and Applications: Satellite Conference of International Congress of Mathematicians 2002, Qingdao, China
(Aug 15, 2002)
"Submodularity of some classes of the combinatorial optimization games",
Short Communication,
International Congress of Mathematicians 2002 (ICM 2002),
Beijing, China
(Aug 21, 2002)
"Matroid Representation of Clique Complexes",
2nd General Workshop on Combinatorics, Geometry, and Computation,
Hiddensee, Germany
(Oct 11, 2002)
"The affine representation theorem for abstract convex geometries",
Ouyou Suugaku Goudou Kenkyuu Shuukai,
Ryukoku University, Ohtsu, Japan
(Dec 20, 2002)
I. SCHURR
"Finding the Sink Takes Some Time",
10th European Symposium on Algorithms,
Rome, Italy
(Sep 19, 2002)
"How structured are Unique Sink Orientations of Cubes?",
2nd General Workshop on Combinatorics, Geometry, and Computation,
Hiddensee, Germany
(Oct 11, 2002)
B. SPECKMANN
"Pseudo-Triangulations and Applications",
Theory Seminar,
Graz University of Technology, Austria
(March 18, 2002)
"Vertex pi-Guards in Simple Polygons",
18th European Workshop on Computational Geometry (EuroCG),
Warszawa, Poland
(Apr 10, 2002)
"Kinetic Maintenance of Context-Sensitive Hierarchical Representations
for Disjo int Simple Polygons", 18th ACM Symposium on Computational
Geometry (SoCG),
Barcelona, Spain
(Jun 6, 2002)
"Kinetic Maintenance of Context-Sensitive Hierarchical Representations
for Disjoint Simple Polygons."
Noon Seminar,
Berlin Free University, Berlin, Germany
(Jun 27, 2002)
"Pseudo-Triangulations: Theory and Applications",
Computer Science Colloquium: Project Presentations, ETH Zurich,
Zurich,
(Jul 1, 2002)
"Convexity minimizes Pseudo-Triangulations", 14th
Canadian Conference on Computational Geometry, Lethbridge(AB), Canada
(Aug 14, 2002)
"Convexity Minimizes Pseudo-Triangulations"
2nd General Workshop on Combinatorics, Geometry, and Computation,
Hiddensee, Germany
(Oct 11, 2002)
"The URAW Logo: An Introduction to Pseudo-Triangulations",
Upper Rhine Algorithms Workshop,
ETH Zurich, Switzerland (Oct 18, 2002)
"Convexity Minimizes Pseudo-Triangulations",
Noon Seminar, Utrecht University, The Netherlands
(Nov 6, 2002)
"The Path of a Pseudo-Triangulation",
DIMACS Workshop on Computational Geometry, Piscataway (NJ),
USA (Nov 14, 2002)
"Kinetic Data Structures for Collision Detection",
DIMACS Workshop on Algorithmic Issues in Modeling Motion, Piscataway
(NJ), USA (Nov 18, 2002)
"Cutting a Country for Smallest Square Fit",
13th International Symposium on Algorithms and Computation (ISAAC),
Vancouver (BC), Canada
(Nov 21, 2002)
"Kinetic Data Structures",
Colloquium ``Combinatorics, Geometry, and Computation'',
Berlin Free University, Germany
(Dec 9, 2002)
"The Path of a Pseudo-Triangulation."
Noon Seminar, Berlin Free University, Germany
(Dec 10, 2002)
M. STOJAKOVIC
"On Restricted Min-Wise Independence of Permutations",
2nd General Workshop on Combinatorics, Geometry, and Computation,
Hiddensee, Germany
(Oct 12, 2002)
T. SZABÓ
"Bounded Size Components - Partitions",
33th Southeastern
International Conf. on Combinatorics, Graph Theory, and
Computing,
Florida Atlantic Univ, Boca Raton, FL, USA
(Mar 7, 2002)
"Unique Sink Orientations of Cubes",
Murray Hill Mathematics Research Colloquium,
Bell Labs (Lucent Technologies),
Murray Hill, NJ, USA
(Apr 11, 2002)
"Unique Sink Orientations of Cube",
Theoretical Computer Science/Discrete Mathematics Seminar,
Institute for Advanced Study,
Princeton, NJ, USA
(Apr 15, 2002)
"Transversals with Bounded Components",
Discrete Mathematics Seminar, Princeton University,
Princeton, NJ, USA
(Apr 18, 2002)
"Two-coloring with bounded monochromatic components",
2nd General Workshop on Combinatorics, Geometry, and Computation,
Hiddensee, Germany
(Oct 11, 2002)
"Unique Sink Orientations of Cubes",
Upper Rhine Algorithms Workshop,
ETH Zurich, Switzerland (Oct 19, 2002)
"Two-Coloring of Graphs with Bounded Monochromatic Components"
3in1 Workshop in Graphs, Krynica, Poland (Nov 22, 2002)
CS. D. TÓTH
"Binary Space Partitions for Line Segments with a Limited Number of
Directions", 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
San Francisco, CA, USA
(Jan 7, 2002)
"Illuminating disjoint line segments",
Monday Colloquium of CGC,
FU Berlin, Germany
(May 13, 2002)
"Connecting Points in the Presence of Obstacles in
the Plane", 14th Canadian Conference on Computational Geometry,
Lethbridge(AB), Canada (Aug 12, 2002)
F. TSCHIRSCHNITZ
"One Line and n Points in 3D",
Upper Rhine Algorithms Workshop,
ETH Zurich, Switzerland (Oct 18, 2002)
U. WAGNER
"On Rectilinear Crossing Numbers of Complete Graphs",
NFS/CBMS Conference on Geometric Graph Theory,
University of North Texas,
Denton, USA
(May 31, 2002)
"On the CLIQUE Problem in Geometric Intersection Graphs",
IXth Prague Combinatorial Workshop, Charles University, Prague,
Czech Republic (Jul 31, 2002)
"On the Rectilinear Crossing Number of Complete Graphs", DIMACS
Workshop on Geometric Graph Theory, DIMACS, Rutgers University, New
Brunswick, USA (Sep 30, 2002)
"Convex Quadrilaterals and k-Sets, Combinatorics Seminar",
University of California, San Diego, USA (Nov 14, 2002)
"On the CLIQUE Problem in Intersection Graphs of Ellipses",
13th International Symposium on Algorithms and Computation (ISAAC),
Vancouver, Canada (Nov 23, 2002)
"Convex Quadrilaterals and k-Sets", ITI/DIMATIA Noon Seminar,
Charles University, Prague (Dec 12, 2002)
E. WELZL
"In Between k-Sets, j-Facets, and i-Faces",
Mostly Discrete - A birthday colloquium for Martin Aigner,
ZIB Berlin, Germany (Jun 7, 2002)
"Randomisierung - Würfeln statt Nachdenken?",
10. Sitzung der Klasse für Ingenieur- und Wirtschaftswissenschaften,
Nordrhein-Westfälische Akademie der Wissenschaften,
Düsseldorf, Germany
(Jun 12, 2002)
"Unique Sink Orientations of Cubes and its Relations to Optimization",
Symposium Discrete Mathematics 2002,
Dresden, Germany (main lecture, Oct 4, 2002)
Courses and Seminars
Approximation: Theory and Algorithms (Pre-Doc Course), J. Blömer, M. Cochand, T. Erlebach, B. Gärtner, A. Steger, P. Widmayer; contact assistant: U. Wagner.
Seminar der Theoretischen Informatik (Noon Seminar), E. Welzl.
Topological Methods in Combinatorics and Geometry (Pre-Doc Course), J. Matousek; contact assistant: T. Szabó.
Pseudorandomness and Algebraic Methods in Combinatorics and Algorithms, T. Szabó.
Randomized Algorithms (Pre-Doc Course), E. Welzl; conctact assistant: Cs. D. Tóth.
Colloquium in Combinatorics, Geometry, and Computation, T. Erlebach, M. Gross, H.-J. Lüthi, J. Nievergelt, B. Schiele, G. Székely, L. Van Gool, R. Wattenhofer, E. Welzl, P. Widmayer.
Geometrie und Algorithmen für Netzgenerierung, J. Giesen.
Seminar der Theoretischen Informatik (Noon Seminar), J. Giesen, B. Speckmann, T. Szabó, E. Welzl.
Theoretische Informatik (Kernfach), E. Welzl; contact assistant: U. Adamy.
Algebra II, E. Welzl; contact assistant: Chr. Ambühl.
Colloquium in Combinatorics, Geometry, and Computation, T. Erlebach, M. Gross, H.-J. Lüthi, J. Nievergelt, B. Schiele, G. Székely, L. Van Gool, R. Wattenhofer, E. Welzl, P. Widmayer.
Organization of Workshops etc.
Extremal Combinatorics, workshop of Forschungsinstitut für Mathematik (FIM), ETH Zurich, Zurich, Switzerland, Jan 28-30, 2002, (M. Burger, M. Cochand, G. Karolyi, J. Nesetril, E. Welzl).
Minisymposium on Theoretical Computer Science, ETH Zurich, Zurich, Switzerland, Feb 27 and Mar 1, 2002, (E. Welzl).
ECG (Effective Computational Geometry of Curves and Surfaces) General Workshop, ETH Zurich, Zurich, Switzerland, May 22-24, 2002, (M. John).
Wege nach oben (auf Polyedern), Working Group of Summer University of the Studienstiftung des Deutschen Volkes, St. Johann im Ahrntal, Italy, Sep 1-14, 2002, (E. Welzl, G. M. Ziegler).
Upper-Rhine-Region Algorithms Workshop (URAW), ETH Zurich, Zurich, Switzerland, October 18-19, 2002. (M. Hoffmann, B. Speckmann, J. Giesen, F. Hefti, E. Welzl).
Dissertations
Christoph Ambühl,
On the List Update Problem
Advisors: B. Gärtner, B. von Stengel; E. Welzl (referee)
/
Co-referees: S. Albers,
Univ. Freiburg, and
B. von Stengel, London School of Economics and Political Science
/
Defense: Feb 8, 2002
Csaba D. Tóth,
Planar Subdivisions
Advisor: E. Welzl
/
Co-referee: G. Rote, Freie Univ. Berlin
/
Defense: May 3, 2002
Sven Schönherr,
Quadratic Programming in Geometric Optimization:
Theory, Implementation, and Applications
Advisors: B. Gärtner; E. Welzl (referee)
/
Co-referees: B. Gärtner, and T. M. Liebling, EPFL Lausanne
/
Defense: Jul 12, 2002
Diploma Theses
Matthias Kaufmann,
Schöning's k-SAT algorithm
Advisor: U. Wagner
/
28. 2. 2002
Papik Meli,
Spectral Voronoi Clustering
Advisor: J. Giesen
/
28. 2. 2002
Michel Stöcklin,
Algorithms and Implementations for Disk Induced Flows
Advisors: J. Giesen, M. John
/
28. 2. 2002
Semester Theses and Pre-Doc Projects
Mattias Andersson,
Rectangle Grid Packing (Pre-Doc mid term)
Advisor: B. Gärtner
/
19. 12. 2002.
Péter Csorba,
Finding Transversals with Bounded Components (Pre-Doc final)
Advisor: T. Szab&ocaute;
/
26. 3. 2002.
Kaspar Fischer,
Implementation of Miniball of Balls
(Pre-Doc final)
Advisor: E. Welzl
/
26. 3. 2002.
Philipp Keller,
On-line Market Research
Advisor: J. Giesen
/
15. 3. 2002.
Yoshio Okamoto,
Unique Sink Orientations and Related Topics
(Pre-Doc final)
Advisor: E. Welzl
/
26. 3. 2002.
Daniel Soll,
Cycles in Smallest-Enclosing-Ball Induced USO (Pre-Doc mid term)
Advisor: B. Gärtner, E. Welzl
/
19.12. 2002.
Milos Stojakovic,
Small Sample Spaces for Permutations
(Pre-Doc final)
Advisor: E. Welzl
/
26. 3. 2002.
Frans Wessendorp,
Optimal Search in Unique Sink Orientations of the 5-Cube
(Pre-Doc final)
Advisor: T. Szab&ocaute;
/
26. 3. 2002.
Miscellaneous
U. ADAMY
Teach. Assistance Theoretische Informatik (Kernfach; SS02).
C. AMBÜHL
Teach. Assistance Algebra II (D-INFK; SS02; chief assistant).
A. BELOW
Teach. Assistance Logik (WS01/02), Algebra II (D-INFK; SS02).
M. HOFFMANN
Teach. Assistance Algebra II (D-INFK; SS02).
M. JOHN
Coordinator ECG (project: Effective Computational Geomtry for Curves and Surfaces).
Teach. Assistance Logik (WS01/02),
Theoretische Informatik (Grundst.; SS02).
I. SCHURR
Teach. Assistance Approximation: Theory and Algorithms (WS02/03)
B. SPECKMANN
Teach. Assistance Logik (WS01/02), Algebra II (D-INFK, SS02).
T. SZABÓ
Teach. Assistance Topological Methods in Combinatorics and Geometry (WS01/02).
CS. D. TÓTH
Teach. Assistance Randomized Algorithms (WS01/02).
F. TSCHIRSCHNITZ
Member of selection committee for Assistenzprofessur für
Theoretische Informatik, Department of Computer Science
Board member of VMI (Mittelbauvertretung D-INFK),
Information Officer (WS01/02, SS02).
Teach. Assistance Informatik I für Mathematiker
(WS01/02; chief assistent), Algebra II (D-INFK; SS02).
Maintenance of the WWW-Site of the Graduate Program
"Combinatorics, Geometry, and Computation" and of
"Theory of Combinatorial Algorithms" group.
U. WAGNER
Coordinator Noon Seminar.
Teach. Assistance Approximation: Theory and Algorithms (WS01/02),
Theoretische Informatik (Kernfach; SS02).
E. WELZL
Speaker (for site Zurich) of Berlin-Zurich Graduate Program `Combinatorics,
Geometry, and Computation'.
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 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002), (Vancouver, Canada, Nov 16-19, 2002)
Member (chair, contact person) of selection committees for
Assistenzprofessur für Theoretische Informatik, Department of Computer Science, (contact person)
Professur für Photonische Kommunikation, Department of Information Technology and Electrical Engineering, (chair)
Professur für Angewandte Mathematik, Mathematics Institute, Zurich University
Assistenzprofessur für Systemoptimierung, Department of Information Technology and Electrical Engineering, (chair)
Professur für Theoretische Informatik, Department of Computer Science
Assistenzprofessur für Systembau, Department of Computer Science
Referee for dissertations of
Christoph Ambühl, On the List Update Problem
Csaba Dávid Tóth, Planar Subdivisions
Sven Schönherr, Quadratic Programming in Geometric Optimization: Theory, Implementation, and Applications
Alexander Below, Complexity of Triangulation (ETH Zurich)
Vladlen Koltun, Arrangements in Four Dimensions and Related Structures (Tel Aviv University, Israel)
Christian Sohler, Property Testing and Geometry (Paderborn University, Germany)
Jörg Rambau, Kombinatorische Methoden in Geometrie, Topologie und Optimierung (Berlin University of Technology, Germany)
Volker Kaibel, Arbeiten zu Polyedern (Berlin University of Technology, Germany)
Member of the EATCS Council (European Association for Theoretical Computer Science).
The project "Study of Arrangements and Randomized Techniques in Discrete and Computational Geometry" (principal investigators: Micha Sharir, Tel Aviv University, Emo Welzl, Freie Univ. Berlin and ETH Zürich, and Kurt Mehlhorn, Max Planck Institute in Computer Science, Saarbrücken) funded 1994-1998 by the German-Israeli Foundation (GIF) for Scientific Research and Development, has been selected by GIF as one of 30 reference projects (out of 690 projects funded since establishment in 1986) for its evaluation in 2002.
Mitglied des Fachausschusses 0.1. Theoretische Informatik der
Gesellschaft für Informatik (GI).
Mitglied der Prüfungsgruppe des Schwerpunktprogramms "Algorithmik grosser und komplexer Netzwerke" der Deutschen
Forschungsgemeinschaft (DFG).
Mitglied der Konferenz der Dozenten der ETH Zürich.
Mitglied des Dozentenausschuss der ETH Zürich.
Mitglied der Studienkommission der ETH Zürich.
Delegierter für Professorenwahlen an der ETH Zürich.