Abstract
We show that, for any γ > 0, the combinatorial complexity of the union of n locally γ-fat objects of constant complexity in the plane is nγ4 2O(log n). For the special case of γ-fat triangles,the bound improves to O(n log n + n/γ log2 1/γ ).
Original language | English (US) |
---|---|
Pages (from-to) | 543-572 |
Number of pages | 30 |
Journal | SIAM Journal on Computing |
Volume | 43 |
Issue number | 2 |
DOIs | |
State | Published - 2014 |
Keywords
- Combinatorial geometry
- Fat objects
- Union complexity
ASJC Scopus subject areas
- General Computer Science
- General Mathematics