| Research My research areas
are discrete and computational geometry, i.e., I study geometric
problems of a combinatorial or computational nature. A good deal of my
research has been motivated by the k-set or halving
hyperplane problem and its connections to crossing numbers of
graphs, polytope theory, and the combinatorics of linear
programming. Here is a survey
artice on the topic.
More recently, I have become interested in the interplay between topology,
combinatorics, and computation, specifically, in embeddability
problems and topological obstructions. Typical questions include: What is the
computational complexity of deciding whether a given simplicial complex embeds
into Euclidean space of a given dimension? And what consequences does embeddability
have for the combinatorics of the complex? The simplest instance of this problem,
embedding graphs in the plane, is classical and well-understood, but the situation
in higher dimensions is far from being understood.
I have also worked on questions concerning geometric transversals
(weak epsilon-nets), manifold learning and reconstruction from points
samples, intersection graphs. For more details, you are invited to explore
my list of publications below.
My research is supported by the Swiss National Science Foundation
(SNF Projects 200021-116741, 20020-125027, and 200021-125309).
|
| Teaching Courses and seminars I have taught at ETH Zurich since Spring 2006, in
reverse chronological order. The links refer to the course webpages,
which contain more information
Spring 2009
Fall 2008
Spring 2008
Fall 2007
Mittagsseminar
(with Bernd Gärtner, Michael Hoffmann, Angelika Steger,
Tibor Szabó, and Emo Welzl)
Reading Seminar
(with Tibor Szabó and Emo Welzl)
Spring 2007
Fall 2006
Spring 2006
|
|
Publications
-
Uli Wagner and Emo Welzl
A Continuous Analogue of the Upper Bound Theorem
(ps.gz,
pdf)
Discrete & Computational Geometry 26 (2) (2001), pp. 205-219.
An extended abstract appeared in Proc. 16th Annual ACM
Symposium on Computational Geometry (SoCG), 2000, pp. 50-56.
-
Uli Wagner
On the Number of Corner Cuts
(ps.gz,
pdf)
Advances in Applied Mathematics, 29 (2002), pp. 152-161.
-
Christoph Ambühl
and Uli Wagner
The Clique Problem in Intersection Graphs of Ellipses and Triangles
(ps.gz,
pdf)
Theory of Computing Systems 38
(2), 2005, 279-292.
An extended abstract
appeared Proc. 13th Annual International
Symposium on Algorithms and Computation (ISAAC), 2002,
pp. 489-500.
-
Uli Wagner
On the Rectilinear Crossing Number of Complete Graphs
(ps.gz,
pdf)
Proc. 14th Annual Symposium on Discrete Algorithms
(SODA), 2003, pp. 583-588.
-
Jiri Matousek and Uli Wagner
New Constructions of Weak Epsilon-Net
(ps.gz,
pdf)
Discrete & Computational Geometry 32 (2) (2004), pp. 195-206.
An extended abstract appeared in Proc. 19th Annual ACM
Symposium on Computational Geometry (SoCG), 2003, pp. 129-135.
-
Joachim Giesen and Uli
Wagner
Shape Dimension and Intrinsic Metric From Samples of Manifolds with High
Co-Dimension (ps.gz, pdf)
Discrete & Computational Geometry 32 (2) (2004), pp. 245-267.
An extended abstract appeared in Proc. 19th Annual ACM
Symposium on Computational Geometry (SoCG), 2003, pp. 329-337.
-
László Lovász, Katalin
Vesztergombi, Uli Wagner, and Emo Welzl
Convex Quadrilaterals and k-Sets
(ps.gz, pdf)
Towards a Theory of Geometric
Graphs (János Pach, ed.), Contemporary Mathematics 342,
American Mathematical Society, Providence, 2004, pp. 139-148.
-
Jiri Matousek,
Micha
Sharir, Shakhar
Smorodinsky, and Uli Wagner
k-Sets in 4 dimensions
(pdf)
Discrete & Computational Geometry
35(2) (2006), pp. 177-191.
-
Jorgen
Bang-Jensen, Bruce
Reed, Mathias
Schacht, Robert Sámal, Bjarne Toft, and Uli Wagner
On six problems posed by Jarik Nesetril
(ps.gz,
pdf)
Topics in Discrete Mathematics (Martin Klazar, Jan Kratochvil, Martin Loebl, Jiri Matousek,
Robin Thomas, eds.),
Algorithms and Combinatorics 26 (2006), pp. 613--627.
-
Ke
Chen, Amos
Fiat, Haim Kaplan,
Meital Levy, Jiri
Matousek, Elchanan
Mossel, János
Pach, Micha Sharir,
Shakhar Smorodinsky, Uli Wagner, and
Emo Welzl
Online conflict-free coloring for intervals
(pdf)
Siam Journal of Computing 36(5)
(2006), pp. 1342--1359. An extended abstract appeared in
Proc. 16th Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), 2005.
-
Uli Wagner.
On a Geometric Generalization of the Upper Bound Theorem
(pdf)
Proc. 47th Annual Symposium on the Foundations of Computer Science (FOCS),
2006, pp. 635-645.
-
Uli Wagner.
k-Sets and k-Facets
(pdf)
Discrete and Computational Geometry - 20 Years Later
(Eli Goodman, János Pach, and Ricky Pollack, eds.), Contemporary Mathematics 453,
American Mathematical Society, to appear.
-
Kevin Buchin,
Andreas Razen,
Takeaki Uno,
and Uli Wagner.
Transforming Spanning Trees
(pdf)
Computational Geometry: Theory and Appications, to appear.
-
Eran Nevo and
Uli Wagner.
On the Embeddability of Skeleta Spheres
(pdf)
Israel Journal of Mathematics, to appear.
-
Jiri Matousek, Martin Tancer, and
Uli Wagner.
Hardness of Embedding Simplicial Complexes in Rd
(pdf)
Journal of the European Mathematical Society, to appear.
|