Алгоритм прыжка и ходьбы

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

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

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

Ссылки

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