IMPROVED BOUNDS FOR INTERSECTING TRIANGLES AND HALVING PLANES

If a configuration of m triangles in the plane has only n points as vertices, then there must be a set of max ⌈ m (2n-5)⌉ ω(m3 (n6log2n)) triangles having a common intersection. As a consequence the number of halving planes for a three-dimensional point set is O(n8 3 log2 3 n). For all m and n there exist configurations of triangles in which the largest common intersection involves max ⌈ m (2n-5)⌉ O(m2 n3) triangles; the upper and lower bounds match for m = O(n2). The best previous bounds were ω(m3 n6 log5 n)) for intersecting triangles and O(n8 3 log5 3 n) for halving planes. © 1993.