Изменения

Перейти к: навигация, поиск

Алгоритм Бентли-Оттмана

2 байта добавлено, 10:47, 11 ноября 2011
Нет описания правки
==Реализация алгоритма==
===Двоичное дерево поиска в качестве статуса===
Из определения статуса ясно, какую структуру удобно использовать в качестве статуса: двоичное дерево поиска. В нем удобно делать все необходимые операции, и выполняться они будут за <tex>O(log_2(n))</tex>.
===Реализация множества необработанных событий===
====Приоритетная очередь====
Опять же, эта идея возникает в процессе описания этого множества. При этом понятно, что точки сравниваются сначала по абсциссе, в случае равенства - по ординате.
====Двоичное дерево поиска====
Анонимный участник

Навигация