ON THE DUALITY OF INTERSECTIONS AND CLOSEST POINTS
Original Publication Date: 1983-Aug-31
Included in the Prior Art Database: 2007-Mar-29
Software Patent Institute
Bajaj, C.: AUTHOR [+3]
0. TEX DUAJ.I'II OF IRIIISfCTIOHS MB CLOSEST POIEIS
0. TEX DUAJ.I'II OF IRIIISfCTIOHS
MB CLOSEST POIEIS
C.. Bajaj and M. L i TR 83-568
Department of Computer Science Cornell University
Ilthaca, New York 14853
research was supported in part by NSF grant MCS81-01220.
On the Duality of Intersections and Closest Points t Chanderjit Bajaj and Ming Li
Department of Computer Science, Cornell University, Ithaca, NY 14853.
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 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 them 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 1'.
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, alongwith problems concerning unequal sized objects. Further certain generalisations 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 DP-
t This research was supported in part by NSF grant MCS81-01220.
On the Duality of Intersections and Closest Points t
Chanderjit Bajaj and Ming Li
Department of Computer Science, Cornell University,
Ithaca, NY 14853.
This paper tries to relate questions about the intersection of objects with that involving the 'closeness' of points in a finite set. Calling the common inter- section of k objects a k-intersection we concern ourselves specifically with ques- tions of finding whether there exists a set of k objects, out of a finite set n, hav- ing a k-intersection? and the maximum value of k for which there exists such k-