Divide-and-conquer in multidimensional space | Zendy

Jon Bentley | Zendy; Michael Ian Shamos | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Divide-and-conquer in multidimensional space

Author(s) -

Jon Bentley,

Michael Ian Shamos

Publication year - 1976

Publication title -

citeseer x (the pennsylvania state university)

Language(s) - English

Resource type - Conference proceedings

DOI - 10.1145/800113.803652

Subject(s) - divide and conquer algorithms , dimension (graph theory) , space (punctuation) , computational geometry , mathematics , two dimensional space , computer science , combinatorics , algorithm , discrete mathematics , geometry , operating system

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 0(N log N) time in any dimension. Related results are discussed, along with some conjectures and unsolved geometric problems.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research