The Heat Method for Distance Computation

Я много пишу о том как Машинное Обучение можно использовать в науке. Но справедливо и обратно.

В статье описывается метод для решения задачи поиска кратчайшего пути на поверхности с помощью использования уравнения распрстранения тепла (heat equation).

Вычисление расстояния можно разделить на два этапа: сначала найти направление, вдоль которого расстояние увеличивается, а затем вычислить само расстояние. Тепловой метод надежен, эффективен и прост в реализации, поскольку он основан на решении пары стандартных разреженных линейных систем. Эти системы могут быть разложены один раз и впоследствии решаться за почти линейное время.

Реальная производительность на порядок выше, чем у современных методов, при сохранении сопоставимого уровня точности. Метод может быть применен в любой размерности и на любой области, допускающей градиент и внутреннее произведение - включая регулярные сетки, треугольные сетки и облака точек.

Сайт проекта

#ScientificML #geometry