Emo Welzl, List of Publications in Conference Proceedings with Selection Process
("*"/nonbold indicates that a complete version has appeared in a journal)

*
On the density of color families,
Proc. 8th Annual International Colloquium on Automata, Languages and Programming (ICALP`81),
LNCS 115 (1981) 6872.

*
Chain code picture languages,
Proc. 2nd International Workshop on Graph Grammars and Their Application to Computer Science (WG'82),
LNCS 153 (1983) 232244
(with H.A. Maurer & G. Rozenberg).

*
On the number of equalsized semispaces of a set of points in the plane,
Proc. 10th Annual International Colloquium on Automata, Languages and Programming (ICALP`83),
LNCS 154 (1983) 182187
(with H. Edelsbrunner).

Two way finite state generators,
Proc. International Conference on Foundation of Computation Theory (FCT`83),
LNCS 158 (1983) 106114 (with K. Culik II).

*
Boundary NLC grammars,
Proc. 9th Colloquium on Trees in Algebra and Programming (CAAP`84),
(B. Courcelle, Ed.), Cambridge University Press
(1984) 257270
(with G. Rozenberg).

Encoding graphs by derivations and implications for the theory of graph grammars,
Proc. 11th Annual International Colloquium on Automata, Languages and Programming (ICALP'84),
LNCS 172 (1984) 503513.

*
Monotone edge sequences in line arrangements and applications,
Proc. 11th International Symposium on Mathematical Foundations of Computer Science (MFCS`84),
LNCS 176 (1984) 265272
(with H. Edelsbrunner).

The complexity of cutting paper,
Proc. 1st ACM Symposium on Computational Geometry (SoCG`85)
(1985) 316321
(with M. Overmars).

*
String grammars with disconnecting,
Proc. 5th International Conference Fundamentals of Computation Theory (FCT`85),
LNCS 199 (1985) 249256
(with K.J. Lange).

*
εnets and simplex range queries,
Proc. 2nd Annual ACM Symposium on Computational Geometry (SoCG`86)
(1986) 6171
(with D. Haussler).

*
Testing the necklace condition for shortest tours and optimal factors in the plane,
Proc. 14th Annual International Colloquium on Automata, Languages and Programming (ICALP`87),
LNCS 267 (1987) 364375
(with H. Edelsbrunner & G. Rote).

Boundary NLC and partition controlled graph grammars,
Proc. 3rd International Workshop on Graph Grammars and Their Application to Computer Science,
LNCS 291 (1987) 593609.

Partitioning and geometric embedding of range spaces of finite VapnikChervonenkis dimension,
Proc. 3rd Annual ACM Symposium on Computational Geometry (SoCG`87)
(1987) 331340
(with N. Alon & D. Haussler).

*
Congruence, similarity, and symmetries of geometric objects,
Proc. 3rd Annual ACM Symposium on Computational Geometry (SoCG`87)
(1987) 308315
(with H. Alt, K. Mehlhorn & H. Wagener).

Partition trees for triangle counting and other range searching problems,
Proc. 4th Annual ACM Symposium on Computational Geometry (SoCG`88)
(1988) 2333.

*
Implicitly representing arrangements of lines or segments,
Proc. 4th Annual ACM Symposium on Computational Geometry (SoCG`88)
(1988) 5669
(with H. Edelsbrunner, L.J. Guibas, J. Hershberger, R. Seidel, M. Sharir & J. Snoeyink).

New methods for computing visibility graphs,
Proc. 4th Annual ACM Symposium on Computational Geometry (SoCG`88)
(1988) 164171,
(with M. Overmars).

*
Combinatorial complexity bounds for arrangements of curves and
surfaces,
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,
Proc. 5th ACM Symposium on Computational Geometry (SoCG`89),
(1989) 124130
(with J. Matoušek).

*
Polynomial graphcolorings,
Proc. 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS`89),
LNCS 349 (1989) 108119
(with W. Gutjahr & G. Woeginger).

*
Approximation of convex figures by pairs of rectangles,
Proc. 7th Annual Symposium on Theoretical Aspects of Computer Science (STACS`90),
LNCS 415 (1990) 240249
(with O. Schwarzkopf, U. Fuchs & G. Rote).

*
Weaving patterns of lines and line segments,
Proc. SIGAL International Symposium on Algorithms,
LNCS 450 (1990) 439446
(with J. Pach & R. Pollack).

How to net a lot with little: small εnets for disks and halfspaces,
Proc. 6th Annual ACM Symposium on Computational Geometry (SoCG`90)
(1990) 1622
(with J. Matoušek & R. Seidel).

*
Quasioptimal upper bounds for simplex range searching and new zone theorems,
Proc. 6th Annual Symposium on Computational Geometry (SoCG`90)
(1990) 2333
(with B. Chazelle & M. Sharir).

*
On simultaneous inner and outer approximation of shapes,
Proc. 6th Annual Symposium on Computational Geometry (SoCG`90)
(1990) 216224
(with R. Fleischer, K. Mehlhorn, G. Rote & C. Yap).

*
Euclidean minimum spanning trees and bichromatic closest pairs,
Proc. 6th Annual Symposium on Computational Geometry (SoCG`90)
(1990) 203210
(with P. Agarwal, H. Edelsbrunner & O. Schwarzkopf).

Efficient parallel computation of arrangements of hyperplanes in d dimensions,
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,
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,
Proc. 32th IEEE Symposium on Foundations of Computer Science (FOCS'91)
(1991) 4958
(with J. Matoušek, J. Pach, S. Sifrony, N. Miller & M. Sharir).

*
Discrepancy and epsilonapproximations for bounded VCdimension,
Proc. 32th IEEE Symposium on Foundations of Computer Science (FOCS'91)
(1991) 424430
(with J. Matoušek & L. Wernisch).

*
Tail estimates for the space complexity of randomized incremental algorithms,
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,
Proc. 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS`92),
LNCS 577
(1992) 570579
(with M. Sharir).

*
A subexponential bound for linear programming,
Proc. 8th Annual ACM Symposium on Computational Geometry (SoCG`92)
(1992) 18
(with J. Matoušek & M. Sharir).

*
Improved bounds for weak εnets for convex sets,
Proc. 25th Annual ACM Symposium on the Theory of Computing (STOC`93)
(1993) 495504
(with B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas & M. Sharir).

*
Surface reconstruction between simple polygons via angle criteria,
Proc. 1st Annual European Symposium on Algorithms (ESA`93),
LNCS 726 (1993) 397408
(with B. Wolfers).

*
Cutting dense point sets in half,
Proc. 10th Annual ACM Symposium on Computational Geometry (SoCG`94)
(1994) 203210
(with H. Edelsbrunner & P. Valtr).

*
Fast greedy triangulation algorithms,
Proc. 10th Annual ACM Symposium on Computational Geometry (SoCG`94)
(1994) 211220
(with M. Dickerson, R. S. Drysdale & S. McElfrish).

*
Voronoi diagrams of lines in 3space under polyhedral convex distance functions,
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,
Proc. 2nd Latin American Symposium on Theoretical Informatics (LATIN`95),
LNCS 911 (1995) 3648
(with T. Asano, T. Ranjan, T. Roos & P. Widmayer).

Rectilinear and polygonal ppiercing and pcenter problems,
Proc. 12th Annual ACM Symposium on Computational Geometry (SoCG`96)
(1996) 122132
(with M. Sharir).

*
The discrete 2center problem,
Proc. 13th Annual ACM Symposium on Computational Geometry (SoCG`97)
(1997) 147155
(with P. Agarwal & M. Sharir).

Results on ksets and jfacets via continuous motions,
Proc. 14th Annual ACM Symposium on Computational Geometry (SoCG`98)
(1998) 192199
(with A. Andrzejak, B. Aronov, S. HarPeled & R. Seidel).
[pdf]

*
Random sampling in geometric optimization: New insights and applications,
Proc. 16th Annual ACM Symppsoim on Computational Geometry (SoCG`98)
(2000) 9199
(with B. Gärtner).

*
Originembracing distributions or a continuous analogue of the Upper Bound Theorem,
Proc. 16th Annual ACM Symposium on Computational Geometry (SoCG`00)
(2000) 5056
(with U. Wagner).

*
One line and n points
Proc. 33rd Annual ACM Symposium on the Theory of Computing (STOC`01)
(2001) 306315
(with B. Gärtner, J. Solymosi, F. Tschirschnitz & P. Valtr).
[ps]

*
Balanced lines, halving triangles, and the Generalized Lower Bound Theorem,
Proc. 17th Annual ACM Symposium on Computational Geometry (SoCG`01)
(2001) 315318
(with M. Sharir).
[ps]

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

Translating a planar object to maximize point containment,
Proc. 10th European Symposium on Algorithms (ESA`02),
LNCS 2461 (2002) 4253
(with P.K. Agarwal, T. Hagerup, R. Ray, M. Sharir & M. Smid).

*
Algorithmic complexity of protein identification: Searching in weighted strings,
Proc. of 2nd IFIP Conference on Theoretical Computer Science,
(2002) 143156,
(with M. Cieliebak, Th. Erlebach, Zs. Lipták & J. Stoye).

*
Euler graphs, trianglefree graphs and bipartite graphs in switching classes,
Proc. 1st International Conference on Graph Transformation (ICGT`02),
LNCS 2505 (2002) 148160
(with J. Hage & T. Harju).

Running time analysis of multiobjective evolutionary algorithms on a simple discrete optimization problem,
Proc. 7th International Conference on Parallel Problem Solving From Nature (PPSN`02),
LNCS 2439 (2002) 4453
(with M. Laumanns, L. Thiele, E. Zitzler & K. Deb).

*
Pointline incidences in space,
Proc. 18th Ann. ACM Symp. on Computational Geometry (SoCG`02)
(2002) 107115
(with M. Sharir).

Offline admission control for advance reservations in star networks,
Proc. 2nd Workshop on Approximation and Online Algorithms (WAOA`04),
LNCS 3351 (2005) 211224
(with U. Adamy, Th. Erlebach, D. Mitsche, I. Schurr & B. Speckmann).

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

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

Interference in cellular networks: The minimum membership set cover problem,
Proc. 11th Annual International Computing and Combinatorics Conference (COCOON`05),
LNCS 3595 (2005) 188198
(with F. Kuhn, P. von Rickenbach, R. Wattenhofer &A. Zollinger,).

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

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

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

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`08)
(2008) 188193
(with A. Razen & J. Snoeyink).
[pdf]

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

*
On Degrees in Random Triangulations of Point Sets,
Proc. 26th Annual Symposium on Computational Geometry (SoCG`10)
(2010) 297306
(with M. Sharir & A. Sheffer).
[pdf]

Counting plane graphs: Flippability and its applications,
Proc. 12th Algorithms and Data Structures Symposium (WADS`11),
LNCS 6844 (2011) 524535
(with M. Hoffmann, M. Sharir, A. Sheffer & Cs. D. Toth).
[arXiv]

*
On the number of upward planar orientations of maximal planar graphs,
Proc. 23rd Int. Symp. on Algorithms and Computation (ISAAC`12),
LNCS 7676 (2012) 413422
(with F. Frati & J. Gudmundsson).

*
Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn's Technique,
Proc. 26th Annual Symposium on Computational Geometry (SoCG`12)
(2012) 189198
(with M. Sharir & A. Sheffer).

*
Order on order types,
Proc. 31st International Symposium on Computational Geometry (SoCG`15)
(2015) 285299
(with A. Pilz).

*
Solving and sampling with many solutions: Satisfiability and other hard problems,
12th International Symposium on Parameterized and Exact Computation (IPEC`17)
LIPIcs 89 (2017) 11:111:12
(with J. Cardinal & J. Nummenpalo).
[arXiv]

*
From crossingfree graphs on wheel sets to embracing simplices and polytopes with few vertices,
Proc. 33rd International Symposium on Computational Geometry (SoCG`17),
LIPIcs 77 (2017) 54:154:16
(with A. Pilz & M. Wettstein,).
[pdf]

*
Lower bounds for searching robots, some faulty,
Proc. 37th ACM Symposium on Principles of Distributed Computing (PODC`18)
(2018) 447453
(with A. Kupavskii).
[arXiv]

*
Minimal representations of order types by geometric graphs,
Proc. 7th International Symposium on Graph Drawing & Network Visualization (GD`19),
LNCS 11904 (2018) 101113
(with O. Aichholzer, M. Balko, M. Hoffmann, J. KynÄ¨l, W. Mulzer, I. Parada, A. Pilz, M. Scheucher, P. Valtr & B. Vogtenhuber).

An Optimal Decentralized (Δ+1)Coloring Algorithm,
Proc. 28th Annual European Symposium on Algorithms (ESA`20),
LIPIcs 173 (2020) 17:117:12
(with D. Bertschinger, J. Lengler, A. Martinsson, R. Meier, A. Steger & M. Trujić).

*
Convex hulls of random order types,
Proc. 36th International Symposium on Computational Geometry (SoCG`20),
LIPIcs 164 (2020) 67:167:16
(with X. Goaoc).

Clustering under perturbation stability in nearlinear time,
Proc. 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS`20),
LIPIcs 182 (2020) 8:18:16
(with E. Taylor, P. K. Agarwal & K. Munagala).

*
Connectivity of triangulation flip graphs in the plane (Part I: Edge flips),
Proc. 31st Annual ACMSIAM Symposium on Discrete Algorithms (SODA`20)
(2020) 28232841
(with U. Wagner).

*
Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips),
Proc. 36th International Symposium on Computational Geometry (SoCG`20),
LIPIcs 164 (2020) 67:167:16
(with U. Wagner).