"place specimens on the grid at randomly selected points until no more can be placed: "no more" because each specimen has a neighborhood radius r_i such that no other specimens may be placed within that radius."

circles.js

function initialiseGrid(w, h) {
  // first get all the initial max radii
  let temp = []
  for (let x = 0; x < w; x++) {
    for (let y = 0; y < h; y++) {
      let k = JSON.stringify([x, y])
      temp.push([k, Math.min(x, y, w-x, h-y)])
    }
  }
  // now shuffle, so that we do not need to filter
  // and shuffle later to find a random point. If
  // we don't do this, the points will be in insertion order.
  let i = temp.length;
  while (--i > 0) {
    let randIndex = Math.floor(Math.random() * (i + 1));
    [temp[randIndex], temp[i]] = [temp[i], temp[randIndex]];
  }
  // now store these in grid.
  return Object.fromEntries(temp)  
}

function pickCircle(r) {
  // because of the way we constructed the grid above,
  // the keys are returned in a random order, and we
  // can just peel off the first matching point.
  let p = Object.keys(grid).find(k => grid[k] >= r);
  if (!p) {
    return null
  }
  return JSON.parse(p)
}

function addCircle(x, y, r) {
  let seen = {}
  let q = [[x, y]]
  let k = JSON.stringify(x, y)
  seen[k] = 1
  let rr = r * r
  while (q.length > 0) {
    [x1, y1] = q.pop()
    // stringifying would not be necessary in python.
    let k = JSON.stringify([x1, y1])
    if (!Object.hasOwn(grid, k)) {
      // can occur if point was removed
      continue
    }
    let r1 = sqrt((x1 - x)*(x1 - x) + (y1 - y)*(y1 - y))
    let rmax = Math.max(r1 - r, 0)
    if (grid[k] > rmax) {
      if (rmax == 0) {
        delete grid[k]
      } else {
        //fill(max(255, 10*(20-rmax)))
        //point(x1, y1)
        grid[k] = rmax        
      }
      for (let i = -1; i <= 1; i++) {
        for (let j = -1; j <= 1; j++) {
          if (i ==0 && j==0) {
            continue
          }
          let k2 = JSON.stringify([x1 + i, y1 + j])
          if (Object.hasOwn(grid, k2) && !Object.hasOwn(seen, k2)) {
            seen[k2] = 1
            q.push([x1 + i, y1 + j])
          }
        }
      }
    }    
  }
}

let grid = {}
let done = false

function setup() {
  createCanvas(400, 400);
  grid = initialiseGrid(400, 400)
}


function draw() {
  if (done) {
    return
  }
  // allowing r to reach the max radius (200), this stops
  // quite quickly as the chance of picking a circle
  // you can't place is high.
  let r = Math.random() * 20;
  let p = pickCircle(r)
  if (!p) {
    console.log("Cannot place circle radius", r) 
    done = true
    return
  }
  let [x, y] = p;
  addCircle(x, y, r)
  fill(255)
  circle(x, y, 2*r)
}

An attempt at Greg Wilson's problem here https://hachyderm.io/@[email protected]/114325906599614671

I have a discrete NxN grid and a potentially infinite supply of specimens. I want to place specimens on the grid at randomly selected points until no more can be placed: "no more" because each specimen has a neighborhood radius r_i such that no other specimens may be placed within that radius. (Different specimens have different r_i.) I have a brute-force algorithm for doing this with O(N^3) running time. Is there a better one? I value simplicity over speed, and pseudocode or Python over either.

The algorithm above can be pasted into https://editor.p5js.org/ to run it. The problem's a little ambiguous, I took it to mean there is an incoming list of random radii, and I continue placing specimens randomly until one comes in that I cannot place.

It works by keeping a dict of all the grid points that are not yet excluded from having an item placed. The value in the dict is the max radius of a circle that can be placed at that point. JS stores dicts in insertion order, and I want to pick points at random; so when initialising the grid, I shuffle the points first, that way when I come to "picking a random point where a circle radius r can be placed" I can just pick the first match rather than finding all matches then randomising again.

Once I've picked a random point, I flood fill outwards from the centre, looking for points where the max radius has been reduced because of the new specimen. If the max radius is 0 (ie inside the exclusion radius of the new point) I drop it from the list to speed up later comparisons.

What's the complexity? Not sure, but it feels better than O(N^3)? All of the scans cut off early and accelerate as circles are added

This is an alternative implementation using spatial hashing, which is just a fancy way of saying, divide into a grid and only test nearby cells for collisions

function addCircle(r, attempts) {
  for (let i = 0; i < attempts; i++) {
    let x = Math.random() * 400;
    let y = Math.random() * 400;
    // a larger gridsize means more collisions to test.
    let gridsize = 400/10
    let cxmin = Math.floor((x - r) / gridsize);
    let cxmax = Math.floor((x + r) / gridsize);
    let cymin = Math.floor((y - r) / gridsize);
    let cymax = Math.floor((y + r) / gridsize);
    let pass = true
    for(let cx = cxmin; pass && cx <= cxmax; cx++) {
      for(let cy = cymin; pass && cy <= cymax; cy++) {
        let k = JSON.stringify([cx, cy])
        if (!Object.hasOwn(grid, k)) {
          continue
        }
        pass = grid[k].every(p => {
          let [x1, y1, r1] = p
          let r2 = sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y))
          return r2 >= r1 + r
        })
      }
    }
    if (pass) {
      circle(x, y, 2*r)
      for(let cx = cxmin; cx <= cxmax; cx++) {
        for(let cy = cymin; cy <= cymax; cy++) {
          let k = JSON.stringify([cx, cy])
          let items = grid[k] ?? [];
          items.push([x, y, r])
          grid[k] = items          
        }
      }
      return true
    }
  }
  return false
}

let grid = {}
let done = false

function setup() {
  createCanvas(400, 400);
  //saveGif("circles", 5)
}


function draw() {
  if (done) {
    return
  }
  let r = Math.random() * 4 + 1;
  let attempts = 1000
  done = !addCircle(r, attempts)
  if (done) {
    console.log("Cannot place circle radius", r, "after", attempts, "attempts") 
    return
  }
}