Welzl, Miscellaneous Publications

Emo Welzl, Miscellaneous Publications

(``*'' indicates that a second version has appeared in a journal or book)

A simple method for solving two-dimensional static range searching, Bulletin EATCS 25 (1985) 31-33 (with M. Overmars).
k-Sets of finite point sets and k-switches in circular sequences, Proc. 3rd Colloquium on Discrete Geometry (Salzburg) (1985) 283-290.
On the set of all subgraphs of the graphs in a boundary NLC graph language, The Book of L (G. Rozenberg & A. Salomaa, Eds.), (1986) 445-459.
Basic techniques in computational geometry, Proc. 14th SOFSEM Seminar, (1987) 189-214 (with Mark Overmars).
Counting points in halfplanes - an Ο(n log n) space and Ο(√n log²n) time solution, Ten Years IIG, Institute for Information Processing, Graz University of Technology, (1988) 192-197.
Smallest enclosing disks (balls and ellipsoids), New Results and New Trends in Computer Science, (H. Maurer, Ed.), LNCS 555 (1991) 359-370. [pdf]
On spanning trees with low crossing numbers, Data Structures and Efficient Algorithms, (B. Monien, Th. Ottmann, Eds.), LNCS 594 (1992) 233-249. [pdf]
Gram's equation - A probabilistic proof, Results and Trends in Theoretical Computer Science, LNCS 812 (1994) 422-424.
Linear programming - randomization and abstract frameworks, in ``Proc. 13th Annual Symp. on Theoretical Aspects of Computer Sci.'', Lecture Notes in Computer Science 1046 (1996) 669-688 (with B. Gärtner). [pdf]
Suchen und Konstruieren durch Verdoppeln, in Highlights der Informatik (Ingo Wegener, Ed.), (1996) 221-228, Springer.
Piecewise linear approximations of Bézier-curves, communication in ``Proc. 13th Annual ACM Symposium on Computational Geometry'', (1997) 433-435 (with H. Alt & B. Wolfers). [pdf]
Contour edge analysis for polyhedron projections, in Geometric Modeling: Theory and Practice, (W. Strasser, R. Klein, R. Rau, Eds.), (1997) 379-394, Focus in Computer Graphics, Springer Verlag (with L. Kettner).
Halving point sets, in Documenta Mathematica, Extra Volume Proceedings of the International Congress of Mathematicians, (1998) Vol III, 471-478 (with A. Andrzejak). [ps]
One sided error predicates in geometric computing, in "Proc. 15th IFIP World Computer Congress", Fundamentals - Foundations of Computer Science (K. Mehlhorn, Ed.), (1998) 13-26 (with L. Kettner).
* G. Karolyi, E. Welzl, Crossing-free segments and triangles in point configurations, in "Proc. 1st Japanese-Hungarian Symp. on Discrete Math. and Its Appl.", (1999) 265-272.
* A. Dumitrescu, B. Gärtner, S. Pedroni, E. Welzl, Enumerating triangulation paths, Proc. 12th Ann. Canadian Conf. on Computational Geometry (CCCG) (2000) 233-238. [ps]
* B. Gärtner, E. Welzl, On a Simple Sampling Lemma, Proc. Computing: The Australasian Theory Symp., Electronic Notes in Theoretical ComputerScience 31 (2000) 10 pages.
B. Gärtner, E. Welzl, Explicit and Implicit Enforcing - Randomized Optimization, in Lectures of the Graduate Program Computational Discrete Mathematics, LNCS 2122 (2001) 26-49. [pdf]
M. Dyer, N. Megiddo, E. Welzl, Linear Programming, in: Handbook of Discrete and Computational Geometry (J.E. Goodman, J. O'Rourke, Eds.), Chapman and Hall/CRC, (2004) 999-1014. [pdf] (New edition: M. Dyer, B. Gärtner, N. Megiddo, E. Welzl. Linear Programming. In: Handbook of Discrete and Computational Geometry, 3rd Edition (J. E. Goodman, J. O'Rourke, Cs. D. Tóth, eds.), Chapman and Hall/CRC,2017.)
* E. Welzl, Kleinster umschliessender Kreis-Ein Demokratiebeitrag aus der Schweiz?, Algorithmus der Woche 42 (2006). [pdf]
* E. Welzl, Kleinster umschliessender Kreis (Ein Demokratiebeitrag aus der Schweiz?), Taschenbuch der Algorithmen, (B. Vöcking et al., Eds.), Springer-Verlag Berlin Heidelberg, eXamen.press, (2008) 385-388. [pdf]
A. Razen, E. Welzl, On the Number of Crossing-Free Partitions in the Plane, Abstracts 25th European Workshop on Computational Geometry (EuroCG) (2009) 147-150.
H. Gebauer, R. A. Moser, D. Scheder, E. Welzl, The Lovász Local Lemma and Satisfiability, Efficient Algorithms - Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday in Lecture Notes in Computer Science (2009) 30-54.
E. Welzl, The smallest enclosing circle - A contribution to democracy from Switzerland?, Algorithms Unplugged, (B. Vöcking, H. Alt, M. Dietzfelbinger, R. Reischuk, C. Scheideler, H. Vollmer, and D. Wagner, Eds.), (2011) 357-360.
A. Razen, E. Welzl, Counting plane graphs with exponential speed-up, Rainbow of Computer Science (C.S. Calude, G. Rozenberg, and A.Salomaa, Eds.) LNCS 6570 (2011) 36-46.
* O. Aichholzer, J. Cardinal, Th. Hackl, F. Hurtado, M. Korman, A. Pilz, R. I. Silveira, R. Uehara, B. Vogtenhuber, E. Welzl, Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane Proc. 25th Canadian Conference on Computational Geometry (CCCG) (2013) 169-174.
* O. Aichholzer, Th. Hackl, M. Korman, M. van Kreveld, M. Löffler, A. Pilz, B. Speckmann, E. Welzl, Packing Plane Spanning Trees and Paths in Complete Geometric Graphs, Proc. 26th Canadian Conference on Computational Geometry (CCCG) (2014) 233-238.

