Abstract by
Gábor Tardos
Hungarian Academy of Sciences
On the boundary complexity of the union of fat triangles.
A triangle is said to be d-fat if its smallest angle is at least d > 0. A connected component of the complement of the union of a family of triangles is called a hole.

We show that every family of d-fat triangles in the plane determines at most O((n/d)log(2/d)) holes. This improves earlier bounds of Efrat, Rote, Sharir, Matou sek et al. Solving a problem of Agarwal and Bern, we also give a general upper bound for the number of holes determined by n triangles in the plane with given angles.

The results represent joint work with János Pach.

Tuesday, November 16, 1999, 12:00 p.m.  - 241 Altgeld Hall
GRAPH THEORY AND COMBINATORICS

Go Back