Cложность задачи о разрезе максимального веса в евклидовом пространстве

Рассматривается задача поиска разреза максимального веса в полном неориентированном графе, вершинами которого являются точки $q$-мерного пространства. Анализируются два случая, в которых длины рёбер равны (i) евклидовым расстояниям между точками пространства и (ii) квадратам этих расстояний. Доказано, что в обоих случаях задача NP-трудна в сильном смысле. Показано также, что для них в предположении $\mathrm{P\neq NP}$ не существует полностью полиномиальной приближённой схемы (FPTAS). Библиогр. 17.