Здравствуйте, vadimcher, Вы писали:

S>>Это, конечно, замечательно, но оценка сложности верна для случая, когда точки разбросаны по карте более-менее равномерно. Для случая, когда они собраны в контура водоемов может быть ситуация, когда длинные сектора от выпуклой границы водоема идут под углом к x-y координатам. При этом по мин-макс координатам вокруг выбранной точки может оказаться до тысяч различных многоугольников и всех их придется перебирать, а это уже совсем не log(n).

V>Число многоугольников не может быть больше, чем число точек. Поэтому если поиск внутри полосы будет действительно log от числа многоугольников, имеющих с данной полосой общую область, то за logn мы никуда не вылезем.

А если поиск внутри полосы будет не за log(n)? Мы же при поиске в полосе находим все многоугольники, которые по второй координате захватывают выбранную точку. Таких многоугольников может быть довольно много (предположим, они идут в косую полоску по полосе, которая их во много раз шире).

Другая проблема такой схемы это то, что она выжирает квадратичное количество памяти. Полос у нас О(n), в каждой полосе может быть до O(n) многоугольников. Для сотен тысяч вершин это уже может быть серьезной проблемой.