Please note: Linked content is NOT stored on Carnegie Mellon University and we can't guarantee its availability, quality, security or accept any liability.
Geometric Intersection Problems
Any type of content formally published in an academic journal, usually following a peer-review process.
posted on 01.01.1976by John Louis Bentley, Michael I. Shamos
We investigate a divide-and-conquer technique in multidimensional space which decomposes a geometric
problem on N points in k dimensions into two problems on N/2 points in k dimensions plus a single problem
on N points in k-1 dimension. Special structure of the subproblems is exploited to obtain an algorithm
for finding the two closest of N points in O(N log N) time in any dimension. Related results are discussed,
along with some conjectures and unsolved geometric problems.