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.