ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Mihail S. Sidorenko                  2:5030/744.237 17 May 2002  17:54:50
 To : All
 Subject : вопрос
 -------------------------------------------------------------------------------- 
 

 
 Возникла такая задача, может, кто подскажет, какие могут быть идеи по этому
 поводу?
 
 Есть множество пронумерованных несовпадающих друг с другом точек на плоскости,
 заданных своими координатами X и Y, всего N точек. Каждой точке сопоставленно
 число 1..M, M < N. Две точки считаются одинаковыми тогда и только тогда, когда
 сопоставленные им числа равны. "Фигурой" называется подмножество точек, не
 имеющее общих точек ни с одной заданной ранее таким образом фигурой. Фигуры
 считаются одинаковыми тогда и только тогда, когда их можно совместить друг с
 другом при помощи некоторых стандартных преобразований на плоскости, причём,
 возможно, не точно совместить все одинаковые соответствующие точки двух фигур, а
 в некоторой эпсилон-окрестности. Под стандартными преобразованиями понимаются
 сдвиг по осям и независимое линейное изменение масштаба по осям; поворот и
 отражение не рассамтриваются. Требуется найти максимальное число самых больших
 одинаковых фигур.
 
 Общее число точек, скорее всего, будет довольно большим (десятки тысяч), а число
 различных точек - на несколько порядков меньше. Можно ещё наложить ограничение
 на фигуры - максимальное расстояние между точками одной фигуры должно быть
 меньше некоей константы, чтобы избежать рассмотрения очень больших геометрически
 фигур.
 
 Заранее спасибо, если кто что-нибудь посоветует.
 
 С уважением, Mihail.
 
 --- GoldED+/W32 1.1.4.7
  * Origin: Origin here (2:5030/744.237)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор