Beemer (dr_tectonic) wrote,
Beemer
dr_tectonic

Math-ish blather

So, speaking of algorithms:

Does anyone know if you can prove that hill-climbing will work on a curvilinear grid?

Which is to say, I have a set of points that have the same combinatorial structure as a regular grid, though it may be all stretched out in lat/lon space. I want to find the point nearest to some target by starting at on point in the grid and repeatedly moving to the neighboring point that's closest to the target. This will work as long as there aren't any local minima in the distance field.

The question is, are there simple conditions under which you can be certain there aren't any local minima? Or certain that there are? Because it would be useful to check whether getting the right answer is guaranteed or not. (Of course, it has to be less work to check that condition than it would be to evaluate every candidate point, or there's no point in using a clever algorithm rather than the brute-force approach...)
Subscribe

  • The Dependency Principle and the Litany Against Fear

    Two thoughts on COVID-19: First, from Iain M. Banks' Excession: There was only one problem with the Land of Infinite Fun, and that was that if…

  • Ultravision

    I fell out of the habit of posting while work was so busy last fall, and now I've been feeling like I need to Say Something Important about my life…

  • Holiday Recovery

    I think, maybe, I am finally recovered from the end of 2019, which was exhausting. Basically, a bunch of work deadlines all converged, most of which…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 19 comments

  • The Dependency Principle and the Litany Against Fear

    Two thoughts on COVID-19: First, from Iain M. Banks' Excession: There was only one problem with the Land of Infinite Fun, and that was that if…

  • Ultravision

    I fell out of the habit of posting while work was so busy last fall, and now I've been feeling like I need to Say Something Important about my life…

  • Holiday Recovery

    I think, maybe, I am finally recovered from the end of 2019, which was exhausting. Basically, a bunch of work deadlines all converged, most of which…