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) 68-72.
-
*
Chain code picture languages,
Proc. 2nd International Workshop on Graph Grammars and Their Application to Computer Science (WG'82),
LNCS 153 (1983) 232-244
(with H.A. Maurer & G. Rozenberg).
-
*
On the number of equal-sized semispaces of a set of points in the plane,
Proc. 10th Annual International Colloquium on Automata, Languages and Programming (ICALP`83),
LNCS 154 (1983) 182-187
(with H. Edelsbrunner).
-
Two way finite state generators,
Proc. International Conference on Foundation of Computation Theory (FCT`83),
LNCS 158 (1983) 106-114 (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) 257-270
(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) 503-513.
-
*
Monotone edge sequences in line arrangements and applications,
Proc. 11th International Symposium on Mathematical Foundations of Computer Science (MFCS`84),
LNCS 176 (1984) 265-272
(with H. Edelsbrunner).
-
The complexity of cutting paper,
Proc. 1st ACM Symposium on Computational Geometry (SoCG`85)
(1985) 316-321
(with M. Overmars).
-
*
String grammars with disconnecting,
Proc. 5th International Conference Fundamentals of Computation Theory (FCT`85),
LNCS 199 (1985) 249-256
(with K.-J. Lange).
-
*
ε-nets and simplex range queries,
Proc. 2nd Annual ACM Symposium on Computational Geometry (SoCG`86)
(1986) 61-71
(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) 364-375
(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) 593-609.
-
Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension,
Proc. 3rd Annual ACM Symposium on Computational Geometry (SoCG`87)
(1987) 331-340
(with N. Alon & D. Haussler).
-
*
Congruence, similarity, and symmetries of geometric objects,
Proc. 3rd Annual ACM Symposium on Computational Geometry (SoCG`87)
(1987) 308-315
(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) 23-33.
-
*
Implicitly representing arrangements of lines or segments,
Proc. 4th Annual ACM Symposium on Computational Geometry (SoCG`88)
(1988) 56-69
(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) 164-171,
(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) 568-579
(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) 124-130
(with J. Matoušek).
-
*
Polynomial graph-colorings,
Proc. 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS`89),
LNCS 349 (1989) 108-119
(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) 240-249
(with O. Schwarzkopf, U. Fuchs & G. Rote).
-
*
Weaving patterns of lines and line segments,
Proc. SIGAL International Symposium on Algorithms,
LNCS 450 (1990) 439-446
(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) 16-22
(with J. Matoušek & R. Seidel).
-
*
Quasi-optimal upper bounds for simplex range searching and new zone theorems,
Proc. 6th Annual Symposium on Computational Geometry (SoCG`90)
(1990) 23-33
(with B. Chazelle & M. Sharir).
-
*
On simultaneous inner and outer approximation of shapes,
Proc. 6th Annual Symposium on Computational Geometry (SoCG`90)
(1990) 216-224
(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) 203-210
(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) 290-297
(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) 86-95
(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) 49-58
(with J. Matoušek, J. Pach, S. Sifrony, N. Miller & M. Sharir).
-
*
Discrepancy and epsilon-approximations for bounded VC-dimension,
Proc. 32th IEEE Symposium on Foundations of Computer Science (FOCS'91)
(1991) 424-430
(with J. Matoušek & L. Wernisch).
-
*
Tail estimates for the space complexity of randomized incremental algorithms,
Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms (SODA`92)
(1992) 89-93
(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) 570-579
(with M. Sharir).
-
*
A subexponential bound for linear programming,
Proc. 8th Annual ACM Symposium on Computational Geometry (SoCG`92)
(1992) 1-8
(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) 495-504
(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) 397-408
(with B. Wolfers).
-
*
Cutting dense point sets in half,
Proc. 10th Annual ACM Symposium on Computational Geometry (SoCG`94)
(1994) 203-210
(with H. Edelsbrunner & P. Valtr).
-
*
Fast greedy triangulation algorithms,
Proc. 10th Annual ACM Symposium on Computational Geometry (SoCG`94)
(1994) 211-220
(with M. Dickerson, R. S. Drysdale & S. McElfrish).
-
*
Voronoi diagrams of lines in 3-space under polyhedral convex distance functions,
Proc. 6th ACM-SIAM Symposium on discrete Algorithms (SODA`95)
(1995) 197-204
(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) 36-48
(with T. Asano, T. Ranjan, T. Roos & P. Widmayer).
-
Rectilinear and polygonal p-piercing and p-center problems,
Proc. 12th Annual ACM Symposium on Computational Geometry (SoCG`96)
(1996) 122-132
(with M. Sharir).
-
*
The discrete 2-center problem,
Proc. 13th Annual ACM Symposium on Computational Geometry (SoCG`97)
(1997) 147-155
(with P. Agarwal & M. Sharir).
-
Results on k-sets and j-facets via continuous motions,
Proc. 14th Annual ACM Symposium on Computational Geometry (SoCG`98)
(1998) 192-199
(with A. Andrzejak, B. Aronov, S. Har-Peled & R. Seidel).
[pdf]
-
*
Random sampling in geometric optimization: New insights and applications,
Proc. 16th Annual ACM Symppsoim on Computational Geometry (SoCG`98)
(2000) 91-99
(with B. Gärtner).
-
*
Origin-embracing distributions or a continuous analogue of the Upper Bound Theorem,
Proc. 16th Annual ACM Symposium on Computational Geometry (SoCG`00)
(2000) 50-56
(with U. Wagner).
-
*
One line and n points
Proc. 33rd Annual ACM Symposium on the Theory of Computing (STOC`01)
(2001) 306-315
(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) 315-318
(with M. Sharir).
[ps]
-
Unique sink orientations of cubes,
Proc. 42nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS`01)
(2001) 547-555
(with T. Szabó).
[pdf]
-
Translating a planar object to maximize point containment,
Proc. 10th European Symposium on Algorithms (ESA`02),
LNCS 2461 (2002) 42-53
(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) 143-156,
(with M. Cieliebak, Th. Erlebach, Zs. Lipták & J. Stoye).
-
*
Euler graphs, triangle-free graphs and bipartite graphs in switching classes,
Proc. 1st International Conference on Graph Transformation (ICGT`02),
LNCS 2505 (2002) 148-160
(with J. Hage & T. Harju).
-
Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem,
Proc. 7th International Conference on Parallel Problem Solving From Nature (PPSN`02),
LNCS 2439 (2002) 44-53
(with M. Laumanns, L. Thiele, E. Zitzler & K. Deb).
-
*
Point-line incidences in space,
Proc. 18th Ann. ACM Symp. on Computational Geometry (SoCG`02)
(2002) 107-115
(with M. Sharir).
-
Off-line admission control for advance reservations in star networks,
Proc. 2nd Workshop on Approximation and Online Algorithms (WAOA`04),
LNCS 3351 (2005) 211-224
(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) 61-67
(with P.K. Agarwal & M. Sharir).
-
Online conflict-free coloring for intervals,
Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA`05)
(2005) 545-554
(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) 188-198
(with F. Kuhn, P. von Rickenbach, R. Wattenhofer &A. Zollinger,).
-
*
On the number of crossing-free matchings, (cycles, and partitions),
Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA`06)
(2006) 860-869
(with M. Sharir).
[pdf]
-
Random triangulations of planar point sets,
Proc. 22nd Annual ACM Symposium on Computational Geometry (SoCG`06)
(2006) 273-281
(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) 261-274
(with S. Gandhi & S. Suri).
[pdf]
-
Number of Crossing-Free Geometric Graphs vs. Triangulations,
Electronic Notes in Discrete Mathematics
31 (2008) 195-200,
and
Proc. of the International Conference on Topological & Geometric Graph Theory (TGGT`08)
(2008) 188-193
(with A. Razen & J. Snoeyink).
[pdf]
-
Capacity of Arbitrary Wireless Networks,
Proc. 28th IEEE International Conference on Computer Communications (Infocom`09)
(2009) 1872-1880
(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) 297-306
(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) 524-535
(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) 413-422
(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) 189-198
(with M. Sharir & A. Sheffer).
-
*
Order on order types,
Proc. 31st International Symposium on Computational Geometry (SoCG`15)
(2015) 285-299
(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:1-11:12
(with J. Cardinal & J. Nummenpalo).
[arXiv]
-
*
From crossing-free 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:1-54: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) 447-453
(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) 101-113
(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:1-17: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:1-67:16
(with X. Goaoc).
-
Clustering under perturbation stability in near-linear time,
Proc. 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS`20),
LIPIcs 182 (2020) 8:1-8:16
(with E. Taylor, P. K. Agarwal & K. Munagala).
-
*
Connectivity of triangulation flip graphs in the plane (Part I: Edge flips),
Proc. 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA`20)
(2020) 2823-2841
(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:1-67:16
(with U. Wagner).