== Описание Решение методом полос==Сумма Минковского позволяет решать задачу Motion Planning, в случае[[Файл:cgslabs.png|200px|right]]Проведём через каждую вершину вертикальную прямую. Получим полосы (slabs). Пусть каждой полосе соответствует точка, когда робота нельзя поворачиватьчерез которую проведён левый край полосы. Таким образом, каждой точке Будем хранить отсортированный массив <tex>(x, y)</tex> ставится в соответствие фигура робота -координат, тогда за <tex>RO(x, y\log n)</tex>можно найти, с точкой привязки помещенной в точку какой полосе лежит <tex>(x, y)P</tex>.{{Определение|definition=Для заданного робота <tex>R</tex> и препятствия <tex>P</tex>В каждой полосе отрезки, '''К-препятствием''' называется множество точексоставляющие ППЛГ, будучи помещенным могут пересекаться только в концах, причём эти точки пересечения могут лежать только на прямых, ограничивающих полосы (по построению). Получается, что внутри каждой полосы можно отсортировать отрезки, которыележат в ней, например, робот заденет препятствие: снизу вверх. Тогда, найдя нужную полосу, можно быстро найти нужный отрезок. <tex>CP := \{==Персистентные деревья===Персистентные структуры данных — это структуры, боже царя хранящие историю своих изменений. Персистентность бывает полная (когда можем изменять любую версию) и частичная (xкогда можем изменить только последнюю версию, yно запросы можем делать на всех) : R. Один из способов сделать дерево частично персистентным — node-copying (xили path-copying, yв разных источниках по-разному) . Храним массив корней дерева. Когда нам нужно изменить ноду, мы создаём в этом массиве новый корень, но его поля left и right совпадают с таковыми в предыдущем корне. Далее мы идём от корня к ноде, которую хотим изменить. Все вершины по пути мы «копируем» так же, как и корень, при этом у предка меняем соответствующий указатель на новый. После этого мы меняем нужную нам ноду. Таким образом, для такого дерева нам нужно <tex>O(n \cap P \neq \varnothing\}log n)</tex>памяти. }}Можно усовершенствовать этот способ. Теперь в каждой ноде будет храниться номер версии и поля для ленивого изменения дерева: фиксированное количество запасных указателей left и right и номера версий для них. Когда мы хотим изменить ноду, вместо копирования записываем изменения в запасные указатели, если они ещё есть, иначе создаём новую ноду и соответственно исправляем её предка. Для поиска по версиям используем бинпоиск. Этот способ называется limited node copying, для него нужно O(n) памяти, потому что амортизированно за один апдейт копируем O(1) нод. ===Локализация в полосе===Воспользуемся сбалансированным частично персистентным деревом для хранения отрезков в полосах. Каждая полоса — это новая версия дерева.{{Определение|definition='''Суммой Минковского''' двух множеств =Время и память==На запрос нужно <tex>S_1 O(\subset R^2, S_2 \subset R^2log n)</tex> называется множество , на препроцессинг — <tex>S_1 O(n \oplus S_2 := \{p + q : p \in S_1, q \in S_2\}log n)</tex>, где ; памяти нужно <tex>p + qO(n)</tex> обозначает векторную сумму.}}{{Определение|definition==Алгоритм Киркпатрика=='''Отрицанием''' множества Существует ли метод локализации со временем поиска за <tex>S O(\subset R^2log n)</tex> называется множество <tex>, использующий менее чем квадратичную память? Эта задача оставалась не решенной довольно долго. Но все же была решена Липтоном и Тарьяном в 1977-S := \{-p : p \in S\}</tex>1980 гг. Но их метод оказался на столько громоздким, а оценки времени его эффективности содержат слишком большую константу, что сами авторы не считали этот метод практичным, но его существование заставляет думать, где что может найтись практичный алгоритм с временной оценкой <tex>-pO(\log n)</tex> обозначает векторное отрицаниеи линейной памятью.}}Недавно Киркпатриком был предложен оптимальный метод, дающий ответ на ожидания Липтона и Тарьяна, {{Теорема---}} детализация триангуляции.|statement=Для заданного робота ==Предобработка===<tex>R</tex> и препятствия <tex>P</texwikitex>[[Файл:кирк1.png|right|300px]]Пусть планарный N-вершинный граф задает триангуляцию нашего многоугольника (если это не так, К-препятствием является множество <tex>P то воспользуемся методом триангуляции многоугольника за время $O (n \oplus (log n)$. Напомним, что триангуляция на множестве вершин $V$ есть планарный граф с не более чем $3 |V| -R6$ ребрами (0, 0)[[Формула_Эйлера |формула Эйлера]]). Для удобства описания алгоритма поместим нашу триангуляцию в охватывающий треугольник и построим триангуляцию области между нашими объектами. После этого преобразования все триангуляции будут обладать тремя границами и ровно $3 |V| - 6$ ребрами.</texwikitex> ===Структура данных===<wikitex>[[Файл:кирк2.png|right|proof=300px]][[Файл:minkowski_sumкирк3.png | right | 150px300px]]Необходимо доказатьИтак, имеется N-вершинная триангуляция $G$, и пусть строится последовательность триангуляций $S_1, S_2, \dots, что робот <tex>RS_{h(xN)}$, где $S_1 = G$, yа $S_i$ получается из $S_{i - 1}$ по следующим правилам:* Шаг 1. Удалим некоторое количество неграничных и независимых (попарно несмежных друг с другом) вершин и инцидентные им ребра (от выбора этого множества напрямую зависит оптимальность алгоритма)</tex> пересекает препятствие <tex>P</tex> .* Шаг 2. Построить триангуляцию получившихся в том и результате шага 1 многоугольников.Таким образом $S_{h(N)}$ состоит из одного треугольника. Заметим, что все триангуляции имеют одну общую границу, так как удаляются только в том случаевнутренние узлы. Далее, будем обозначать все треугольники как $R$, а также будем говорить, что треугольник $R_ij$ принадлежит триангуляции $S_i$, если <tex>он был создан на шаге (x2) при построении этой триангуляции. Теперь построим структуру данных $T$ для поиска. Эта структура представляет собой направленный ацикличный граф, вершинами которого будут наши треугольники. Определим эту структуру следующим образом: из треугольника $R_k$ будет вести ребро в треугольник $R_j$, y) \in P \oplus (если при построении $S_i$ из $S_{i-1}$ мы имеем* $R_j$ удалятся из $S_{i -R1}$ на шаге (0, 01)* $R_k$ создается в $S_{i}$ на шаге (2)</tex>.* $R_j \cap R_k \ne \varnothing $
Пусть робот задевает препятствие, и точка <tex>q = (q_x , q_y)</tex> является точкой пересечения. Тогда, так как <tex>q \in R(x, y)</tex>, то <tex>(q_x - x, q_y - y) \in R(0,0)</tex>, или <tex>(x - q_x , y - q_y) \in -R(0,0)</tex>. А заметивОчевидно, что <tex>q \in P</tex>, получаем <tex>(x, y) \in P \oplus (-R(0,0))</tex>.В обратную сторону, пусть <tex>(x, y) \in P \oplus (-R(0,0))</tex>, тогда существуют точки <tex>треугольники из $S_1$ (r_x , r_y) \in R(0, 0)</tex> и <tex>(p_x , p_y) \in P</tex> такие, что <tex>(x, y) = (p_x - r_x , p_y - r_y)</tex> или <tex>(p_x , p_y) = (x + r_x , y + r_y)</tex>, а это означает, что <tex>R(x, yтолько они)</tex> пересекает <tex>P</tex>не имеют исходящих ребер.}}
ДопустимДля ясности удобно изобразить $T$ в рассмотренном виде, для простотыто есть помещая его узлы в горизонтальные строки, что робот каждая из которых соответствует какой-нибудь триангуляции. Последовательность триангуляций и все препятствия выпуклые, а позже обобщим для невыпуклых фигурсоответствующая ей структура $T$ показаны на рисунке. Треугольники пронумерованы в порядке их появления.{{Теорема|statement=Пусть заданы две выпуклые фигуры <tex>P</tex> и <tex>R</tex>Кружком обведены вершины, с числом вершин <tex>n</tex> и <tex>m</tex> соответственнокоторые удалены на данном шаге. Тогда суммой Минковского <tex>P \oplus R</texwikitex> является выпуклая фигура с не более чем <tex>m + n</tex> вершинами.|proof====Выбор множества удаляемых вершин====[[Файл:minkowski_extreme.png | right | 200px]]Для начала заметим, что любая крайняя точка в направлении вектора <texwikitex>\vecКак уже упоминалось, от выбора множества вершит триангуляции, которые будут удалены при построении $S_i$ по $S_{di-1}</tex> есть сумма крайних точек фигур в этом направлении$ существенно зависит эффективность метода. Убедиться Предположим, что можно выбрать это множество так, чтобы выполнялись следующие ''свойства'' ($N_i$ обозначает число вершин в этом можно спроецировав обе фигуры на вектор <tex>\vec{d}</tex>.$S_i$):
Теперь рассмотрим произвольное ребро <tex>e</tex> из <tex>P \oplus R</tex>'''Свойство 1'''. Оно является крайним в направлении к своей нормали$N_i = a_i N_{i-1}$, а значит оно образовано крайними точками фигур, и хотя бы у одной из фигур должно быть ребро, которое является крайним в этом направлении. Сопоставим <tex>e</tex> с этим ребром. Тогда сопоставив таким образом всем ребрам <tex>P где $a_i \oplus Rle a </tex> ребра исходных фигур1$ для $i = 2, получаем что всего ребер в <tex>P \oplus R</tex> не более чем <tex>m + n</tex>dots , так как каждое ребро исходных фигур использовалось не более разаh(N)$.}}
== Псевдокод == '''Свойство 2'''. Каждый треугольник $R_i \in S_i$ пересекается не более чем с $H$ треугольниками из $S_{i = j = 0-1}$ и наоборот. V[n] = V[0]Первое свойство немедленно влечет за собой следствие, V[n+что $h(N) \le \left \lceil \log_{1] /a}N \right \rceil = V[1], W[n] = W[0], W[n+1] = W[1] while i < n or j < m do add V[i]+W[j] to answer if angleO(V[i], V[i+1]log N) < angle(W[j], W[j+1]) ++i else if angle(V[i]$, V[поскольку при переходе от $S_{i+1]) > angle(W[j], W[j+-1]) ++j else ++i, ++jЗдесь множества точек <tex>V</tex> и <tex>W</tex> отсортированы в порядке обхода против часовой стрелки, причем первым элементом в обоих массивах является самая левая нижняя точка множества. Функция angle возвращает значение полярного угла вектора, заданного ее аргументами}$ к $S_i$ удаляется по меньшей мере фиксированная доля вершин.
Корректность алгоритма Также из этих свойств следует из доказательства предыдущей теоремы, а время работы равно <tex>что память для $T$ равна $O(n + mN)$. Действительно, заметим, что эта память используется для хранения узлов и указателей на их потомков. Из [[Формула_Эйлера|теоремы Эйлера]] о плоских графах следует, что $S_i$ содержит $F_i </tex>2N_i$ треугольников. Число узлов в $T$, представляющих треугольники из $S_i$, так как не превосходит $F_i$ (только те треугольники, которые действительно принадлежат $S_i$, появляются на каждой итерации хотя бы один из индексов <tex>i</tex> и <tex>j</tex> увеличиваетсясоответствующем «ярусе» $T$).Отсюда следует, что общее число узлов в $T$ меньше, чем== Случай невыпуклых фигур ==Для начала заметим следующий факт: <tex>S_1 $2(N_1 + N_2 + \oplus dots + N_{h(S_2 \cup S_3N) = (S_1 \oplus S_2}) \cup le 2N_1(S_1 1 + a + a^2 + \oplus S_3dots + a^{h(N) - 1})</tex>\frac{2N}{1 - a}$.Что касается памяти, используемой под указатели, то по свойству 2 каждый узел имеет не более $H$ указателей, поэтому не более $\frac{2NH}{1-a}$ указателей появится в $T$. Это доказывает последнее утверждение.
В Покажем теперь, что критерий выбора множества удаляемых вершин, удовлетворяющий вышеописанным свойствам, существует.{{Теорема|about=критерий выбора множества удаляемых вершин|statement=Если на шаге (1) построения последовательности триангуляции удалять несмежные вершины со степенью меньше некоторого целого (будет указано позже) числа $K$, то свойства, описанные выше, будут выполнены.|proof='''1. ''' Для проверки первого свойства воспользуемся некоторыми особенностями плоских графов. Из [[Формула_Эйлера | формулы Эйлера]] для плоских графов, в частном случаетриангуляции, ограниченной тремя ребрами, следует, когда одна что число вершин $N$ и число ребер $e$ связаны соотношением $e = 3N - 6$.Пока в триангнуляции есть внутренние вершины (в противном случае задача тривиальна), степень каждой из фигур невыпуклатрех граничных вершин не меньше трех. Поскольку существует $3N - 6$ ребер, а каждое ребро инцидентно двум вершинам, её сначала надо затриангулироватьто сумма степеней всех вершин меньше $6N$. Отсюда сразу следует, получив <tex>nчто не менее $ \frac{N}{2}$ вершин имеет степень меньше 12. Следовательно, пусть $K = 12$. Пусть также $v$ {{---}} число выбранных вершин. Поскольку каждой из них инцидентно не более $K-1 = 11$ ребер, а три граничные вершины не выбираются, то мы имеем $v \ge \left \lfloor \frac{1}{12}(\frac{N}{2</tex> треугольников} - 3) \right \rfloor $. После этогоСледовательно, уже известным алгоритмом$a \cong 1 - \frac{1}{24} < 0, надо построить 959 <tex>n-1$, что доказывает справедливость свойства 1.'''2</tex> выпуклых фигур . ''' Выполнение второго свойства обеспечивается тривиально. Поскольку удаление вершины со степенью меньше $K$ приводит к образованию многоугольника с числом ребер менее $K$, то каждый из удаленных треугольников пересекает не более чем <tex>m+3</tex> вершинами, которые будут суммами Минковского соответствующих $K - 2 = H$ новых треугольников. Объединение этих выпуклых фигур будет состоять из <tex>O(nm)}}</texwikitex> вершин.
В случае===Поиск===<wikitex>После построения структуры легко понять, как в ней происходит поиск. Элементарной операцией здесь является определение принадлежности треугольнику. Очевидно, что она выполняется константное время. Сначала мы локализуемся в треугольнике $S_1$. После этого мы строим путь от корневой вершины до листа следующим образом: находясь в какой-либо вершине $z$, просмотрим всех ее детей на принадлежность точки соответствующему треугольнику и, так как точка может находиться лишь в одном треугольнике конкретной триангуляции, перейдем в эту вершину, и продолжим поиск.Этот поиск также можно рассматривать как последовательную локализацию в триангуляциях $S_1, когда обе фигуры невыпуклы\dots, обе эти фигуры надо затриангулироватьS_{h(N)}$, получив <tex>n-2</tex> откуда и <tex>m-2происходит название самого метода.</texwikitex> треугольников соответственно. Построив суммы Минковского множеств этих треугольников получим ====Псевдокод====<texwikitex>Пусть все потомки узла $u$ из $T$ собраны в список successors(n-2u), а triangle(m-2u)обозначает треугольник, соответствующий узлу $u$. Тогда алгоритм поиска может выглядеть следующим образом: </texwikitex> выпуклых фигур, объединение которых состоит из <tex>O procedure localization(z) if (z not in triangle(root)) z in infinite region else u = root while (successors(u) != null) for (v in successors(u)) if (z in triangle(n^2m^2v))</tex> вершин. u = v return u
