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

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

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

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

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

Как это будет не за log(n)? Если у тебя n точек на прямой, заранее известных, сможешь поиск за log(n) организовать? Ну и тут то же самое, только упорядоченные пересечения выпуклых многоугольников с полоской, каждое пересечение -- трапеция, верхняя и нижняя часть задаются уравнением линии, строится дерево, в котором в каждом узле проверяем, выше мы данной линии или ниже. Можно еще ускорить дополнительной проверкой, не попали ли мы сразу в трапецию выше или ниже данной прямой. Можно устроить двоичное дерево, в котором в каждом узле проверяется не то, выше ли ли мы данного отрезка-стороны-трапеции или ниже, а принадлежит ли данная точка данной трапеции (сравнение в двумя прямыми сторонами -- верхней и нижней -- трапеции, т.е. два умножения и два сложения) или он выше или ниже ее, т.е. двоичный поиск трапеций. Но в любом случае, как вылезти за пределы log(n) не представляю себе.

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

В реальности -- не может. Это же не просто какие-то многоугольникии какие-то полосы. Многоугольника Вороного, а полосы построены через их вершины. Если у тебя и будет полоса с O(n) трапеций, то O(n) оставшихся полос будут иметь O(1) трапеций. Что касается памяти, то здесь ее уж точно требуется гораздо меньше, чем для любых приемлемых сеток, например.