Emo Welzl, List of Publications / Conference
Proceedings with Selection Process
(``*'' indicates that a complete version has appeared in a journal)
 * On the density of color families, in
``Proc. 8th Annual International Colloquium on Automata,
Languages and Programming (ICALP `81)'', Lecture Notes in Computer
Science 115 (1981) 6872.
 * Chain code picture languages, in ``Proc. 2nd
International Workshop on Graph Grammars and Their Application to
Computer Science'', Lecture Notes in Computer Science 153
(1983) 232244 (with H.A. Maurer & G. Rozenberg).
 * On the number of equalsized semispaces of a
set of points in the pane, in ``Proc. 10th Annual International
Colloquium on Automata, Languages and Programming (ICALP `83)'',
Lecture Notes in Computer Science 154 (1983) 182187 (with
H. Edelsbrunner).
 Two way finite state generators, in ``Proc. International Conference on
Foundation of Computation Theory'', Lecture Notes in Computer
Science 158 (1983) 106114 (with K. Culik II).
 * Boundary NLC grammars, in ``Ninth Colloquium on
Trees in Algebra and Programming'', (B. Courcelle, ed.) Cambridge
University Press (1984) 257270 (with G. Rozenberg).
 Encoding graphs by derivations and implications for the theory of graph
grammars, in ``Proc. 11th Annual International Colloquium on
Automata, Languages and Programming (ICALP '84)'', Lecture
Notes in Computer Science 172 (1984) 503513.
 * Monotone edge sequences in line arrangements
and applications, in ``Proc. 11th International Symposium on
Mathematical Foundations of Computer Science (MFCS `84)'',
Lecture Notes in Computer Science 176 (1984) 265272 (with
H. Edelsbrunner).
 The complexity of cutting paper, in ``Proc. 1st ACM Symposium on
Computational Geometry'' (1985) 316321 (with M. Overmars).
 * String grammars with disconnecting, in
``Proc. 5th International Conference Fundamentals of
Computation Theory (FCT `85)'', Lecture Notes in Computer
Science 199 (1985) 249256, (with K.J. Lange).
 * Epsilonnets and simplex range queries, in
``Proc. 2nd Annual ACM Symposium on Computational Geometry'' (1986)
6171 (with D. Haussler).
 * Testing the necklace condition for shortest
tours and optimal factors in the plane, in ``Proc. 14th Annual
International Colloquium on Automata, Languages and Programming
(ICALP `87)'', Lecture Notes in Computer Science 267
(1987) 364375 (with H. Edelsbrunner & G. Rote).
 Boundary NLC and partition controlled graph grammars, in ``Proc. 3rd
International Workshop on Graph Grammars and Their Application to
Computer Science'', Lecture Notes in Computer Science 291
(1987) 593609.
 Partitioning and geometric embedding of range spaces of finite
VapnikChervonenkis dimension, in ``Proc. 3rd Annual ACM Symposium
on Computational Geometry'' (1987) 331340 (with N. Alon &
D. Haussler).
 * Congruence, similarity, and symmetries of
geometric objects, in ``Proc. 3rd Annual ACM Symposium on
Computational Geometry'' (1987) 308315 (with H. Alt, K. Mehlhorn
& H. Wagener).
 Partition trees for triangle counting and other range searching problems,
in ``Proc. 4th Annual ACM Symposium on Computational Geometry''
(1988) 2333.
 * Implicitly representing arrangements of lines
or segments, in ``Proc. 4th Annual ACM Symposium on Computational
Geometry'' (1988) 5669 (with H. Edelsbrunner,
L.J. Guibas, J. Hershberger, R. Seidel,
M. Sharir & J. Snoeyink).
 New methods for computing visibility graphs, in ``Proc. 4th Annual ACM
Symposium on Computational Geometry'' (1988) 164171, (with
M. Overmars).
 * Combinatorial
complexity bounds for arrangements of curves and surfaces, in
``Proc. 29th Annual IEEE Symposium on Foundations of Computer
Science (FOCS `88)'' (1988) 568579 (with K.L. Clarkson,
H. Edelsbrunner, L.J. Guibas & M. Sharir).
 * Good splitters for counting points in
triangles, in ``Proc. 5th ACM Symposium on Computational Geometry''
(1989) 124130 (with J. Matousek).
 * Polynomial graphcolorings, in ``Proc. 6th
Annual Symposium on Theoretical Aspects of Computer Science
(STACS `89)'', Lecture Notes in Computer Science 349
(1989) 108119 (with W. Gutjahr & G. Woeginger).
 * Approximation of convex figures by pairs of rectangles, in ``Proc. 7th
Annual Symposium on Theoretical Aspects of Computer Science
(STACS `90)'', Lecture Notes in Computer Science 415
(1990) 240249 (with O. Schwarzkopf, U. Fuchs & G. Rote).
 * Weaving patterns of lines and line segments, in
``Proc. SIGAL International Symposium on Algorithms'', Lecture
Notes in Computer Science 450 (1990) 439446 (with J. Pach
& R. Pollack).
 How to net a lot with little: small epsilonnets for disks
and halfspaces, in ``Proc. 6th Annual ACM Symposium on Computational
Geometry'' (1990) 1622 (with J. Matousek & R. Seidel).
 * Quasioptimal upper bounds for simplex range
searching and new zone theorems, in ``Proc. 6th Annual Symposium on
Computational Geometry'' (1990) 2333 (with B. Chazelle &
M. Sharir).
 * On simultaneous inner and outer approximation
of shapes, in ``Proc. 6th Annual Symposium on Computational
Geometry'' (1990) 216224 (with R. Fleischer, K. Mehlhorn, G. Rote
& C. Yap).
 * Euclidean minimum spanning trees and
bichromatic closest pairs, in ``Proc. 6th Annual Symposium on
Computational Geometry'' (1990) 203210 (with P. Agarwal,
H. Edelsbrunner & O. Schwarzkopf).
 Efficient parallel computation of arrangements of hyperplanes in d
dimensions, in ``Proc. 2nd Annual ACM Symposium on Parallel
Algorithms and Architectures (SPAA `90)'' (1990) 290297 (with
T. Hagerup & H. Jung).
 * Drawing graphs in the plane with high
resolution, in ``Proc. 31th IEEE Symposium on Foundations of
Computer Science (FOCS `90)'' (1990) 8695 (with M. Formann,
T. Hagerup, I. Haralambides, M. Kaufmann, F.T. Leighton, A. Simvonis
& G. Woeginger).
 * Fat triangles determine linearly many holes, in
``Proc. 32th IEEE Symposium on Foundations of Computer Science (FOCS
'91)'' (1991) 4958 (with J. Matousek, J. Pach,
S. Sifrony, N. Miller & M. Sharir).
 * Discrepancy and epsilon approximations for bounded VCdimension, in
``Proc. 32th IEEE Symposium on Foundations of Computer Science
(FOCS'91)'' (1991) 424430 (with J. Matousek &
L. Wernisch).
 * Tail estimates for the space complexity of
randomized incremental algorithms, in ``Proc. 3rd ACMSIAM
Symposium on Discrete Algorithms (SODA `92)'' (1992) 8993 (with
K. Mehlhorn & M. Sharir).
 A combinatorial bound for linear programming and related problems, in
``Proc. 9th Annual Symposium on Theoretical Aspects of Computer
Science (STACS `92)'', Lecture Notes in Computer Science 577
(1992) 570579 (with M. Sharir).
 * A subexponential bound for linear programming,
in ``Proc. 8th Annual ACM Symposium on Computational Geometry''
(1992) 18 (with J. Matousek & M. Sharir).
 * Improved bounds for weak epsilonnets for convex sets, in ``Proc. 25th
Annual ACM Symposium on the Theory of Computing'' (1993) 495504
(with B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas &
M. Sharir).
 * Surface reconstruction between simple polygons
via angle criteria, in ``Proc. 1st Annual European Symposium on
Algorithms (ESA `93)'' Lecture Notes in Compter Science 726
(1993) 397408 (with B. Wolfers).
 * Cutting dense point sets in half, in
``Proc. 10th Annual ACM Symposium on Computational Geometry'' (1994)
203210 (with H. Edelsbrunner & P. Valtr).
 * Fast greedy triangulation algorithms, in
``Proc. 10th Annual ACM Symposium on Computational Geometry'' (1994)
211220 (with M. Dickerson, R. S. Drysdale & S. McElfrish).
 * Voronoi diagrams of lines in 3space under polyhedral convex distance
functions, in ``Proc. 6th ACMSIAM Symposium on discrete Algorithms
(SODA `95)'', (1995) 197204 (with L. P. Chew, K. Kedem, M. Sharir
& B. Tagansky).
 * Space filling curves and their use in the design of geometric data
structures, in ``Proc. 2nd Latin American Symposium on Theoretical
Informatics (LATIN `95)'', Lecture Notes in Computer Science
911 (1995) 3648 (with T. Asano, T. Ranjan, T. Roos &
P. Widmayer).
 Rectilinear and polygonal ppiercing and pcenter problems,
in ``Proc. 12th Annual ACM Symposium on Computational Geometry'',
(1996) 122132 (with M. Sharir).
 * The discrete 2center problem, in ``Proc. 13th Annual ACM Symposium on
Computational Geometry'', (1997) 147155 (with P. Agarwal &
M. Sharir).
 Results on ksets and
jfacets via continuous motions, in "Proc. 14th
Annual ACM Symposium on Computational Geometry", (1998) 192199 (with
A. Andrzejak, B. Aronov, S. HarPeled & R. Seidel).

* B. Gärtner, E. Welzl,
Random sampling in geometric optimization: New insights
and applications,
Proc. 16th Ann. ACM Symp. on Computational Geometry
(2000) 9199.

* U. Wagner, E. Welzl,
Originembracing distributions or a continuous analogue of the
Upper Bound Theorem,
Proc. 16th Ann. ACM Symp. on Computational Geometry
(2000) 5056.

* 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) 306315.

* M. Sharir, E. Welzl,
Balanced
lines, halving triangles, and the Generalized Lower Bound Theorem,
Proc. 17th Ann. ACM Symp. on Computational Geometry
(2001) 315318.

T. Szabó, E. Welzl,
Unique
sink orientations of cubes,
Proc. 42nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS)
(2001) 547555.
[pdf]

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) 4253.

* 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) 143156, Kluwer Adacemic Publishers.

* J. Hage, T. Harju, E. Welzl, Euler Graphs,
Trianglefree graphs and bipartite graphs in switching classes,
Proc. 1st International Conference on Graph Transformation (ICGT),
Lecture
Notes in Computer Science
2505 (2002) 148160.

M. Laumanns, L. Thiele, E. Zitzler, E. Welzl, K. Deb,
Running time analysis of multiobjective evolutionary algorithms
on a simple discrete optimization problem,
Parallel Problem Solving From Nature,
Lecture
Notes in Computer Science
2439 (2002) 4453.

* M. Sharir, E. Welzl,
Pointline incidences in space,
Proc. 18th Ann. ACM Symp. on Computational Geometry
(2002) 107115.

U. Adamy, Th. Erlebach, D. Mitsche, I. Schurr, B. Speckmann, E. Welzl,
Offline admission control for advance reservations in star networks,
Proc. 2nd Workshop on Approximation and Online Algorithms (WAOA04),
Lecture Notes in Computer Science 3351 (2005) 211224.

* P.K. Agarwal, M. Sharir, E. Welzl,
Algorithms for center and Tverberg points,
Proc. 20th Annual ACM Symposium on Computational Geometry (SoCG)
(2004) 6167.

A. Fiat, M. Levy,
J. Matoušek, E. Mossel, J. Pach, M. Sharir,
S. Smorodinsky, U. Wagner, E. Welzl,
Online conflictfree coloring for intervals,
Proc. 16th Annual ACMSIAM Symposium on Discrete Algorithms (SODA)
(2005) 545554.

F. Kuhn, P. von Rickenbach, R. Wattenhofer, E. Welzl, A. Zollinger,
Interference in Cellular Networks:
The Minimum Membership Set Cover Problem,
Proc. 11th Annual International Computing and Combinatorics
Conference (COCOON),
Lecture Notes in Computer Science 3595
(2005) 188198.

* M. Sharir, E. Welzl,
On the number of crossingfree matchings, (cycles, and partitions),
Proc. 17th Annual ACMSIAM Symposium on Discrete Algorithms (SODA)
(2006) 860869.
[pdf]

M. Sharir, E. Welzl,
Random
triangulations of planar point sets,
Proc. 22nd Annual ACM Symposium on Computational Geometry (SoCG)
(2006) 273281.
[pdf]

* S. Gandhi, S. Suri, E. Welzl,
Catching elephants with mice: sparse sampling for monitoring sensor networks,
Proc. 5th International ACM Conference on Embedded Networked Sensor Systems (SenSys)
(2007) 261274.
[pdf]

A. Razen, J. Snoeyink, E. Welzl,
Number of CrossingFree Geometric Graphs vs. Triangulations,
Electronic Notes in Discrete Mathematics 31 (2008) 195200, and Proc. of the International Conference on Topological & Geometric Graph Theory (TGGT) (2008) 188193.
[pdf]

O. Goussevskaia, R. Wattenhofer, M. M. Halldórsson, E. Welzl,
Capacity of Arbitrary Wireless Networks,
Proc. 28th IEEE International Conference on Computer Communications (Infocom)
(2009) 18721880.

M. Sharir, A. Sheffer, E. Welzl,
On Degrees in Random Triangulations of Point Sets,
Proc. 26th Annual Symposium on Computational Geometry (SoCG)
(2010) 297306.