Tangencies between families of disjoint regions in the plane

Let C be a family of n convex bodies in the plane, which can be decomposed into k subfamilies of pairwise disjoint sets. It is shown that the number of tangencies between the members of C is at most O(kn), and that this bound cannot be improved. If we only assume that our sets are connected and vertically convex, that is, their intersection with any vertical line is either a segment or the empty set, then the number of tangencies can be superlinear in n, but it cannot exceed O(n log(2) n). Our results imply a new upper bound on the number of regular intersection points on the boundary of boolean OR C. Published by Elsevier B.V.

Published in:
Proc. Annual Symposium on Computational Geometry, 423-428

 Record created 2010-11-26, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)