Unit squares intersecting all secants of a square

LetS be a square of side lengths>0. We construct, for any sufficiently larges, a set of less than 1.994s closed unit squares whose sides are parallel to those ofS such that any straight line intersectingS intersects at least one square ofS. It disproves L. Fejes Tóth's conjecture that, for integrals, there is no such configuration of less than 2s−1 unit squares. Supported by “Deutsche Forschungsgemeinschaft”, Grant We 1265/2-1.     

The probability thatn random points in a triangle are in convex position

We show thatn random points chosen independently and uniformly from a triangle are in convex position with probability $$\frac{{2^n (3n - 3)!}}{{((n - 1)!)^3 (2n)!}}$$ .     

Lines,line-point incidences and crossing families in dense sets

LetP be a set ofn points in the plane. We say thatP isdense if the ratio between the maximum and the minimum distance inP is of order . A setC of line segments in the plane is calleda crossing family if the relative interiors of any two line segments ofC intersect. Vertices of line segments of a crossing familyC are calledvertices of C. It is known that for any setP ofn points in general position in the plane there is a crossing family of size with vertices inP. In this paper we show that ifP is dense then there is a crossing family of almost linear size with vertices inP.The above result is related to well-known results of Beck and of Szemerédi and Trotter. Beck proved that any setP ofn points in the plane, not most of them on a line, determines at least (n ²) different line. Szemerédi and Trotter proved that ifP is a set ofn points and is a set ofm lines then there are at mostO(m ^2/3 n ^2/3 +m+n) incidences between points ofP and lines of . We study whether or not the bounds shown by Beck and by Szemerédi and Trotter hold for any dense setP even if the notion of incidence is extended so that a point is considered to be incident to a linel if it lies in a small neighborhood ofl. In the first case we get very close to the conjectured bound (n ²). In the second case we obtain a bound of order .The work on this paper was supported by Czech Republic grant GAR 201/94/2167, by Charles University grants No. 351 and 361, by Deutsche Forschungsgemeinschaft, grant We 1265/2-1, and by DIMACS.     

Rough surface scattering simulations using graphics cards

In this article we present results of rough surface scattering calculations using a graphical processing unit implementation of the Finite Difference in Time Domain algorithm. Numerical results are compared to real measurements and computational performance is compared to computer processor implementation of the same algorithm. As a basis for computations, atomic force microscope measurements of surface morphology are used. It is shown that the graphical processing unit capabilities can be used to speedup presented computationally demanding algorithms without loss of precision.     

The Partitioned Version of the Erdős—Szekeres Theorem

   Abstract. Let k≥ 4 . A finite planar point set X is called a convex k -clustering if it is a disjoint union of k sets X ₁ , . . . ,X _k of equal sizes such that x ₁ x ₂ . . . x _k is a convex k -gon for each choice of x ₁ ∈ X ₁ , . . . ,x _k ∈ X _k . Answering a question of Gil Kalai, we show that for every k≥ 4 there are two constants c=c(k) , c'=c'(k) such that the following holds. If X is a finite set of points in general position in the plane, then it has a subset X' of size at most c' such that X \ X' can be partitioned into at most c convex k -clusterings. The special case k=4 was proved earlier by Pór. Our result strengthens the so-called positive fraction Erdos—Szekeres theorem proved by Barany and Valtr. The proof gives reasonable estimates on c and c' , and it works also in higher dimensions. We also improve the previous constants for the positive fraction Erdos—Szekeres theorem obtained by Pach and Solymosi.     

Coding and Counting Arrangements of Pseudolines

Arrangements of lines and pseudolines are important and appealing objects for research in discrete and computational geometry. We show that there are at most 2^{0.657> n2}2^{0.657\> n^{2}} simple arrangements of n pseudolines in the plane. This improves on previous work by Knuth who proved an upper bound of 3^\binomn2 @ 2^{0.792> n2}3^{\binom{n}{2}} \cong 2^{0.792\> n^{2}} in 1992 and the first author, who obtained 2^{0.697> n2}2^{0.697\> n^{2}} in 1997. The argument uses surprisingly little geometry. The main ingredient is a lemma that was already central to the argument given by Knuth.     

Geometric Graphs with Few Disjoint Edges

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position, the edges are represented by straight line segments connecting the corresponding points. Improving a result of Pach and T?rőcsik, we show that a geometric graph on n vertices with no k+1 pairwise disjoint edges has at most k ³ (n+1) edges. On the other hand, we construct geometric graphs with n vertices and approximately (3/2)(k-1)n edges, containing no k+1 pairwise disjoint edges. We also improve both the lower and upper bounds of Goddard, Katchalski, and Kleitman on the maximum number of edges in a geometric graph with no four pairwise disjoint edges. Received May 7, 1998, and in revised form March 24, 1999.     

A Positive Fraction Erdos - Szekeres Theorem

We prove a fractional version of the Erdős—Szekeres theorem: for any k there is a constant c _k > 0 such that any sufficiently large finite set X⊂ R ² contains k subsets Y ₁ , ... ,Y _k , each of size ≥ c _k |X| , such that every set {y ₁ ,...,y _k } with y _i ε Y _i is in convex position. The main tool is a lemma stating that any finite set X⊂ R ^d contains ``large' subsets Y ₁ ,...,Y _k such that all sets {y ₁ ,...,y _k } with y _i ε Y _i have the same geometric (order) type. We also prove several related results (e.g., the positive fraction Radon theorem, the positive fraction Tverberg theorem). <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p335.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received March 8, 1996, and in revised form June 24, 1996.     

Convex independent sets and 7-holes in restricted planar point sets

For a finite setA of points in the plane, letq(A) denote the ratio of the maximum distance of any pair of points ofA to the minimum distance of any pair of points ofA. Fork>0 letc (k) denote the largest integerc such that any setA ofk points in general position in the plane, satisfying for fixed , contains at leastc convex independent points. We determine the exact asymptotic behavior ofc (k), proving that there are two positive constants=(), such thatk ^1/3c (k)k ^1/3. To establish the upper bound ofc (k) we construct a set, which also solves (affirmatively) the problem of Alonet al. [1] about the existence of a setA ofk points in general position without a 7-hole (i.e., vertices of a convex 7-gon containing no other points fromA), satisfying . The construction uses Horton sets, which generalize sets without 7-holes constructed by Horton and which have some interesting properties.     

A Sufficient Condition for the Existence of Large Empty Convex Polygons

   Abstract. Let P be a set of points in general position in the plane. We say that P is k -convex if no triangle determined by P contains more than k points of P in the interior. We say that a subset A of P in convex position forms an empty polygon (in P ) if no point of P \ A lies in the convex hull of A . We show that for any k,n there is an N=N(k,n) such that any k -convex set of at least N points in general position in the plane contains an empty n -gon. We also prove an analogous statement in R ^d for each odd d≥ 3 .