Local minimum function getting stuck not at minimum

Question

Summary
My simple function performing a binary search for a local minimum often returns spurious values corresponding to exactly ¼, ½, and ¾ of the search. Why is this happening?

/**
 * minX  : the smallest input value
 * maxX  : the largest input value
 * ƒ     : a function that returns a value `y` given an `x`
 * ε     : how close in `x` the bounds must be before returning
 * return: the `x` value that produces the smallest `y`
 */
function localMinimum(minX, maxX, ƒ, ε) {
    if (ε===undefined) ε=1e-15;
    let m=minX, n=maxX, k;
    while ((n-m)>ε) {
        k = (n+m)/2;
        if (ƒ(m)<ƒ(n)) n=k;
        else           m=k;
    }
    return k;
}

Live Demo: http://phrogz.net/svg/closest-point-on-bezier_broken.html

The demo lets you adjust a cubic Bézier curve, move the mouse around, and attempts to find a point on the curve closest to the mouse location. In the screenshots below, you can see the curve (black), the location of the mouse (centered in the gray circle), the location found on the curve (red dot), a brute-force graph of the distance from the cursor to each point on the curve (lower right corner), and the t parameter that was calculated as the local minimum (red text).

These screenshots represent the worst case. In them the mouse location is very close to the line, and the "local minimum" function is returning a point that is NOT the local minimum. If you experiment with the demo, you will see that in many cases the local minimum function is working as intended. Just…not near some of the early binary search bounds.

Guide to the Code
The localMinimum() function (line 225) is called by the closestPoint() function (line 194):

/**
 * out   : A vmath vector to modify with the point value
 * curve : Array of vectors as control points for a Bézier curve (any degree)
 * pt    : Object with .x/.y to find the point closest to
 * return: A parameter t representing the location of `out`
 */
function closestPoint(out, curve, pt, tmps) {
    let vec=vmath[ 'w' in curve[0] ? 'vec4' : 'z' in curve[0] ? 'vec3' : 'vec2' ];
    return localMinimum(0, 1,
      t => vec.squaredDistance(pt, bézierPoint(out, curve, t)));
}

The bézierPoint() function (line 207) uses De Casteljau's algorithm to calculate a point along the curve parameterized by t. This function works as expected, tested independently of the rest of the problem.

The squaredDistance() function is part of the vmath library, and is as simple as you would imagine.

What am I missing? How is my local minima function failing?

Answer 1

I had this very same problem using a different set of functions to find closest point on the curve.

The progressive search

function localMinimum(minX, maxX, ƒ, ε) {
    if (ε===undefined) ε=1e-15;
    let m=minX, n=maxX, k;
    while ((n-m)>ε) {
        k = (n+m)/2;
        if (ƒ(m)<ƒ(n)) n=k;
        else           m=k;
    }
    return k;
}

is at fault as it will close in on the wrong local. From memory it is the derivative (or second derivative) of the curve that is the distance from the point that will show an inflection point where you are getting the wrong result. In other words at that part of the curve it moves closer and closer to your point and then starts to move away. The search function assume that this inflection point is the point you are looking for.

The solution is systematic search (at some resolution) then a progressive search for the final result.

Answer 2

As so often happens, the moment you take the time to write up a question, the answer becomes obvious. My localMinimum() function was flawed.

If we look at the graph for the third example above and draw a line from the maximum point, we see that it is on the right side:

The way the algorithm (as shown above) is written, it immediately throws away the right half of the graph and focuses on the left. From that point on, it is doomed. It keeps moving the left bound toward the right at 0.5, but is never allowed to move the right again.

Here is a fixed version of the localMinimum() function, employing a bit of a hack. Given any bounds, it finds the spot in the middle, and then steps to the left and right "slightly" (as determined by the ε parameter) and decides which half to keep based on that.

/**
 * minX  : the smallest input value
 * maxX  : the largest input value
 * ƒ     : a function that returns a value `y` given an `x`
 * ε     : how close in `x` the bounds must be before returning
 * return: the `x` value that produces the smallest `y`
 */
function localMinimum(minX, maxX, ƒ, ε) {
    if (ε===undefined) ε=1e-10;
    let m=minX, n=maxX, k;
    while ((n-m)>ε) {
        k = (n+m)/2;
        if (ƒ(k-ε)<ƒ(k+ε)) n=k;
        else               m=k;
    }
    return k;
}

I've uploaded a fixed version of the demo to:http://phrogz.net/svg/closest-point-on-bezier.html