Improved bounds for the union of locally fat objects in the plane

B. Aronov, M.T. Berg, de, E. Ezra, M. Sharir

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

20 Citaten (Scopus)
83 Downloads (Pure)

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-2Engels
Pagina's (van-tot)543-572
Aantal pagina's30
TijdschriftSIAM Journal on Computing
Volume43
Nummer van het tijdschrift2
DOI's
StatusGepubliceerd - 2014

Vingerafdruk Duik in de onderzoeksthema's van 'Improved bounds for the union of locally fat objects in the plane'. Samen vormen ze een unieke vingerafdruk.

Citeer dit