Алгоритм прыжка и ходьбы
-
Обзор алгоритма Jump-and-Walk
- Алгоритм используется для определения местоположения точки в триангуляциях Делоне.
- Не требует предварительной обработки данных, кроме простого представления триангуляции.
- Предшественники метода — Лоусон (1977) и Грин и Сибсон (1978), но их теоретический анализ был выполнен позже.
- Jump-and-Walk выбирает группу точек выборки и обходит их, пока не найдет симплекс с заданной точкой запроса.
- Алгоритм был широко распространен на практике и получил теоретическое обоснование в середине 1990-х.
- В 2004 году было показано, что граничное условие для нахождения точки запроса может быть снято.
-
Практическое применение
- Jump-and-Walk использовался в известных программных пакетах, таких как QHULL, Triangle и CGAL.
-
Рекомендации по форматированию
- В статье приведены рекомендации по форматированию библиографических описаний и HTML-кода.