Рассматривается евклидова задача коммивояжера, характеризующаяся недетерминированной полиномиальной сложностью. Основной целью является расширение применимости полиномиальных алгоритмов для специальных случаев евклидовой задачи коммивояжера, таких как задачи с вершинами, лежащими на выпуклой оболочке, на более общие конфигурации точек. Для этого используется метод попарного сходства. Разработан новый эвристический алгоритм с гарантированной абсолютной погрешностью, который состоит из трех этапов. На первом этапе проводится разбиение множества точек на подмножества, образующие вложенные выпуклые многоугольники. На втором этапе решаются подзадачи для каждого многоугольника как специального случая с линейной сложностью. На третьем этапе осуществляется объединение решений подзадач в единый маршрут. Теоретическая часть работы посвящена оценке погрешности предложенного алгоритма. Было доказано, что абсолютная погрешность решения зависит от числа выпуклых многоугольников и расстояний между ними. Показано, что при увеличении расстояния между многоугольниками погрешность стремится к нулю. Кроме того, введено понятие ε-окрестности выпуклого многоугольника – области, для которой лежащие в ней точки могут быть добавлены в обход на основе ближайшего расстояния до вершин многоугольника без нарушения оптимальности обхода. Работа алгоритма и выполнимость утверждений были проверены с помощью численных экспериментов на примерах задач из библиотеки Traveling Salesman Problem Library. Результаты подтвердили, что при увеличении расстояния между выпуклыми оболочками относительная погрешность снижается. Также было показано, что рост числа выпуклых оболочек приводит к увеличению погрешности, что требует минимизации их количества в практических приложениях. Отмечены направления для дальнейших исследований, включая поиск точных верхних оценок погрешности, оптимизацию параметров и обобщение метода на многомерные евклидовы пространства.