List of publications and manuscripts (Pavel Valtr)

Theses

Papers and manuscripts

  1. Convex independent sets and 7-holes in restricted planar point sets, Discrete and Computational Geometry 7 (1992), 135-152
  2. Sets in $R^d$ with no large empty convex subsets, Discrete Mathematics 108 (1992), 115-124
  3. Generalized Davenport-Schinzel sequences with linear upper bound (with R. Adamec and M. Klazar), Discrete Mathematics 108 (1992), 219-229
  4. A Ramsey-type theorem in the plane (with J. Nesetril), Combinatorics, Probability and Computing 3 (1994), 127-135
  5. Unit squares intersecting all secants of a square, Discrete and Computational Geometry 11 (1994), 235-239
  6. Cutting dense point sets in half (with H. Edelsbrunner and E. Welzl), Proc. Tenth Annual Symp. on Comp. Geom., Stony Brook, ACM Press (1994), 203-210; also Discrete and Computational Geometry 17 (1997), 243-255
  7. Generalized Davenport-Schinzel sequences (with M. Klazar), Combinatorica 14 (1994), 463-476
  8. Probability that $n$ random points are in convex position, Discrete and Computational Geometry 13 (1995), 637-643
  9. On the minimum number of empty polygons in planar point sets, Studia Scientiarum Mathematicarum Hungarica 30 (1995), 155-163
  10. Ramsey-remainder (with P. Erdös and Zs. Tuza), European Journal of Combinatorics 17 (1996), 519-532
  11. Lines, line-point incidences and crossing families in dense sets, DIMACS Technical Report 94-55 or Combinatorica 16 (1996), 269-294
  12. The probability that $n$ random points in a triangle are in convex position (abstract), Combinatorica 16 (1996), 567-573
  13. On Mutually Avoiding Sets, in: R.L. Graham and J. Nesetril (eds.), The Mathematics of Paul Erdös II, Springer, Algorithms and Combinatorics 14 (1997), 324-332
  14. Catalan numbers via random planar point sets, Intuitive Geometry (I. Barany, ed.), Bolyai Society Math. Studies 6 (1997), 441-443
  15. Graph drawings with no $k$ pairwise crossing edges, in: G. DiBattista (ed.), Graph Drawing '97, Rome, September 1997, pp. 205-218
  16. The complexity of the lower envelope of segments with $h$ endpoints (with J. Matousek), Intuitive Geometry (I. Barany, ed.), Bolyai Society Math. Studies 6 (1997), 407-411
  17. Ramsey-type results for geometric graphs, II (with Gy. Karolyi, J. Pach, and G. Toth), DIMACS Technical Report 97-13, Discrete and Computational Geometry 20 (1998), 375-388.
  18. Guarding galleries where no point sees a small area, Israel Journal of Mathematics 104 (1998), 1-16
  19. On the density of subgraphs in a graph with bounded independence number DIMACS Technical Report 97-11 and J. Comb. Th., Ser. B, 73 (1998), 146-158.
  20. Finding the convex hull of an $\alpha$-dense set
  21. A Ramsey property of order types (with J. Nesetril), J. of Comb. Th. (Ser. A) 81 (1998), 88-107
  22. A positive fraction Erdos-Szekeres theorem (with I. Barany), Discrete and Computational Geometry 19 (1998), 335-342.
  23. On geometric graphs with no $k$ pairwise parallel edges, DIMACS Technical Report 97-07 , Discrete and Computational Geometry 19 (1998), 461-469.
  24. Note on the Erdos-Szekeres theorem (with G. Toth), Discrete and Computational Geometry 19 (1998), 457-459, DIMACS Technical Report 97-31.
  25. Geometric graphs with few disjoint edges (with G. Toth), Discrete Comput. Geom. 22 (1999), 633-642 (also Proc. of Ann. Symp. Comput. Geom. 1998, pp. 181-194).
  26. The largest $k$-ball in a $d$-dimensional box (with H. Everett, I. Stojmenovic, and S. Whitesides), Computational Geometry: Theory and Applications 11 (1998), 59-67
  27. On an extremal problem for colored trees, Europ. J. Comb. 20 (1999), 115-121
  28. On galleries with no bad points, DIMACS Technical Report 96-55, Discrete and Computational Geometry 21 (1999), 193-200.
  29. Generalizations of Davenport-Schinzel sequences (survey paper), Contemporary Trends in Discrete Mathematics (Edited by: J. Nesetril, J. Kratochvil, F.S. Roberts, R.L. Graham), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 49 (1999), 349-389.
  30. Induced monochromatic subconfigurations (with J. Nesetril and J. Solymosi), Contemporary Trends in Discrete Mathematics (Edited by: J. Nesetril, J. Kratochvil, F.S. Roberts, R.L. Graham), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 49 (1999), 219-227
  31. Almost-tiling the plane by ellipses (with K. Kuperberg, W. Kuperberg, and J. Matousek), Discrete and Computational Geometry 22 (1999), 367-375.
  32. On visibility and covering by convex sets (with J. Matousek), Israel Journal of Mathematics 113 (1999), 341-379.
  33. Low-distortion embeddings of trees (with R. Babilon, J. Matousek, and J. Maxova), Graph Drawing 2001, Lecture Notes in Comp. Sci. 2265, Springer 2002, pp. 343-351.
  34. The partitioned version of the Erdos-Szekeres theorem (with A. Por), Discrete and Computational Geometry 28 (2002), 625-637.
  35. A sufficient condition for the existence of large empty convex polygons, Discrete and Computational Geometry 28 (2002), 671-682
  36. One line and n points (with B. Gartner, J. Solymosi, F. Tschirschnitz, and E. Welzl), Random Structures and Algorithms 23 (2003), 453-471.
  37. Davenport-Schinzel trees, Combinatorica 23 (2003), 151-184
  38. Point configurations in $d$-space without large subsets in convex position (with Gy. Karolyi), Discrete and Computational Geometry 30 (2003), 277-286.
  39. A Turan-type extremal theory of convex geometric graphs (with P. Brass and Gy. Karolyi), in: B. Aronov et al. (Eds.), Discrete and Computational Geometry--The Goodman-Pollack Festschrift, Springer, Berlin, 2003, pp. 275-300.
  40. VC-dimension of exterior visibility (with K. Daniilidis, V. Isler, and S. Kannan), to appear in IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (2004)
  41. Planar point sets with a small number of empty convex polygons (with I. Barany), to appear in Studia Math Hung.
  42. Distributions producing random Voronoi diagrams of large complexity
  43. Three asymptotically equivalent definitions of Davenport-Schinzel trees, submitted
  44. A Ramsey property of planar graphs (with J. Nesetril and J. Solymosi), to appear
  45. The unit distance problem on spheres (with K. Swanepoel), to appear

If you are interested in getting some of my papers, just send me an e-mail. If you don't get a reply in 10 days or so, please send me a reminder.

December 2003
Email: "surname"@kam.mff.cuni.cz