All Near Pairs

Research archive · original page Research.AllNearPairs · last recorded update 2010-02-25

allnearpairs.cc is a program to take a set of points in \(E^3\) and a fixed radius \(R\), and report all the point pairs within \(R\) .

allnearpairs is very fast. E.g., processing 20K points to find 688K pairs took 20msec, excluding I/O times, on a 2.8GHz machine. For a fixed number of points per point within the radius, the time is linear in the number of points. \( 10^6 \) points is easy.

Author

W. Randolph Franklin, Professor ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, 110 8th St, Troy NY, 12180 USA

wrf@ecse.rpi.edu +1 (518) 276-6077

http://wrfranklin.org/

Terms of use and acknowledgement

allnearpairs is free for nonprofit research and education. I would appreciate a credit, and the following acknowledgement:

-->This research was partially supported by NSF grant CMMI-0835762.

Offers of collaboration and co-authorships are always welcome. See my research page for ideas.

Usage

1. allnearpairs was written to test the algorithm, not as a packaged commercial product.
2. Parameters are set by editing the code and recompiling.
3. There is considerable debugging code.
4. Array sizes are set at compile time (for efficiency).
5. Algorithm:
6. Create a 3D uniform grid, of up to mg*mg*mg cells, with space for up to mpc points per cell.
7. Read the 3D points from a file, scale them to the range [0,1)'^3^', and insert each point into the appropriate cell.
8. Iterate through the cells, comparing all the points in each cell, pair by pair.
9. Write a file with the pairs.
10. User parameters to set in the code: