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


DD>Хт, этого хотелось бы избежать...

DD>Кстати, где можно посмотреть, откуда будет "очевидно, что задача NP-полная"?
Вообще-то это мое ИМХО, доказательства для подобной задачи я не видел, но думаю, что это все-таки именно так.

DD>Похоже я немного не точно сформулировал задачу.
DD>Алгоритм может помещать точки на периметре как хочет, главное
DD>чтобы они были размещены равномерно, это меняет дело? (похоже не особо )
По-моему только усложняет...
DD>Ну и бог с ней с оптимальностью по длине, главное первое
DD>приближенное решение давало непересекающиеся отрезки, это возможно?
Можно попробовать так:
1. размещаем точки по периметру.
2. соединяем точку из прямоугольника с ближайшей точкой на периметре
3. если пересечений нет, берем следующую точку из прямоугольника , и идем на шаг 2. Иначе — на шаг4.
4. если еще есть точки на периметре, то помечаем текущую точку и берем следующую из непомеченных, идем на шаг 2. Иначе — шаг 5
5. разрываем предыдущий отрезок, и соединяем точку в прямоугольнике с другой точкой на периметре.


Это в общих чертах...