Emo Welzl, List of Publications / Refereed Journals

  1. On the complexity of the general coloring problem, Inform. and Control 51 (1981) 128-145 (with H.A. Maurer & I. H. Sudborough).
  2. Color families are dense, Theoret. Comput. Sci. 17 (1982) 29-41.
  3. Stabbing line segments, BIT 22 (1982) 274-281 (with H. Edelsbrunner, H.A. Maurer, F.P. Preparata, A.L. Rosenberg & D. Wood).
  4. Using stringlanguages to describe picture languages, Inform. and Control 54 (1982) 155-185 (with H.A. Maurer & G. Rozenberg).
  5. Stationing guards in rectilinear art galleries, Comput. Graphics and Image Process. 27 (1984) 167-176 (with H. Edelsbrunner & J. O'Rourke).
  6. Symmetric graphs and interpretations, J. Combin. Theory Ser. B 37 (1984) 235-244.
  7. Complexity and decidability for chain code picture languages, Theoret. Comput. Sci. 36 (1985) 173-202 (with I. H. Sudborough).
  8. On the number of line-separations of a finite set in the plane, J. Combin. Theory Ser. A 38 (1985) 15-29 (with H. Edelsbrunner).
  9. Recurrent words and simultaneous growth in TOL-systems, Theoret. Comput. Sci. 35 (1985) 1-16 (with K.-J. Lange).
  10. Constructing the visibility graph for n line segments in O(n^2) time, Inform. Process. Lett. 20 (1985) 167-171.
  11. The bounded degree problem is decidable for NLC grammars, J. Comput. System Sci. 33 (1986) 415-422 (with D. Janssens & G. Rozenberg).
  12. Constructing belts in two-dimensional arrangements with applications, SIAM J. Comput. 15 (1986) 271-284 (with H. Edelsbrunner).
  13. On the maximal number of edges of many faces in an arrangement, J. Combin. Theory Ser. A 41 (1986) 159-166 (with H. Edelsbrunner).
  14. Trace languages defined by regular string languages, RAIRO Inform. Theor. 20 (1986) 103-119 (with I. J. Aalbersberg).
  15. Boundary NLC graph grammars - basic definitions, normal forms, and complexity, Inform. and Control 69 (1986) 136-167 (with G. Rozenberg).
  16. More on k-sets of finite sets in the plane, Discrete Comput. Geom. 1 (1986) 95-100.
  17. Graph theoretic closure properties of the family of boundary NLC graph languages, Acta Inform. 23 (1986) 289-309 (with G. Rozenberg).
  18. Denseness, maximality, and decidability of grammatical families, Ann. Acad. Sci. Fenn. Ser. A I Math. 11 (1986) 167-178 (with H. A. Maurer, A. Salomaa & D. Wood).
  19. Halfplanar range search in linear space and O(n^0.695) query time, Inform. Process. Lett. 23 (1986) 289-293 (with H. Edelsbrunner).
  20. Combinatorial properties of boundary NLC graph languages, Discrete Appl. Math 16 (1987) 59-73 (with G. Rozenberg).
  21. String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing, Discrete Appl. Math. 16 (1987) 17-30 (with K.-J. Lange).
  22. Epsilon-nets and simplex range queries, Discrete Comput. Geom. 2 (1987) 127-151 (with D. Haussler).
  23. Visibility graphs and obstacle-avoiding shortest paths, Z. Oper. Res. Ser. A 32 (1988) 145-164 (with H. Alt).
  24. Congruence, similarity, and symmetries of geometric objects, Discrete Comput. Geom. 3 (1988) 237-256 (with H. Alt, K. Mehlhorn & H. Wagener).
  25. Testing the necklace condition for shortest tours and optimal factors in the plane, Theoret. Comput. Sci. 66 (1989) 433-466 (with H. Edelsbrunner & G. Rote).
  26. Quasi-optimal range searching in spaces with finite VC-dimension, Discrete Comput. Geom. 4 (1989) 467-490 (with B. Chazelle).
  27. Implicitely representing arrangements of lines or segments, Discrete Comput. Geom. 4 (1989) 433-466 (with H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir & J. Snoeyink)
  28. Boundary graph grammars with dynamic edge relabeling, J. Comput. System Sci. 40 (1990) 307-345 (with J. Engelfriet & G. Leih).
  29. Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (1990) 99-160 (with K. L. Clarkson, H. Edelsbrunner, L. J. Guibas & M. Sharir).
  30. Ranking intervals under visibility constraints, Intern. J. Computer Math. 34 (1990) 129-144 (with H. Edelsbrunner, J. A. Feldman, I. Ben-Arroyo Hartmann & M. Overmars).
  31. Euclidean minimum spanning trees and bichromatic closest pairs, Discrete Comput. Geom. 6 (1991) 407-422 (with P. Agarwal, H. Edelsbrunner & O. Schwarzkopf).
  32. Polynomial graph-colorings, Discrete Appl. Math. 35 (1992) 29-45 (with W. Gutjahr & G. Wöginger).
  33. Good splitters for counting points in triangles, J. Algorithms 13 (1992) 307-319 (with J. Matousek).
  34. Quasi-optimal upper bounds for simplex range searching and new zone theorems, Algorithmica 8 (1992) 407-429 (with B. Chazelle & M. Sharir).
  35. Simultaneous inner and outer approximations of shapes, Algorithmica 8 (1992) 365-389 (with R. Fleischer, K. Mehlhorn, G. Rote & Ch. Yap).
  36. Weaving patterns of lines and line segments in space, Algorithmica 9 (1993) 561-571 (with J. Pach & R. Pollack).
  37. Shortest paths for line segments, Algorithmica 10 (1993) 182-200 (with Chr. Icking, G. Rote & Ch. Yap).
  38. Tail estimates for the space complexity of randomized incremental algorithms, Computational Geometry: Theory and Applications 4 (1993) 185-246 (with K. Mehlhorn & M. Sharir).
  39. Discrepancy and approximations for bounded VC-dimension, Combinatorica 13 (1993) 455-466 (with J. Matousek & L. Wernisch).
  40. Drawing graphs in the plane with high resolution, SIAM J. Comput. 22 (1993) 1035-1052 (with M. Formann, T. Hagerup, I. Haralambides, M. Kaufmann, F.T. Leighton, A. Simvonis & G. Wöginger).
  41. Fat triangles determine linearly many holes, SIAM J. Comput. 23 (1994) 154-169 (with J. Matousek, J. Pach, M. Sharir & Sh. Sifrony).
  42. Surface reconstruction between simple polygons via angle criteria, J. of Symbolic Comput. 17 (1994) 351-369 (with B. Wolfers).
  43. Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements, Discrete Comput. Geom. 12 (1994) 399-432 (with B. Gärtner).
  44. Improved bounds for weak epsilon-nets for convex sets, Discrete Comput. Geom. 13 (1995) 1-15 (with B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas & M. Sharir).
  45. A subexponential bound for linear programming, Algorithmica 16 (1996) 498-516 (with J. Matousek & M. Sharir). [pdf]
  46. Cutting dense point sets in half, Discrete Comput. Geom. 17 (1997) 243-255 (with H. Edelsbrunner & P. Valtr).
  47. Fast greedy triangulation algorithms, Computational Geometry - Theory and Applications 8 (1997) 67-86 (with M. T. Dickerson, R. L S. Drysdale & S.A. McElfresh).
  48. The rank of sparse random matrices over finite fields, Random Structures and Algorithms 10 (1997) 407-419 (with J. Blömer & R. Karp). [pdf]
  49. Space filling curves and their use in the design of geometric data structures, Theoretical Computer Science 181 (1997) 3-15 (with T. Asano, D. Rajan, T. Roos & P. Widmayer).
  50. Approximation of convex figures by pairs of rectangles, Computational Geometry - Theory and Applications 10 (1998) 77-87 (with O. Schwarzkopf, U. Fuchs & G. Rote).
  51. The discrete 2-center problem, Discrete Comput. Geom. 20 (1998) 287-305 (with P.K. Agarwal & M. Sharir).
  52. Voronoi diagrams of lines in three dimensions under a polyhedral convex distance function, J. Algorithms 29 (1998) 238-255 (with L. P. Chew, K. Kedem, M. Sharir & B. Tagansky).
  53. A class of point sets with few k-sets, Computational Geometry - Theory and Applications 16 (2000) 95-101 (with H. Alt, S. Felsner, F. Hurtado, M. Noy).
  54. A. Dumitrescu B. Gärtner, S. Pedroni, E. Welzl, Enumerating triangulation paths, Computational Geometry - Theory and Applications 20 (2001) 3-12.
  55. B. Gärtner, E. Welzl, Random sampling in geometric optimization: New insights and applications, Discrete & Computational Geometry 25 (2001) 569-590.
  56. Gy. Károlyi, E. Welzl, Crossing-free segments and triangles in point configurations, Discrete Applied Mathematics 112 (2001) 77-88.
  57. E. Welzl, Entering and leaving  j-facets, Discrete & Computational Geometry 25 (2001) 351-364. [pdf]
  58. U. Wagner, E. Welzl, A continuous analogue of the UpperBound Theorem, Discrete & Computational Geometry 26 (2001) 205-219. [pdf]
  59. A. Andrzejak, E. Welzl, In between k-sets, j-facets, and i-faces: (i,j)-Partitions, Discrete & Computational Geometry 29:1 (2003) 105-131. [pdf]
  60. J. Hage, T. Harju, E. Welzl, Euler graphs, triangle-free graphs and bipartite graphs in switching classes, Fundamenta Informaticae 58:1 (2003) 23-37.
  61. M. Sharir, E. Welzl, Balanced lines, halving triangles, and the Generalized Lower Bound Theorem, Discrete & Computational Geometry - The Goodman-Pollack Festschrift (2003) 789-797. [pdf]
  62. G.M. Beutler, J. Kurmanavicius, M. Hoffmann, E. Welzl, R. Huch, M.Bajka, New nomogram for foetal weight estimation based on Hadlock's two-parameter formula, Ultraschall in der Medizin 25 (2004) 1-7.
  63. M. Cieliebak, Th. Erlebach, Zs. Lipták, J. Stoye, E. Welzl, Algorithmic complexity of protein identification: Combinatorics of weighted strings, Discrete Applied Mathematics, 137 (2004) 27-46.
  64. B. Gärtner, J. Solymosi, F. Tschirschnitz, P. Valtr, E. Welzl, One line and n points, Random Structures & Algorithms 23:4 (2004) 453-471. [pdf]
  65. L. Lovász, K. Vesztergombi, U. Wagner, E. Welzl, Convex quadrilaterals and k-sets, in: Towards a Theory of Geometric Graphs, (J.Pach, Ed.), Contemporary Mathematics 342 (2004) 139-148. [pdf]
  66. M. Sharir, E. Welzl, Point-line incidences in space, Combinatorics Probability and Computing 13 (2004) 203-220.
  67. P. Agarwal, M. Sharir, E. Welzl, Algorithms for center and Tverberg points, ACM Transactions on Algorithms 5 (1) (2008), Article 5 (20 pp).
  68. M. Sharir, E. Welzl, On the number of crossing-free matchings, cycles, and partitions, SIAM Journal of Computing 36 (2006) 1342-1359. [pdf]
  69. K. Chen, A. Fiat, H. Kaplan, M. Levy, J. Matousek, E. Mossel, J. Pach, M. Sharir, Sh. Smorodinsky, U. Wagner, E. Welzl, Online conflict-free coloring for intervals, SIAM Journal of Computing 36 (2006) 956-973.
  70. P. Agarwal, M. Sharir, E. Welzl, Algorithms for center and Tverberg points, ACM Transactions on Algorithms 5 (1) (2008), Article 5 (20 pp).
  71. S. Gandhi, S. Suri, E. Welzl, Catching Elephants with Mice: Sparse Sampling for Monitoring Sensor Networks, ACM Transactions on Sensor Networks 6(1) (2009), Article 1.