Carnegie Mellon University
Browse

File(s) stored somewhere else

http://euro.ecom.cmu.edu/shamos.html

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

journal contribution
posted on 1976-01-01, 00:00 authored by 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.

History

Publisher Statement

All Rights Reserved

Date

1976-01-01

Usage metrics

    Categories

    Keywords

    Software Research

    Licence

    In Copyright

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC