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

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

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

V>Кстати, если у тебя информация представлена в виде карты, и есть возможность впихнуть дополнительную информацию в карту (например, под каждую точку карты выделено 4 байта, а палитру можно снизить до 65536 цветов, т.е два старших байта каждой точки использовать в личных целях), то можно сразу запомнить для каждой точки карты номер ближайшей к ней точки ближайшего водоема. Тогда поиск O(1).

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