Очевидно, что задача NP — полная, т.е. глобальный оптимум гарантированно можно найти только полным перебором, т.е. в данном случае сложность — M! Поэтому подобные задачи решаются только приближенно. Один из возможных подходов:
На первом этапе строится некое приближенное решение, которое даже может содержать пересечения (например каждую точку внутри соединить с ближайшей точкой на границе). Затем полученное решение улучшается с использованием алгоритмов локального поиска. Из таких алгоритмов в последнее время очень популярен Tabu search. В инете куча материалов по этому поводу, правда как правило на английском.
