Emo Welzl, List of Publications in Refereed Journals

• On the complexity of the general coloring problem, Inform. and Control 51 (1981) 128-145 (with H.A. Maurer & I.H. Sudborough).
• Color families are dense, Theoret. Comput. Sci. 17 (1982) 29-41.
• Stabbing line segments, BIT 22 (1982) 274-281 (with H. Edelsbrunner, H.A. Maurer, F.P. Preparata, A.L. Rosenberg & D. Wood).
• Using string languages to describe picture languages, Inform. and Control 54 (1982) 155-185 (with H.A. Maurer & G. Rozenberg).
• Stationing guards in rectilinear art galleries, Comput. Graphics and Image Process. 27 (1984) 167-176 (with H. Edelsbrunner & J. O'Rourke).
• Symmetric graphs and interpretations, J. Combin. Theory Ser. B 37 (1984) 235-244.
• Complexity and decidability for chain code picture languages, Theoret. Comput. Sci. 36 (1985) 173-202 (with I.H. Sudborough).
• 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).
• Recurrent words and simultaneous growth in TOL-systems, Theoret. Comput. Sci. 35 (1985) 1-16 (with K.-J. Lange).
• Constructing the visibility graph for n line segments in O(n²) time, Inform. Process. Lett. 20 (1985) 167-171.
• The bounded degree problem is decidable for NLC grammars, J. Comput. System Sci. 33 (1986) 415-422 (with D. Janssens & G. Rozenberg).
• Constructing belts in two-dimensional arrangements with applications, SIAM J. Comput. 15 (1986) 271-284 (with H. Edelsbrunner).
• On the maximal number of edges of many faces in an arrangement, J. Combin. Theory Ser. A 41 (1986) 159-166 (with H. Edelsbrunner).
• Trace languages defined by regular string languages, RAIRO Inform. Theor. 20 (1986) 103-119 (with I.J. Aalbersberg).
• Boundary NLC graph grammars - basic definitions, normal forms, and complexity, Inform. and Control 69 (1986) 136-167 (with G. Rozenberg).
• More on k-sets of finite sets in the plane, Discrete Comput. Geom. 1 (1986) 95-100.
• Graph theoretic closure properties of the family of boundary NLC graph languages, Acta Inform. 23 (1986) 289-309 (with G. Rozenberg).
• 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).
• Halfplanar range search in linear space and O(n^0.695) query time, Inform. Process. Lett. 23 (1986) 289-293 (with H. Edelsbrunner).
• Combinatorial properties of boundary NLC graph languages, Discrete Appl. Math 16 (1987) 59-73 (with G. Rozenberg).
• 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).
• ε-nets and simplex range queries, Discrete Comput. Geom. 2 (1987) 127-151 (with D. Haussler).
• Visibility graphs and obstacle-avoiding shortest paths, Z. Oper. Res. Ser. A 32 (1988) 145-164 (with H. Alt).
• Congruence, similarity, and symmetries of geometric objects, Discrete Comput. Geom. 3 (1988) 237-256 (with H. Alt, K. Mehlhorn & H. Wagener).
• 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).
• Quasi-optimal range searching in spaces with finite VC-dimension, Discrete Comput. Geom. 4 (1989) 467-490 (with B. Chazelle).
• 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)
• Boundary graph grammars with dynamic edge relabeling, J. Comput. System Sci. 40 (1990) 307-345 (with J. Engelfriet & G. Leih).
• 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).
• 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).
• Euclidean minimum spanning trees and bichromatic closest pairs, Discrete Comput. Geom. 6 (1991) 407-422 (with P. Agarwal, H. Edelsbrunner & O. Schwarzkopf).
• Polynomial graph-colorings, Discrete Appl. Math. 35 (1992) 29-45 (with W. Gutjahr & G. Wöginger).
• Good splitters for counting points in triangles, J. Algorithms 13 (1992) 307-319 (with J. Matoušek).
• Quasi-optimal upper bounds for simplex range searching and new zone theorems, Algorithmica 8 (1992) 407-429 (with B. Chazelle & M. Sharir).
• Simultaneous inner and outer approximations of shapes, Algorithmica 8 (1992) 365-389 (with R. Fleischer, K. Mehlhorn, G. Rote & C. Yap).
• Weaving patterns of lines and line segments in space, Algorithmica 9 (1993) 561-571 (with J. Pach & R. Pollack).
• Shortest paths for line segments, Algorithmica 10 (1993) 182-200 (with C. Icking, G. Rote & C. Yap).
• Tail estimates for the space complexity of randomized incremental algorithms, Comput. Geom. 4 (1993) 185-246 (with K. Mehlhorn & M. Sharir).
• Discrepancy and approximations for bounded VC-dimension, Combinatorica 13 (1993) 455-466 (with J. Matoušek & L. Wernisch).
• 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).
• Fat triangles determine linearly many holes, SIAM J. Comput. 23 (1994) 154-169 (with J. Matoušek, J. Pach, M. Sharir & Sh. Sifrony).
• Surface reconstruction between simple polygons via angle criteria, J. Symb. Comput. 17 (1994) 351-369 (with B. Wolfers).
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements, Discrete Comput. Geom. 12 (1994) 399-432 (with B. Gärtner).
• Improved bounds for weak ε-nets for convex sets, Discrete Comput. Geom. 13 (1995) 1-15 (with B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas & M. Sharir).
• A subexponential bound for linear programming, Algorithmica 16 (1996) 498-516 (with J. Matoušek & M. Sharir). [pdf]
• Cutting dense point sets in half, Discrete Comput. Geom. 17 (1997) 243-255 (with H. Edelsbrunner & P. Valtr).
• Fast greedy triangulation algorithms, Comput. Geom. 8 (1997) 67-86 (with M.T. Dickerson, R.L.S. Drysdale & S.A. McElfresh).
• The rank of sparse random matrices over finite fields, Random Struct. Alg. 10 (1997) 407-419 (with J. Blömer & R. Karp). [pdf]
• Space filling curves and their use in the design of geometric data structures, Theoret. Comput. Sci. 181 (1997) 3-15 (with T. Asano, D. Rajan, T. Roos & P. Widmayer).
• Approximation of convex figures by pairs of rectangles, Comput. Geom. 10 (1998) 77-87 (with O. Schwarzkopf, U. Fuchs & G. Rote).
• The discrete 2-center problem, Discrete Comput. Geom. 20 (1998) 287-305 (with P.K. Agarwal & M. Sharir).
• 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).
• A class of point sets with few k-sets, Comput. Geom. 16 (2000) 95-101 (with H. Alt, S. Felsner, F. Hurtado & M. Noy).
• Enumerating triangulation paths, Comput. Geom. 20 (2001) 3-12 (with A. Dumitrescu, B. Gärtner & S. Pedroni).
• Random sampling in geometric optimization: New insights and applications, Discrete Comput. Geom. 25 (2001) 569-590 (with B. Gärtner).
• Crossing-free segments and triangles in point configurations, Discrete Appl. Math. 112 (2001) 77-88 (with Gy. Károlyi).
• Entering and leaving  j-facets, Discrete Comput. Geom. 25 (2001) 351-364. [pdf]
• A continuous analogue of the Upper Bound Theorem, Discrete Comput. Geom. 26 (2001) 205-219 (with U. Wagner). [pdf]
• In between k-sets, j-facets, and i-faces: (i,j)-Partitions, Discrete Comput. Geom. 29 (2003) 105-131 (with A. Andrzejak). [pdf]
• Euler graphs, triangle-free graphs and bipartite graphs in switching classes, Fundam. Inform. 58 (2003) 23-37 (with J. Hage & T. Harju).
• Balanced lines, halving triangles, and the Generalized Lower Bound Theorem, Discrete & Computational Geometry - The Goodman-Pollack Festschrift (2003) 789-797 (with M. Sharir). [pdf]
• New nomogram for foetal weight estimation based on Hadlock's two-parameter formula, Ultraschall in der Medizin 25 (2004) 1-7 (with G.M. Beutler, J. Kurmanavicius, M. Hoffmann, R. Huch & M. Bajka).
• Algorithmic complexity of protein identification: Combinatorics of weighted strings, Discrete Appl. Math., 137 (2004) 27-46 (with M. Cieliebak, Th. Erlebach, Zs. Lipták & J. Stoye). [pdf]
• One line and n points, Random Struct. Alg. 23 (2004) 453-471 (with B. Gärtner, J. Solymosi, F. Tschirschnitz & P. Valtr). [pdf]
• Convex quadrilaterals and k-sets, in: Towards a Theory of Geometric Graphs, (J.Pach, Ed.), Contemporary Mathematics 342 (2004) 139-148 (with L. Lovász, K. Vesztergombi & U. Wagner). [pdf]
• Point-line incidences in space, Comb. Probab. Comput. 13 (2004) 203-220 (with M. Sharir). [pdf]
• On the number of crossing-free matchings, cycles, and partitions, SIAM J. Comput. 36 (2006) 1342-1359 (with M. Sharir ). [pdf]
• Online conflict-free coloring for intervals, SIAM J. Comput. 36 (2006) 956-973 (with K. Chen, A. Fiat, H. Kaplan, M. Levy, J. Matoušek, E. Mossel, J. Pach, M. Sharir, Sh. Smorodinsky & U. Wagner).
• Algorithms for center and Tverberg points, ACM Trans. Algorithms 5 (2008) 5:-5:20 (with P. Agarwal and M. Sharir).
• Catching elephants with mice: Sparse sampling for monitoring sensor networks, ACM Transactions on Sensor Networks 6 (2009) 1:1-1:27 (with S. Gandhi & S. Suri).
• On degrees in random triangulations of point sets, J. Combin. Theory Ser. A 118 (2011) 1979-1999 (with M. Sharir & A. Sheffer).
• Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn's Technique, Journal of Combinatorial Theory, Series A 120 (2013), 777-794 (with M. Sharir & A. Sheffer). [arXiv]
• On the number of crossing-free partitions, Comput. Geom. 46 (2013), 879-893 (with A. Razen).
• On the number of upward planar orientations of maximal planar graphs, Theoret. Comput. Sci. 544 (2014) 32-59 (with F. Frati & J. Gudmundsson).
• Cell-paths in mono- and bichromatic line arrangements in the plane, Discrete Math. Theor. Comput. Sci. 16 (2014) 317-332 (with O. Aichholzer, J. Cardinal, Th. Hackl, F. Hurtado, M. Korman, A. Pilz, R.I. Silveira, R. Uehara & B. Vogtenhuber).
• Packing plane spanning trees and paths in complete geometric graphs, Inform. Process. Lett. 124 (2017) 35-41 (with O. Aichholzer, Th. Hackl, M. Korman, M. van Kreveld, M. Löffler, A. Pilz & B. Speckmann).
• ARRIVAL: A zero-player graph game in NP ∩ coNP, A Journey through Discrete Mathematics. A Tribute to Jiří Matoušek (M. Loebl, J. Nešetřil and R. Thomas, Eds.) (2017) 367-374 (with J. Dohrau, B. Gärtner, M. Kohler & J. Matoušek). [arXiv]
• Crossing-free perfect matchings in wheel point sets, A Journey through Discrete Mathematics. A Tribute to Jiří Matoušek, (M. Loebl, J. Nešetřil & R. Thomas, Eds.) (2017) 735-764 (with A.J. Ruiz).
• Order on order types, Discrete Comput. Geom. 59 (2018) 886-922 (with A. Pilz).
• Minimal representations of order types by geometric graphs, J. Graph Algorithms and Appl. 24 (2020) 551-572 (with O. Aichholzer, M. Balko, M. Hoffmann, J. Kynčl, W. Mulzer, I. Parada, A. Pilz, M. Scheucher, P. Valtr & B. Vogtenhuber). [arXiv]
• Solving and sampling with many solutions, Algorithmica 82 (2020) 1474-1489 (with J. Cardinal & J. Nummenpalo). [arXiv]
• From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices, Discrete Comput. Geom. 64 (2020) 1067-1097 (with A. Pilz & M. Wettstein). [arXiv]
• Lower bounds for searching robots, some faulty, Distributed Comput. (special issue of the 37th Symp. on Principles of Distributed Computing) 34 (2021) 229-237 (with A. Kupavskii). [arXiv]
• Connectivity of triangulation flip graphs in the plane, Discrete Compu. Geom. (special issue of 36th International Symp. on Computational Geometry) 68 (2022) 1227-1284 (with U. Wagner). [arXiv]
• Convex hulls of random order types, Journal of the ACM 70 (2023) 1-47, Article 8 (with X. Goaoc). [arXiv]