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

.
Итак, есть препятствия, заданные как многоугольники произвольной формы. Для них можно провести подготовительные вычисления.
Далее задаются две точки вне препятствий и нужно найти кратчайший путь между ними за

, где N - количество вершин. При этом разрешается использовать только

памяти.
Я умею решать эту задачу с намного худшей оценкой:
1) на этапе предподготовки нахожу кратчайшие пути между всеми вершинами препятствий, на это уходит

времени (алгоритм Флойда-Уоршалла) и в конечном итоге нужно занимать

памяти.
2) для обеих заданных точек за

нахожу прямые расстояния до всех точек препятствий, выходят два массива размера N (fromstart, fromfinish)
3) за

нахожу
![$argmin_{i,j}(fromstart[i] + mindistance[i,j] + fromfinish[j])$ $argmin_{i,j}(fromstart[i] + mindistance[i,j] + fromfinish[j])$](https://dxdy-02.korotkov.co.uk/f/d/f/5/df5078e06422292a50b26db2c70f25f982.png)
Как видите, оценки крайне далеки от требуемых, возможно я туплю на этапе 3) и этот поиск можно сделать хотя бы за

Что касается запроса за

, я вообще не представляю как это возможно. Искал в книге Рурка, так и не смог разобраться, там много разных задач с похожей формулировкой и разными оценками, к тому же решений всё равно нет. Чувствую, что если это и можно сделать за

, задание всё равно слишком сложное и объемное как для "просто лабы". Кто что-то знает по теме? Подскажите что почитать, пожалуйста.