Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. On the Duality of Intersections and Closest Points

On the Duality of Intersections and Closest Points

File(s)
83-568.ps (260.38 KB)
83-568.pdf (1.28 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6408
Collections
Computer Science Technical Reports
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-08
Publisher
Cornell University
Keywords
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

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance