вопрос

From

Mihail S. Sidorenko (2:5030/744.237)

To

All

Date

2002-05-17T17:54:50Z

Area

RU.ALGORITHMS

Привет, All!

Возникла такая задача, может, кто подскажет, какие могут быть идеи по этому поводу?

Есть множество пронумерованных несовпадающих друг с другом точек на плоскости, заданных своими координатами X и Y, всего N точек. Каждой точке сопоставленно число 1..M, M < N. Две точки считаются одинаковыми тогда и только тогда, когда сопоставленные им числа равны. "Фигурой" называется подмножество точек, не имеющее общих точек ни с одной заданной ранее таким образом фигурой. Фигуры считаются одинаковыми тогда и только тогда, когда их можно совместить друг с другом при помощи некоторых стандартных преобразований на плоскости, причём, возможно, не точно совместить все одинаковые соответствующие точки двух фигур, а в некоторой эпсилон-окрестности. Под стандартными преобразованиями понимаются сдвиг по осям и независимое линейное изменение масштаба по осям; поворот и отражение не рассамтриваются. Требуется найти максимальное число самых больших одинаковых фигур.

Общее число точек, скорее всего, будет довольно большим (десятки тысяч), а число различных точек - на несколько порядков меньше. Можно ещё наложить ограничение на фигуры - максимальное расстояние между точками одной фигуры должно быть меньше некоей константы, чтобы избежать рассмотрения очень больших геометрически фигур.

Заранее спасибо, если кто что-нибудь посоветует.

С уважением, Mihail.

--- GoldED+/W32 1.1.4.7
 * Origin: Origin here (2:5030/744.237)