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

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

V>>Остается вопрос поиска многоугольника Вороного для заданной точки. Как вариант, можно упорядочить все расчитанные вершины многоугольников по оси x, для двух соседних значений x хранить список многоугольников, попавших в вертикальную полосу между ними, и для каждого многоугольника в таком списке хранить минимальную и максимальную координаты по y. Тогда поиск полосы -- log(n), поиск многоугольника log от числа многоугольников в полосе.

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

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

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