Loading...
conference paper
Tangencies between families of disjoint regions in the plane
2010
Proc. Annual Symposium on Computational Geometry
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.
Type
conference paper
Web of Science ID
WOS:000281594400052
Authors
Publication date
2010
Published in
Proc. Annual Symposium on Computational Geometry
Start page
423
End page
428
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
November 26, 2010
Use this identifier to reference this record