ON CONSTANTS FOR CUTTINGS IN THE PLANE

A theorem of Chazelle and Friedman with numerous applications in combi natorial and computational geometry asserts that for any set L of n li nes in the plane and for any parameter r > 1 there exists a subdivisio n of the plane into at most Cr? (possibly unbounded) triangles, C a co nstant, such that the interior of each triangle is intersected by at m ost n/r lines of L. (Such a subdivision is called a (1/r)-cutting for L.) We give upper and lower bounds on the constant C. We also consider the canonical triangulation of the arrangement of a random sample of r lines from L. Although this typically is not a (1/r)-cutting, the ex pectation of the kth degree average of the number of lines intersectin g a triangle is O(n/r) for any fixed k. We estimate the constant of pr oportionality in this result.