Samenvatting
We show that, for any $\gamma > 0$, the combinatorial complexity of the union of $n$ locally $\gamma$-fat objects of constant complexity in the plane is $\frac{n}{\gamma^4} 2^{O(\log^*n)}$. For the special case of $\gamma$-fat triangles, the bound improves to $O(n \log^*{n} + \frac{n}{\gamma}\log^2{\frac{1}{\gamma}})$.
Keywords: combinatorial geometry, union complexity, fat objects
Originele taal-2 | Engels |
---|---|
Pagina's (van-tot) | 543-572 |
Aantal pagina's | 30 |
Tijdschrift | SIAM Journal on Computing |
Volume | 43 |
Nummer van het tijdschrift | 2 |
DOI's | |
Status | Gepubliceerd - 2014 |