Fat Triangles Determine Linearly Many Holes

Emo Welzl (joint work with Jiri Matousek, Janos Pach, Micha Sharir, Shmuel Sifrony) Institut für Informatik Freie Universität Berlin email: emo@inf.fu-berlin.de Report B 92-13 June 92

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-92-13.ps.gz
We show that for every fixed $\delta>0$ the following holds: If $F$ is a union of $n$ triangles, all of whose angles are at least $\delta$, then the complement of $F$ has $O(n)$ connected components, and the boundary of $F$ consists of $O(n \log \log n)$ straight segments (where the constants of proportionality depend on $\delta$). This latter complexity becomes linear if all triangles are of roughly the same size or if they are all infinite wedges.