On the Duality of Intersections and Closest Points

Abstract

We call the common intersection of $k$ objects a $k$-intersection. We address questions of the form: Given $n$ objects in the plane, "Does there exist a $k$-intersection?", "How many such $k$-intersections exist?" and "What is the maximum value of $k$ for which there exists a $k$-intersection?". In answering such questions we utilize a duality that exists between $k$-intersections and and $k$-closest points (the $k$ points with the smallest enclosing circle), in that as long as $k$ points are close enough to be enclosed by a circle of radius $r$, the common intersection of $k$ circles of radius $r$ centered at each of those $k$ points (i.e. their $k$-intersection) is non-null. A technique, dubbed "rotation sorting" is then developed to provide efficient solutions to dual questions of the form: Given $n$ points in the plane, "Does there exist a set of $k$ points which can be covered by a circle of radius $r$?", "How many such sets of $k$ points exist?", and "What are the maximum number of points that can be enclosed by a circle of radius $r$?". A similar duality between the intersection of a line with circles and the proximity of this line to the centers of the circles is exploited to obtain efficient algorithms for the transversals of circles in the plane. Extensions of the above questions to three and higher dimensions are also addressed, along with problems concerning unequal sized objects. Further certain generalizations of $k$-intersections and of the number of points enclosed by $k$ objects in two dimensions and higher are shown to be NP-complete and $D^{p}$-complete.