Алгоритм прыжков и ходьбы - Jump-and-Walk algorithm

Прыгать и ходить является алгоритм для точка расположения в триангуляции (хотя большая часть теоретического анализа проводилась в 2D и 3D случайных Триангуляции Делоне ). Удивительно, но алгоритм не требует предварительной обработки или сложных структур данных, за исключением простого представления самой триангуляции. Предшественником Jump-and-Walk стали Лоусон (1977) и Грин и Сибсон (1978), которые выбирают случайную начальную точку S, а затем идут от S к точке запроса Q по одному треугольнику за раз. Но теоретический анализ этих предшественников был известен только после середины 1990-х годов.

Функция Jump-and-Walk выбирает небольшую группу точек выборки и начинает обход от точки выборки, которая является ближайшей к Q, до тех пор, пока не будет найден симплекс, содержащий Q. В течение некоторого времени алгоритм был фольклором на практике, и формальное представление алгоритма и анализ его производительности на случайной двумерной триангуляции Делоне был проведен Деврой, Маке и Чжу в середине 1990-х годов (статья появилась в Algorithmica, 1998). . Анализ трехмерной случайной триангуляции Делоне был проведен Mucke, Saias и Zhu (Симпозиум ACM по вычислительной геометрии, 1996). В обоих случаях предполагалось граничное условие, а именно, точка Q должна быть немного дальше от границы выпуклой области, где нарисованы вершины случайной триангуляции Делоне. В 2004 году Деврой, Лемер и Моро показали, что в 2D граничное условие может быть снято (статья появилась в Computational Geometry: Theory and Applications, 2004).

Jump-and-Walk использовался во многих известных программных пакетах, например, QHULL, Triangle и CGAL.

использованная литература

• Грин, П. Дж .; Сибсон, Р. (1978), "Вычисление мозаики Дирихле на плоскости", Компьютерный журнал, 21 (2): 168–173, Дои:10.1093 / comjnl / 21.2.168, Г-Н  0485467.
• Лоусон, К. (1977), "Программное обеспечение для интерполяции поверхности C1", в Райс, Дж. Р. (ред.), Математическое программное обеспечение III, Нью-Йорк: Academic Press, стр. 161–194..
• Деврой, Люк; Лемэр, Кристоф; Моро, Жан-Мишель (2004), «Расчет ожидаемого времени для определения местоположения точки Делоне», Вычислительная геометрия: теория и приложения, 29 (2): 61–89, Дои:10.1016 / j.comgeo.2004.02.002, Г-Н  2082208.
• Devroye, L .; Mücke, E.P .; Чжу, Биньхай (1998), "Заметка о местоположении точки в триангуляции Делоне случайных точек", Алгоритмика, 22 (4): 477–482, CiteSeerX  10.1.1.15.8612, Дои:10.1007 / PL00009234, Г-Н  1701623.
• Mücke, Ernst P .; Сайас, Исаак; Чжу, Биньхай (1999), «Быстрое рандомизированное определение местоположения точки без предварительной обработки в двух- и трехмерных триангуляциях Делоне», специальный выпуск для 12-го ACM Симпозиум по вычислительной геометрии (Филадельфия, Пенсильвания, 1996), Вычислительная геометрия: теория и приложения, 12 (1–2): 63–83, Дои:10.1016 / S0925-7721 (98) 00035-2, Г-Н  1677599.