228
правок
Изменения
→Случай коллизии
<tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex>.
==Случай коллизии==
Рассмотрим момент, когда мы мы строим карты. Мы должны добавить очередной отрезок.
Предположим, левый конец отрезка лежит на одной вертикале с уже добавленной в карту точкой <tex> p </tex>.
Скажем, что наша точка лежит правее чем та которая уже есть. В случаи если мы попали на уже созданный отрезок мы скажем, что находимся например ниже его.
Что при этом произойдет.
*С геометрической точки зрения появится еще несколько трапецоидов как в случааи если бы вновь добавленная точка была правее на <tex> \varepsilon \rightarrow 0</tex>.
А значит, что у трапецоида по прежнему не более двух правых соседей.
*С точки зрения поисковой структуры мы по прежнему можем локализоваться. По крайней мере узел соответствующий точке <tex> p </tex> будет иметь правого сына нашу точку.
Итого, слова "трапецоидные карты просты отсутствие случаев" появляются именно отсюда, так как казалось бы неприятный случай будет прописан заменой <tex>\textless </tex>
на <tex> \le </tex>
==Асимптотика==
