Closest-point problems simplified on the RAM
Timothy M. Chan · 2002
Basic proximity problems for low-dimensional point sets, such as closest pair (CP) and approximate nearest neighbor (ANN), have been studied extensively in the computational geometry literature, with well over a hundred papers published (we merely cite the survey by Smid [10] and omit most references). Generally, optimal algorithms designed for worst-case input require hierarchical spatial structures with sophisticated balancing conditions (we mention, for example, the BBD trees of Arya et al., balanced quadtrees, and Callahan and Kosaraju's fair-split trees); dynamization of these structures is even more involved (relying on Sleator and Tarjan's dynamic trees or Frederickson's topology trees). In this note, we point out that much simpler algorithms with the same performance are possible using standard, though nonalgebraic, RAM operations. This is interesting, considering that nonalgebraic operations have been used before in the literature (e.g., in the original version of the BBD tree [2], as well as in various randomized CP methods). The CP algorithm can be stated completely in one paragraph. Assume coordinates are positive integers bounded by U = 2 w. Given a point p in a constant dimension d where the i-th coordinate p i is the number p iw p i0 in binary, dene its shue (p) to be the number p 1w pdw p 10 p d0 in binary, and dene shifts i (p) = (p 1 + bi2