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

B>можно найти только полным перебором, т.е. в данном случае сложность — M!

Хт, этого хотелось бы избежать...
Кстати, где можно посмотреть, откуда будет "очевидно, что задача NP-полная"?

Похоже я немного не точно сформулировал задачу.
Алгоритм может помещать точки на периметре как хочет, главное
чтобы они были размещены равномерно, это меняет дело? (похоже не особо )
Ну и бог с ней с оптимальностью по длине, главное первое
приближенное решение давало непересекающиеся отрезки, это возможно?

Удачи, DaD