For k>0 let f(k) denote the minimum integer f such that, for any family of k pairwise disjoint congruent disks in the plane, there is a direction α such that any line having direction α intersects at most f of the disks. We determine the exact asymptotic behavior of f(k) by proving that there are two positive constants d1, d2 such that d1√k √log k≤f(k)≤d2√k √log k. This result has been motivated by problems dealing with the separation of convex sets by straight lines.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics