Emo Welzl, List of Publications in Refereed Journals

On the complexity of the general coloring problem,
Inform. and Control
51 (1981) 128145
(with H.A. Maurer & I.H. Sudborough).

Color families are dense,
Theoret. Comput. Sci.
17 (1982) 2941.

Stabbing line segments,
BIT
22 (1982) 274281
(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) 155185
(with H.A. Maurer & G. Rozenberg).

Stationing guards in rectilinear art galleries,
Comput. Graphics and Image Process.
27 (1984) 167176
(with H. Edelsbrunner & J. O'Rourke).

Symmetric graphs and interpretations,
J. Combin. Theory Ser. B
37 (1984) 235244.

Complexity and decidability for chain code picture languages,
Theoret. Comput. Sci.
36 (1985) 173202
(with I.H. Sudborough).

On the number of lineseparations of a finite set in the plane,
J. Combin. Theory Ser. A
38 (1985) 1529
(with H. Edelsbrunner).

Recurrent words and simultaneous growth in TOLsystems,
Theoret. Comput. Sci. 35 (1985) 116
(with K.J. Lange).

Constructing the visibility graph for n line segments in O(n^{2}) time,
Inform. Process. Lett.
20 (1985) 167171.

The bounded degree problem is decidable for NLC grammars,
J. Comput. System Sci. 33 (1986) 415422
(with D. Janssens & G. Rozenberg).

Constructing belts in twodimensional arrangements with applications,
SIAM J. Comput.
15 (1986) 271284
(with H. Edelsbrunner).

On the maximal number of edges of many faces in an arrangement,
J. Combin. Theory Ser. A
41 (1986) 159166
(with H. Edelsbrunner).

Trace languages defined by regular string languages,
RAIRO Inform. Theor.
20 (1986) 103119
(with I.J. Aalbersberg).

Boundary NLC graph grammars  basic definitions, normal forms, and complexity,
Inform. and Control
69 (1986) 136167
(with G. Rozenberg).

More on ksets of finite sets in the plane,
Discrete Comput. Geom.
1 (1986) 95100.

Graph theoretic closure properties of the family of boundary NLC graph languages,
Acta Inform.
23 (1986) 289309
(with G. Rozenberg).

Denseness, maximality, and decidability of grammatical families,
Ann. Acad. Sci. Fenn. Ser. A I Math.
11 (1986) 167178
(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) 289293
(with H. Edelsbrunner).

Combinatorial properties of boundary NLC graph languages,
Discrete Appl. Math
16 (1987) 5973
(with G. Rozenberg).

String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing,
Discrete Appl. Math.
16 (1987) 1730
(with K.J. Lange).

εnets and simplex range queries,
Discrete Comput. Geom.
2 (1987) 127151
(with D. Haussler).

Visibility graphs and obstacleavoiding shortest paths,
Z. Oper. Res. Ser. A
32 (1988) 145164
(with H. Alt).

Congruence, similarity, and symmetries of geometric objects,
Discrete Comput. Geom.
3 (1988) 237256
(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) 433466
(with H. Edelsbrunner & G. Rote).

Quasioptimal range searching in spaces with finite VCdimension,
Discrete Comput. Geom.
4 (1989) 467490
(with B. Chazelle).

Implicitely representing arrangements of lines or segments,
Discrete Comput. Geom.
4 (1989) 433466
(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) 307345
(with J. Engelfriet & G. Leih).

Combinatorial complexity bounds for arrangements of curves and spheres,
Discrete Comput. Geom.
5 (1990) 99160
(with K.L. Clarkson, H. Edelsbrunner, L.J. Guibas & M. Sharir).

Ranking intervals under visibility constraints,
Intern. J. Computer Math.
34 (1990) 129144
(with H. Edelsbrunner, J. A. Feldman, I. BenArroyo Hartmann & M. Overmars).

Euclidean minimum spanning trees and bichromatic closest pairs,
Discrete Comput. Geom.
6 (1991) 407422
(with P. Agarwal, H. Edelsbrunner & O. Schwarzkopf).

Polynomial graphcolorings,
Discrete Appl. Math.
35 (1992) 2945
(with W. Gutjahr & G. Wöginger).

Good splitters for counting points in triangles,
J. Algorithms
13 (1992) 307319
(with J. Matoušek).

Quasioptimal upper bounds for simplex range searching and new zone
theorems,
Algorithmica 8 (1992) 407429 (with B. Chazelle &
M. Sharir).

Simultaneous inner and outer approximations of shapes,
Algorithmica
8 (1992) 365389
(with R. Fleischer, K. Mehlhorn, G. Rote & C. Yap).

Weaving patterns of lines and line segments in space,
Algorithmica
9 (1993) 561571
(with J. Pach & R. Pollack).

Shortest paths for line segments,
Algorithmica
10 (1993) 182200
(with C. Icking, G. Rote & C. Yap).

Tail estimates for the space complexity of randomized incremental algorithms,
Comput. Geom.
4 (1993) 185246
(with K. Mehlhorn & M. Sharir).

Discrepancy and approximations for bounded VCdimension,
Combinatorica
13 (1993) 455466
(with J. Matoušek & L. Wernisch).

Drawing graphs in the plane with high resolution,
SIAM J. Comput.
22 (1993) 10351052 (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) 154169 (with J. Matoušek, J. Pach, M. Sharir &
Sh. Sifrony).

Surface reconstruction between simple polygons via angle criteria,
J. Symb. Comput. 17 (1994) 351369 (with B. Wolfers).

VapnikChervonenkis dimension and (pseudo)hyperplane arrangements,
Discrete Comput. Geom. 12 (1994) 399432 (with B. Gärtner).

Improved bounds for weak εnets for convex sets,
Discrete
Comput. Geom. 13 (1995) 115 (with B. Chazelle, H. Edelsbrunner,
M. Grigni, L. Guibas & M. Sharir).

A subexponential bound for linear programming,
Algorithmica
16 (1996) 498516
(with J. Matoušek & M. Sharir).
[pdf]

Cutting dense point sets in half,
Discrete Comput. Geom. 17
(1997) 243255 (with H. Edelsbrunner & P. Valtr).

Fast greedy triangulation algorithms,
Comput. Geom.
8 (1997) 6786
(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) 407419
(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) 315
(with T. Asano, D. Rajan, T. Roos & P. Widmayer).

Approximation of convex figures by pairs of rectangles,
Comput. Geom.
10 (1998) 7787
(with O. Schwarzkopf, U. Fuchs & G. Rote).

The discrete 2center problem,
Discrete Comput. Geom. 20
(1998) 287305 (with P.K. Agarwal & M. Sharir).

Voronoi diagrams of lines in three dimensions under a polyhedral convex
distance function,
J. Algorithms 29 (1998) 238255 (with L.P. Chew, K. Kedem, M. Sharir & B. Tagansky).

A class of point sets with few ksets,
Comput. Geom.
16 (2000) 95101
(with H. Alt, S. Felsner, F. Hurtado & M. Noy).

Enumerating triangulation paths,
Comput. Geom.
20 (2001) 312
(with A. Dumitrescu, B. Gärtner & S. Pedroni).

Random sampling in geometric optimization: New insights and applications,
Discrete Comput. Geom.
25 (2001) 569590
(with B. Gärtner).

Crossingfree segments and triangles in point configurations,
Discrete Appl. Math.
112 (2001) 7788
(with Gy. Károlyi).

Entering and leaving jfacets,
Discrete Comput. Geom.
25 (2001) 351364.
[pdf]

A continuous analogue of the Upper Bound Theorem,
Discrete Comput. Geom.
26 (2001) 205219
(with U. Wagner).
[pdf]

In between ksets, jfacets, and ifaces: (i,j)Partitions,
Discrete Comput. Geom.
29 (2003) 105131
(with A. Andrzejak).
[pdf]

Euler graphs, trianglefree graphs and bipartite graphs in switching classes,
Fundam. Inform.
58 (2003) 2337
(with J. Hage & T. Harju).

Balanced lines, halving triangles, and the Generalized Lower Bound Theorem,
Discrete & Computational Geometry  The GoodmanPollack Festschrift
(2003) 789797
(with M. Sharir).
[pdf]

New nomogram for foetal weight estimation based on Hadlock's twoparameter formula,
Ultraschall in der Medizin
25 (2004) 17
(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) 2746
(with M. Cieliebak, Th. Erlebach, Zs. Lipták & J. Stoye).
[pdf]

One line and n points,
Random Struct. Alg.
23 (2004) 453471
(with B. Gärtner, J. Solymosi, F. Tschirschnitz & P. Valtr).
[pdf]

Convex quadrilaterals and ksets,
in: Towards a Theory of Geometric Graphs,
(J.Pach, Ed.),
Contemporary Mathematics
342 (2004) 139148
(with L. Lovász, K. Vesztergombi & U. Wagner).
[pdf]

Pointline incidences in space,
Comb. Probab. Comput.
13 (2004) 203220
(with M. Sharir).
[pdf]

On the number of crossingfree matchings, cycles, and partitions,
SIAM J. Comput.
36 (2006) 13421359
(with M. Sharir ).
[pdf]

Online conflictfree coloring for intervals,
SIAM J. Comput.
36 (2006) 956973
(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:11:27
(with S. Gandhi & S. Suri).

On degrees in random triangulations of point sets,
J. Combin. Theory Ser. A
118 (2011) 19791999
(with M. Sharir & A. Sheffer).

Counting plane graphs: Perfect matchings, spanning cycles, and
Kasteleyn's Technique,
Journal of Combinatorial Theory, Series A
120 (2013), 777794
(with M. Sharir & A. Sheffer).
[arXiv]

On the number of crossingfree partitions,
Comput. Geom.
46 (2013), 879893
(with A. Razen).

On the number of upward planar orientations of maximal planar graphs,
Theoret. Comput. Sci.
544 (2014) 3259
(with F. Frati & J. Gudmundsson).

Cellpaths in mono and bichromatic line arrangements in the plane,
Discrete Math. Theor. Comput. Sci.
16 (2014) 317332
(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) 3541
(with O. Aichholzer, Th. Hackl, M. Korman, M. van Kreveld, M. Löffler, A. Pilz & B. Speckmann).

ARRIVAL: A zeroplayer 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) 367374
(with J. Dohrau, B. Gärtner, M. Kohler & J. Matoušek).
[arXiv]

Crossingfree 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) 735764
(with A.J. Ruiz).

Order on order types,
Discrete Comput. Geom.
59 (2018) 886922
(with A. Pilz).

Minimal representations of order types by geometric graphs,
J. Graph Algorithms and Appl.
24 (2020) 551572
(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) 14741489
(with J. Cardinal & J. Nummenpalo).
[arXiv]

From crossingfree graphs on wheel sets to embracing simplices and polytopes with few vertices,
Discrete Comput. Geom.
64 (2020) 10671097
(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) 229237
(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) 12271284
(with U. Wagner).
[arXiv]

Convex hulls of random order types,
Journal of the ACM
70 (2023) 147, Article 8
(with X. Goaoc).
[arXiv]