Skip to main content
Journal cover image

Fast spatial decomposition and closest pair computation for limited precision input

Publication ,  Journal Article
Reif, JH; Tate, SR
Published in: Algorithmica (New York)
November 1, 2000

In this paper we show that if the input points to the geometric closest pair problem are given with limited precision (each coordinate is specified with O(log n) bits), then we can compute the closest pair in O (n log log n) time. We also apply our spatial decomposition technique to the k-nearest neighbor and n-body problems, achieving similar improvements. To make use of the limited precision of the input points, we use a reasonable machine model that allows "bit shifting" in constant time -We believe that this model is realistic, and provides an interesting way of beating the Ω(n log n) lower bound that exists for this problem using the more typical algebraic RAM model.

Duke Scholars

Published In

Algorithmica (New York)

DOI

ISSN

0178-4617

Publication Date

November 1, 2000

Volume

28

Issue

3

Start / End Page

271 / 287

Related Subject Headings

  • Computation Theory & Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Tate, S. R. (2000). Fast spatial decomposition and closest pair computation for limited precision input. Algorithmica (New York), 28(3), 271–287. https://doi.org/10.1007/s004530010040
Reif, J. H., and S. R. Tate. “Fast spatial decomposition and closest pair computation for limited precision input.” Algorithmica (New York) 28, no. 3 (November 1, 2000): 271–87. https://doi.org/10.1007/s004530010040.
Reif JH, Tate SR. Fast spatial decomposition and closest pair computation for limited precision input. Algorithmica (New York). 2000 Nov 1;28(3):271–87.
Reif, J. H., and S. R. Tate. “Fast spatial decomposition and closest pair computation for limited precision input.” Algorithmica (New York), vol. 28, no. 3, Nov. 2000, pp. 271–87. Scopus, doi:10.1007/s004530010040.
Reif JH, Tate SR. Fast spatial decomposition and closest pair computation for limited precision input. Algorithmica (New York). 2000 Nov 1;28(3):271–287.
Journal cover image

Published In

Algorithmica (New York)

DOI

ISSN

0178-4617

Publication Date

November 1, 2000

Volume

28

Issue

3

Start / End Page

271 / 287

Related Subject Headings

  • Computation Theory & Mathematics