Suppose I have a finite set of points distributed in a unit square. I can't access the point coordinates; instead, I can only specify a (point, radius) pair and see how many points fall inside that circle. I want to find a set of circles such that each point is in at least one circle, and no circle contains more than 1000 points. What's an efficient way to do this? E.g. a way that minimizes the expected number of (point, radius) searches?

I tried a recursive approach. E.g. f(point, radius) takes a circle and returns a set of smaller circles that cover it. Then recurse until each circle contains fewer than 1000 points. But there's not a straightforward (to me) way to choose the smaller circles in the recursive step.

Edit: Circles are allowed to overlap with each other / with the outside of the square.

CodePudding user response：

Assumption: When you pick a point and a radius, you get back a list of points that are in the containing circle. I.e., you know which points are covered by which circles.

If that's correct,then you can map out the approximate relative location of all points, after which answers to this

Here's a (cursorily tested) demo using that approach

class Circle {
  constructor(x,y,radius) {
    Object.assign(this, { x, y, radius })
    this.rSquared = radius*radius
  }

  contains(point) {
    let dx = point.x - this.x
    let dy = point.y - this.y
    return dx*dx   dy*dy < this.rSquared
  }

  draw() {
    ctx.beginPath();
    ctx.arc(this.x, this.y, this.radius, 0, 2 * Math.PI);
    ctx.stroke();  
  }

  subdivide() {
    const halfR = this.radius / 2.0
    const smallR = this.radius * Math.SQRT2 / 2.0

    return [
      new Circle(this.x-halfR, this.y-halfR, smallR),
      new Circle(this.x-halfR, this.y halfR, smallR),
      new Circle(this.x halfR, this.y-halfR, smallR),
      new Circle(this.x halfR, this.y halfR, smallR),
    ]
  }

}

// this class keeps a set of random points and answers countInCircle() 
// solutions may only call countInCircle() 
class Puzzler {
  constructor(count) {
    this.points = []

    for (let i=0; i<count; i  ) {
      let point = { x: Math.random()*width, y: Math.random()*height}
      this.points.push(point)
    }
  }

  // answer how many points fall inside circle
  countInCircle(circle) {
    return this.points.reduce((total, p) => total  = circle.contains(p) ? 1 : 0, 0);
  }

  drawSolution(circles) {
    this.points.map(p => ctx.fillRect(p.x,p.y,2,2))
    ctx.strokeStyle =  'lightgray'
    circles.forEach(circle => circle.draw())

    const counts = circles.map(circle => this.countInCircle(circle));
    console.log('circles:', circles.length)
    // console.log('counts:', counts.join(', '))
    // console.log('counts above 100:', counts.filter(c => c > 100).length)

    console.log('average count:', counts.reduce((a, b) => a   b) / counts.length)

    const uncovered = this.points.reduce((total, point) => {
      return total   (circles.some(circle => circle.contains(point)) ? 0 : 1)
    }, 0)
    console.log('uncovered points:', uncovered)
  }

}

// setup canvas
const canvas = document.getElementById('canvas')
const { width, height } = canvas
const ctx = canvas.getContext('2d')

// setup puzzle
const count = 1000
const maxCountPer = 100
const puzzler = new Puzzler(count, maxCountPer)

// begin with an encompasing circle, subdivide and solve recursively
// until all subdivided circles meet the count criterion
let r = width*Math.SQRT2/2
let c = new Circle(width/2.0, width/2.0, r)
let solution = solve(c);

function solve(circle) {
  let result = []
  let count = puzzler.countInCircle(circle)
  if (count > 0 && count <= maxCountPer) {
    result.push(circle);
  } else if (count > maxCountPer) {
    circle.subdivide().forEach(c => {
      result.push(...solve(c))
    })
  }
  return result
}

requestAnimationFrame(() => {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  puzzler.drawSolution(solution)
});

<h1>Circles Puzzle</h1>
 <canvas style="border: 1px solid gray;" id="canvas" height="800" width="800"></canvas>