Emo Welzl, Publications / Miscellaneous

(``*'' indicates that a second version has appeared in a journal or book)
  1. A simple method for solving two-dimensional static range searching, Bulletin EATCS 25 (1985) 31-33 (with M. Overmars).
  2. k-Sets of finite point sets and k-switches in circular sequences, in ``Proc. 3rd Colloquium on Discrete Geometry, Salzburg'' (1985) 283-290.
  3. 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, Springer Verlag.
  4. Basic techniques in computational geometry, in ``Proc. of the 14th SOFSEM Seminar'', (1987) 189-214 (with Mark Overmars).
  5. Counting points in halfplanes - an O(n log n) space and O(sqrt{n} log^2 n) time solution, ``Ten Years IIG, Institute for Information Processing, Graz University of Technology'', (1988) 192-197.
  6. Smallest enclosing disks (balls and ellipsoids), ``New Results and New Trends in Computer Science'', (H. Maurer, Ed.), Lecture Notes in Computer Science 555 (1991) 359-370. [pdf]
  7. On spanning trees with low crossing numbers, ``Data Structures and Efficient Algorithms'', (B. Monien, Th. Ottmann, Eds.), Lecture Notes in Computer Science 594 (1992) 233-249. [pdf]
  8. Gram's equation - A probabilistic proof, ``Results and Trends in Theoretical Computer Science'', Lecture Notes in Computer Science 812 (1994) 422-424.
  9. 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]
  10. Suchen und Konstruieren durch Verdoppeln, in Highlights der Informatik (Ingo Wegener, Ed.), (1996) 221-228, Springer.
  11. 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]
  12. 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).
  13. Halving point sets, in Documenta Mathematica, Extra Volume Proceedings of the International Congress of Mathematicians, (1998) Vol III, 471-478 (with A. Andrzejak).
  14. 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).
  15. * 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.
  16. * A. Dumitrescu, B. Gärtner, S. Pedroni, E. Welzl, Enumerating triangulation paths, Proc. 12th Ann. Canadian Conf. on Computational Geometry (CCCG) (2000) 233-238.
  17. * 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.
  18. B. Gärtner, E. Welzl, Explicit and Implicit Enforcing - Randomized Optimization, in Lectures of the Graduate Program Computational Discrete Mathematics, Lecture Notes in Computer Science 2122 (2001) 26-49. [pdf]
  19. 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]
  20. * E. Welzl, Kleinster umschliessender Kreis-Ein Demokratiebeitrag aus der Schweiz?, Algorithmus der Woche 42 (2006). [pdf]
  21. 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]
  22. 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.
  23. 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.
Short Abstracts
  1. 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.
  2. E. Welzl, Counting plane graphs on point sets in the plane, Proc. XI Encuentros de Geometría Computacional (EGC`05), (2005) p. 13.
  3. E. Welzl, Random triangulations of planar point sets, Proc. V Jornadas de Matemática Discreta y Algoríthmica (V JMDA), (2006) 41-46.
  4. E. Welzl, Random triangulations of planar point sets, in: "Algorithmic Graph Theory", Oberwolfach Reports 7 (2006) 432-435.
  5. 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.
  6. 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.
  7. E. Welzl, On the number of lattice triangulations, in: "Combinatorics, Probability, and Computing", Oberwolfach Reports (2007), to appear.
Editor for Special Volumes, Proceedings, etc.
  1. R. Seidel, E. Welzl (Eds.), special issue (devoted to papers from Computational Geometry) of Journal of Symbolic Computation 10:3-4 (1990) 225-393.
  2. E. Welzl (Ed.), special issue (devoted to 11th ACM Symposium on Computational Geometry) of Discrete & Computational Geometry 16:4 (1996) 315-479.
  3. E. Welzl (Ed.), special issue (devoted to 11th ACM Symposium on Computational Geometry, experimental and applied) of Computational Geometry-Theory and Applications 7:5-6 (1997) 263-406.
  4. 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).
  5. 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.
  6. L. Arge, E. Welzl (Eds.), special issue (devoted to the 15th European Symposium on Algorithms) of Algorithmica 55(2) (2009)