Кратчайший путь в условиях препятствий

[lonelyass]

Препод задал сделать как лабу весьма сложную задачу и я сильно сомневаюсь, что она имеет решение за $log(N)$.

Итак, есть препятствия, заданные как многоугольники произвольной формы. Для них можно провести подготовительные вычисления.
Далее задаются две точки вне препятствий и нужно найти кратчайший путь между ними за $log(N)$, где N - количество вершин. При этом разрешается использовать только $O(N*log(N))$ памяти.


Я умею решать эту задачу с намного худшей оценкой:
1) на этапе предподготовки нахожу кратчайшие пути между всеми вершинами препятствий, на это уходит $O(N^3)$ времени (алгоритм Флойда-Уоршалла) и в конечном итоге нужно занимать $O(N^2)$ памяти.
2) для обеих заданных точек за $O(N)$ нахожу прямые расстояния до всех точек препятствий, выходят два массива размера N (fromstart, fromfinish)
3) за $O(N^2)$ нахожу $argmin_{i,j}(fromstart[i] + mindistance[i,j] + fromfinish[j])$
Как видите, оценки крайне далеки от требуемых, возможно я туплю на этапе 3) и этот поиск можно сделать хотя бы за $N*log(N)$

Что касается запроса за $log(N)$, я вообще не представляю как это возможно. Искал в книге Рурка, так и не смог разобраться, там много разных задач с похожей формулировкой и разными оценками, к тому же решений всё равно нет. Чувствую, что если это и можно сделать за $log(N)$, задание всё равно слишком сложное и объемное как для "просто лабы". Кто что-то знает по теме? Подскажите что почитать, пожалуйста.

[venco]

Что-то мне кажется, что это невозможно сделать за $O(\log N)$.
Может препод ошибся и имеется в виду $O(N\log N)$?