Алгоритм прыжка и ходьбы
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 , Нью-Йорк: 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, doi : 10.1016/S0925-7721(98)00035-2 , MR 1677599 .