Nearest Fibonacci sphere points

Question

I have n points on a unit sphere (n up to 10^9). I need to find nearest approximations of these points by n_samples Fibonacci sphere points (n_samples in my case is 65536).

I.e. for each input point, I need to find index i_sample of the nearest Fibonacci point.

What's a good way to do it in less than O(n * n_samples) operations?

Answer 1

One approach is to use a KD-tree data structure to efficiently search for the nearest neighbor in the set of Fibonacci sphere points

Here is a sample algorithm to do this:

// Define the Fibonacci sphere points
const n_samples = 65536;
const phi = (1 + Math.sqrt(5)) / 2; // Golden ratio
const inc = Math.PI * (3 - Math.sqrt(5));
const points = [];
for (let i = 0; i < n_samples; i++) {
  const y = 1 - (i / (n_samples - 1)) * 2; // Map to [-1, 1]
  const r = Math.sqrt(1 - y * y);
  const theta = i * inc;
  const x = Math.cos(theta) * r;
  const z = Math.sin(theta) * r;
  points.push([x, y, z]);
}

// Define a function to find the nearest Fibonacci point to a given point on the sphere

function findNearestFibonacciPoint(point) {
  // Define a KD-tree using the Fibonacci sphere points
  const tree = new kdTree(points, distance, ['x', 'y', 'z']);

  // Define a distance function that calculates the great-circle distance between two points
  function distance(a, b) {
    const dot = a.x * b.x + a.y * b.y + a.z * b.z;
    const angle = Math.acos(Math.min(dot, 1));
    return angle;
  }

  // Find the nearest Fibonacci point to the input point
  const nearest = tree.nearest({
    x: point[0],
    y: point[1],
    z: point[2]
  }, 1);
  const i_sample = nearest[0][0];
  return i_sample;
}

// Find the nearest Fibonacci point to each input point
function findNearestFibonacciPoints(inputPoints) {
  const n = inputPoints.length;
  const nearestPoints = new Array(n);
  for (let i = 0; i < n; i++) {
    nearestPoints[i] = findNearestFibonacciPoint(inputPoints[i]);
  }
  return nearestPoints;
}

// Define the Fibonacci sphere points
const n_samples = 65536;
const phi = (1 + Math.sqrt(5)) / 2; // Golden ratio
const inc = Math.PI * (3 - Math.sqrt(5));
const points = [];
for (let i = 0; i < n_samples; i++) {
  const y = 1 - (i / (n_samples - 1)) * 2; // Map to [-1, 1]
  const r = Math.sqrt(1 - y * y);
  const theta = i * inc;
  const x = Math.cos(theta) * r;
  const z = Math.sin(theta) * r;
  points.push([x, y, z]);
}

// Define a function to find the nearest Fibonacci point to a given point on the sphere

function findNearestFibonacciPoint(point) {
  // Define a KD-tree using the Fibonacci sphere points
  const tree = new kdTree(points, distance, ['x', 'y', 'z']);

  // Define a distance function that calculates the great-circle distance between two points
  function distance(a, b) {
    const dot = a.x * b.x + a.y * b.y + a.z * b.z;
    const angle = Math.acos(Math.min(dot, 1));
    return angle;
  }

  // Find the nearest Fibonacci point to the input point
  const nearest = tree.nearest({
    x: point[0],
    y: point[1],
    z: point[2]
  }, 1);
  const i_sample = nearest[0][0];
  return i_sample;
}

// Find the nearest Fibonacci point to each input point
function findNearestFibonacciPoints(inputPoints) {
  const n = inputPoints.length;
  const nearestPoints = new Array(n);
  for (let i = 0; i < n; i++) {
    nearestPoints[i] = findNearestFibonacciPoint(inputPoints[i]);
  }
  return nearestPoints;
}