Short Abstracts

E. Welzl, Geometric optimization and unique sink orientations of cubes, in: "Proc. 29th International Symposium on the Mathematical Foundation of Computer Science (MFCS`04)", Lecture Notes in Computer Science 3153 (2004) p. 176.
E. Welzl, Counting plane graphs on point sets in the plane, Proc. XI Encuentros de Geometría Computacional (EGC`05), (2005) p. 13.
E. Welzl, Random triangulations of planar point sets, Proc. V Jornadas de Matemática Discreta y Algoríthmica (V JMDA), (2006) 41-46.
E. Welzl, Random triangulations of planar point sets, in: "Algorithmic Graph Theory", Oberwolfach Reports 7 (2006) 432-435.
E. Welzl, The number of crossing-free configurations on finite point sets in the plane, in: "Proc. 26th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS`06)", Lecture Notes in Computer Science 4337 (2006) p. 20.
E. Welzl, The number of triangulations on planar point sets, in: "Proc. 14th International Symposium on Graph Drawing (GD`06)", Lecture Notes in Computer Science 4372 (2007), to appear.
E. Welzl, On the number of lattice triangulations, in: "Combinatorics, Probability, and Computing", Oberwolfach Reports (2007), to appear.
E. Welzl, When Conflicting Constraints Can Be Resolved - The Lovász Local Lemma and Satisfiability, Proc. 37th Annual International Colloquium on Automata, Languages and Programming (ICALP), LNCS 6198 (2010) 18-18.
E. Welzl, Counting Simple Polygonizations of Planar Point Sets, Proc. 23rd Canadian Conference on Computational Geometry (CCCG) (2011).

Editor for Special Volumes, Proceedings, etc.

R. Seidel, E. Welzl (Eds.), special issue devoted to research in Computational Geometry in Journal of Symbolic Computation 10:3-4 (1990) 225-393.
E. Welzl (Ed.), special issue devoted to the 11th ACM Symposium on Computational Geometry in Discrete & Computational Geometry 16:4 (1996) 315-479.
E. Welzl (Ed.), special issue devoted to the 11th ACM Symposium on Computational Geometry, experimental and applied in Computational Geometry-Theory and Applications 7:5-6 (1997) 263-406.
U. Montanari, J.D.P. Rolim, E. Welzl (Eds.), Automata, Languages and Programming, Proc. 27th International Colloquium, ICALP 2000, Lecture Notes in Computer Science 1853 (2000).
J.E. Goodman, J. Pach, E. Welzl (Eds.), Current Trends in Combinatorial and Computational Geometry, special volume devoted to special program "Discrete and Computational Geometry" at MSRI in its series Mathematical Sciences Research Institute Publications 52 (2005), Cambridge University Press.
L. Arge, E. Welzl (Eds.), special issue devoted to the 15th European Symposium on Algorithms (ESA`07) in Algorithmica 55:2 (2009) 269-391. [foreword]
M. Hoffmann, E. Welzl (Eds.), special issue devoted to the 27th European Workshop on Computational Geometry (EuroCG`11) in Computational Geometry - Theory and Applications 47:6 (2014) 643-694. [foreword]