Miniball to Matoušek-Sharir-Welzl algorithm | Hacker News Reader

Miniball to Matoušek-Sharir-Welzl algorithm

d3.express

80 pointsbased29 comments

I wanted to try a more naive/slow/sledge-hammer approach of just setting up the cost function and throwing it at an optimizer.

I couldn't get it to converge and I am not sure if it's just the library I am using being buggy (numeric.js) or my cost function is just bad.

Cost:

    const cost = (a, b) => {
      // If a encloses b, returns 0, otherwise a positive cost
      const dx = b.x - a.x;
      const dy = b.y - a.y;
      return Math.max(
        0,
        -a.r + (b.r + Math.sqrt(dx * dx + dy * dy))
      );
    }
    let iter = 0;
    const costAll = ([x, y, r]) => {
      // Cost of enclosing all balls (which should be 0) plus cost of radius (which should get us the smallest ball)
      const a = { x, y, r };
      const radiusCost = Math.abs(a.r);
      let encloseCost = 0;
      for (let i = 0; i < B.length; i++) {
        encloseCost += cost(a, B[i]);
      }  
      const totalCost = encloseCost + radiusCost;
      return totalCost;
    }

Demo:

https://codepen.io/anon/pen/ZyEaaQ?editors=0010

EDIT: demo should work correctly after mbostock's hint below!

To answer my own question, the problem seems to be that once it finds an enclosing circle it loses gradient on x and y so it doesn't know where to reposition the circle. Not sure how to fix this.

You can solve by finding the point <x, y> that minimizes the distance from any point in any input circle: \sqrt{(x_p - x) ^ 2 + (y_p - y) ^ 2} + r_p for p ∈ L. This is the center of the smallest enclosing circle. Once you have the center, you can iterate over every input circle to compute its radius.

That's clever! I updated the code and it seems to work for the several times I refreshed now. Thanks!

This was the final cost function that worked:

  let encloseCost = 0;  
  let farthestPointCost = 0;  
  for (let i = 0; i < B.length; i++) {
    const b = B[i];
    const dx = b.x - a.x;
    const dy = b.y - a.y;
    encloseCost += Math.max(
      0,
      -a.r + (b.r + Math.sqrt(dx * dx + dy * dy))
    );
    farthestPointCost = Math.max(
      farthestPointCost,
      b.r + Math.sqrt(dx * dx + dy * dy)
    );
  }
  const radiusCost = Math.abs(a.r);
  
  const totalCost = encloseCost + farthestPointCost + radiusCost;

A similar problem is also the smallest enclosing ball of a point set. A solver for that is available, implemented in C++ [0]. Both of these problems can be generalized to finding the sink of a unique sink orientation [1], so there is in fact a rich mathematical theory underlying all of this.

[0]: https://people.inf.ethz.ch/gaertner/subdir/software/miniball...

[1]: https://www.ti.inf.ethz.ch/ew/courses/ApproxGeom05/paper/fis...

Why can it only touch three circles? I can draw as many tangent circles as I want to for any given path.

The same reason that a table with three legs is always stable. If you add more legs it can begin to wobble depending on the smoothness of surface it stands on. The larger circle needs to touch three circles because if it touches any more two of those circles will be not change the larger circles if removed and are thus not necessary.

I'm not sure we're saying the same thing. I'm saying that it is not true that it can only touch three (or four, or any less-than-infinite number of circles). I think you're saying that only three of them are necessary to draw the correct circle.

The analogy would be that any three points on a plane describe both the vertices of exactly one triangle and exactly one circle circumscribing it (your statement) and that an infinite number of circumscribed triangles can be found for any nontrivial circle (my statement).

You can have more than three tangent circles, but three tangent circles are sufficient to represent an enclosing circle.

Reply on news.ycombinator.com