JavaScript is disabled for your browser. Some features of this site may not work without it.
On the Duality of Intersections and Closest Points

Author
Bajaj, Chanderjit; Li, Ming
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.
Date Issued
1983-08Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR83-568
Type
technical report