We show that, for any fixed δ > 0, the combinatorial complexity of the union of a triangles in the plane, each of whose angles is at least δ, is O(n2α(n) log* n). with the constant of proportionality depending oil δ. This considerably improves the twenty-year-old bound O(n log log n), due to Matoušek et al. [24, 25].
|Original language||English (US)|
|Title of host publication||Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011|
|Publisher||Association for Computing Machinery|
|Number of pages||8|
|State||Published - 2011|
|Name||Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms|
ASJC Scopus subject areas