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

*allnearpairs*was written to test the algorithm, not as a packaged commercial product.- Parameters are set by editing the code and recompiling.
- There is considerable debugging code.
- Array sizes are set at compile time (for efficiency).

- Algorithm:
- Create a 3D uniform grid, of up to
*mg*mg*mg*cells, with space for up to*mpc*points per cell. - Read the 3D points from a file, scale them to the range [0,1)
^{3}, and insert each point into the appropriate cell. - Iterate through the cells, comparing all the points in each cell, pair by pair.
- Write a file with the pairs.

- Create a 3D uniform grid, of up to
- User parameters to set in the code:
*mp*Max number of input points *r*Radius of interest *scale*Scale factor to multiply the input coordinates by to reduce them to the range [0,1). *mg*Max allowable grid resolution. *mpc*Max allowable number of points per cell. *mpcc*Max allowable number of near pairs. - How to compile: g++ -O3 -o allnearpairs allnearpairs.cc
- The input file is called
*points*and has the format: x y z

x y z

... - The output file is called
*pairs*. Each line is one point pair, with these entries, in fixed-width columns for easy post-processing.- 1st point number in points file, indexed from 0
- 2nd ...
- 1st point coordinates
- 2nd ...
- Square of the distance