10.1184/R1/6622361.v1
John Louis Bentley
John Louis
Bentley
Michael I. Shamos
Michael I.
Shamos
Geometric Intersection Problems
Carnegie Mellon University
1976
Software Research
1976-01-01 00:00:00
Journal contribution
https://kilthub.cmu.edu/articles/journal_contribution/Geometric_Intersection_Problems/6622361
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.