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

(``*'' indicates that a complete version has appeared in a journal)
  1. * 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) 68-72.
  2. * 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) 232-244 (with H.A. Maurer & G. Rozenberg).
  3. * On the number of equal-sized 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) 182-187 (with H. Edelsbrunner).
  4. Two way finite state generators, in ``Proc. International Conference on Foundation of Computation Theory'', Lecture Notes in Computer Science 158 (1983) 106-114 (with K. Culik II).
  5. * Boundary NLC grammars, in ``Ninth Colloquium on Trees in Algebra and Programming'', (B. Courcelle, ed.) Cambridge University Press (1984) 257-270 (with G. Rozenberg).
  6. 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) 503-513.
  7. * 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) 265-272 (with H. Edelsbrunner).
  8. The complexity of cutting paper, in ``Proc. 1st ACM Symposium on Computational Geometry'' (1985) 316-321 (with M. Overmars).
  9. * String grammars with disconnecting, in ``Proc. 5th International Conference Fundamentals of Computation Theory (FCT `85)'', Lecture Notes in Computer Science 199 (1985) 249-256, (with K.-J. Lange).
  10. * Epsilon-nets and simplex range queries, in ``Proc. 2nd Annual ACM Symposium on Computational Geometry'' (1986) 61-71 (with D. Haussler).
  11. * 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) 364-375 (with H. Edelsbrunner & G. Rote).
  12. 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) 593-609.
  13. Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension, in ``Proc. 3rd Annual ACM Symposium on Computational Geometry'' (1987) 331-340 (with N. Alon & D. Haussler).
  14. * Congruence, similarity, and symmetries of geometric objects, in ``Proc. 3rd Annual ACM Symposium on Computational Geometry'' (1987) 308-315 (with H. Alt, K. Mehlhorn & H. Wagener).
  15. Partition trees for triangle counting and other range searching problems, in ``Proc. 4th Annual ACM Symposium on Computational Geometry'' (1988) 23-33.
  16. * Implicitly representing arrangements of lines or segments, in ``Proc. 4th Annual ACM Symposium on Computational Geometry'' (1988) 56-69 (with H. Edelsbrunner, L.J. Guibas, J. Hershberger, R. Seidel, M. Sharir & J. Snoeyink).
  17. New methods for computing visibility graphs, in ``Proc. 4th Annual ACM Symposium on Computational Geometry'' (1988) 164-171, (with M. Overmars).
  18. * Combinatorial complexity bounds for arrangements of curves and surfaces, in ``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).
  19. * Good splitters for counting points in triangles, in ``Proc. 5th ACM Symposium on Computational Geometry'' (1989) 124-130 (with J. Matousek).
  20. * Polynomial graph-colorings, in ``Proc. 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS `89)'', Lecture Notes in Computer Science 349 (1989) 108-119 (with W. Gutjahr & G. Woeginger).
  21. * 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) 240-249 (with O. Schwarzkopf, U. Fuchs & G. Rote).
  22. * Weaving patterns of lines and line segments, in ``Proc. SIGAL International Symposium on Algorithms'', Lecture Notes in Computer Science 450 (1990) 439-446 (with J. Pach & R. Pollack).
  23. How to net a lot with little: small epsilon-nets for disks and halfspaces, in ``Proc. 6th Annual ACM Symposium on Computational Geometry'' (1990) 16-22 (with J. Matousek & R. Seidel).
  24. * Quasi-optimal upper bounds for simplex range searching and new zone theorems, in ``Proc. 6th Annual Symposium on Computational Geometry'' (1990) 23-33 (with B. Chazelle & M. Sharir).
  25. * On simultaneous inner and outer approximation of shapes, in ``Proc. 6th Annual Symposium on Computational Geometry'' (1990) 216-224 (with R. Fleischer, K. Mehlhorn, G. Rote & C. Yap).
  26. * Euclidean minimum spanning trees and bichromatic closest pairs, in ``Proc. 6th Annual Symposium on Computational Geometry'' (1990) 203-210 (with P. Agarwal, H. Edelsbrunner & O. Schwarzkopf).
  27. Efficient parallel computation of arrangements of hyperplanes in d dimensions, in ``Proc. 2nd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA `90)'' (1990) 290-297 (with T. Hagerup & H. Jung).
  28. * Drawing graphs in the plane with high resolution, in ``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).
  29. * Fat triangles determine linearly many holes, in ``Proc. 32th IEEE Symposium on Foundations of Computer Science (FOCS '91)'' (1991) 49-58 (with J. Matousek, J. Pach, S. Sifrony, N. Miller & M. Sharir).
  30. * Discrepancy and epsilon -approximations for bounded VC-dimension, in ``Proc. 32th IEEE Symposium on Foundations of Computer Science (FOCS'91)'' (1991) 424-430 (with J. Matousek & L. Wernisch).
  31. * Tail estimates for the space complexity of randomized incremental algorithms, in ``Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms (SODA `92)'' (1992) 89-93 (with K. Mehlhorn & M. Sharir).
  32. 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) 570-579 (with M. Sharir).
  33. * A subexponential bound for linear programming, in ``Proc. 8th Annual ACM Symposium on Computational Geometry'' (1992) 1-8 (with J. Matousek & M. Sharir).
  34. * Improved bounds for weak epsilon-nets for convex sets, in ``Proc. 25th Annual ACM Symposium on the Theory of Computing'' (1993) 495-504 (with B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas & M. Sharir).
  35. * 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) 397-408 (with B. Wolfers).
  36. * Cutting dense point sets in half, in ``Proc. 10th Annual ACM Symposium on Computational Geometry'' (1994) 203-210 (with H. Edelsbrunner & P. Valtr).
  37. * Fast greedy triangulation algorithms, in ``Proc. 10th Annual ACM Symposium on Computational Geometry'' (1994) 211-220 (with M. Dickerson, R. S. Drysdale & S. McElfrish).
  38. * Voronoi diagrams of lines in 3-space under polyhedral convex distance functions, in ``Proc. 6th ACM-SIAM Symposium on discrete Algorithms (SODA `95)'', (1995) 197-204 (with L. P. Chew, K. Kedem, M. Sharir & B. Tagansky).
  39. * 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) 36-48 (with T. Asano, T. Ranjan, T. Roos & P. Widmayer).
  40. Rectilinear and polygonal p-piercing and p-center problems, in ``Proc. 12th Annual ACM Symposium on Computational Geometry'', (1996) 122-132 (with M. Sharir).
  41. * The discrete 2-center problem, in ``Proc. 13th Annual ACM Symposium on Computational Geometry'', (1997) 147-155 (with P. Agarwal & M. Sharir).
  42. Results on k-sets and j-facets via continuous motions, in "Proc. 14th Annual ACM Symposium on Computational Geometry", (1998) 192-199 (with A. Andrzejak, B. Aronov, S. Har-Peled & R. Seidel).
  43. * B. Gärtner, E. Welzl, Random sampling in geometric optimization: New insights and applications, Proc. 16th Ann. ACM Symp. on Computational Geometry (2000) 91-99.
  44. * U. Wagner, E. Welzl, Origin-embracing distributions or a continuous analogue of the Upper Bound Theorem, Proc. 16th Ann. ACM Symp. on Computational Geometry (2000) 50-56.
  45. * 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) 306-315.
  46. * M. Sharir, E. Welzl, Balanced lines, halving triangles, and the Generalized Lower Bound Theorem, Proc. 17th Ann. ACM Symp. on Computational Geometry (2001) 315-318.
  47. T. Szabó, E. Welzl, Unique sink orientations of cubes, Proc. 42nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS) (2001) 547-555. [pdf]
  48. 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) 42-53.
  49. * 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) 143-156, Kluwer Adacemic Publishers.
  50. * J. Hage, T. Harju, E. Welzl, Euler Graphs, Triangle-free graphs and bipartite graphs in switching classes, Proc. 1st International Conference on Graph Transformation (ICGT), Lecture Notes in Computer Science 2505 (2002) 148-160.
  51. M. Laumanns, L. Thiele, E. Zitzler, E. Welzl, K. Deb, Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem, Parallel Problem Solving From Nature, Lecture Notes in Computer Science 2439 (2002) 44-53.
  52. * M. Sharir, E. Welzl, Point-line incidences in space, Proc. 18th Ann. ACM Symp. on Computational Geometry (2002) 107-115.
  53. U. Adamy, Th. Erlebach, D. Mitsche, I. Schurr, B. Speckmann, E. Welzl, Off-line admission control for advance reservations in star networks, Proc. 2nd Workshop on Approximation and Online Algorithms (WAOA04), Lecture Notes in Computer Science 3351 (2005) 211-224.
  54. * P.K. Agarwal, M. Sharir, E. Welzl, Algorithms for center and Tverberg points, Proc. 20th Annual ACM Symposium on Computational Geometry (SoCG) (2004) 61-67.
  55. A. Fiat, M. Levy, J. Matoušek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, E. Welzl, Online conflict-free coloring for intervals, Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2005) 545-554.
  56. 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) 188-198.
  57. * M. Sharir, E. Welzl, On the number of crossing-free matchings, (cycles, and partitions), Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2006) 860-869. [pdf]
  58. M. Sharir, E. Welzl, Random triangulations of planar point sets, Proc. 22nd Annual ACM Symposium on Computational Geometry (SoCG) (2006) 273-281. [pdf]
  59. * 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) 261-274. [pdf]
  60. A. Razen, J. Snoeyink, E. Welzl, 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) (2008) 188-193. [pdf]
  61. 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) 1872-1880.
  62. M. Sharir, A. Sheffer, E. Welzl, On Degrees in Random Triangulations of Point Sets, Proc. 26th Annual Symposium on Computational Geometry (SoCG) (2010) 297-306.