228
правок
Изменения
→Постановка задачи
Трапецоидная карта {{---}} геометрическая структура позволяющая локализоваться на площади за <tex>\mathcal{O}(\log(n))</tex>.
==Постановка задачи==
<wikitex>
{{Определение
|id=arrangement
'''Сторона''' (англ. ''facet'') — ячейка размерности d-1.
}}
</wikitex>Предположим, у нас есть наши координаты, и есть карта мирадвумерная конфигурация. Наша задача выдать грань содержащую точку. Пусть каждая грань конфигурации является трапецоидом. Тогда каждая грань однозначно задается двумя отрезками ограничивающими эту грань(боковые стороны трапеции).Таким образом задача локализации точки сводится к тому, что нужно выдать два отрезка между которыми находится точка.
Мы можем найти по карте наше местоположение и сказать в какой стране мы находимся.
Области задаются замкнутыми ломаными. '''Формальная постановка задачи''' Есть множество отрезков на плоскости.Есть запрос (точка <tex>q</tex>), на выходе {{---}} область, в которой находится точка <tex>q</tex>.
==Структура данных==
