Emo Welzl, List of Publications in Conference Proceedings with Selection Process

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