Линия лучше всего подходит для набора точек S на плоскости, если она минимизирует сумму расстояний между точками в S и линией. Предполагая, что алгоритм выпуклой оболочки доступен, найдите линию наилучшего соответствия для заданного множества точек S на плоскости. Это упражнение из книги «Дискретная и вычислительная геометрия». Я пытаюсь решить эту проблему месяцами. Я знаю, как решить это с исчислением и умной грубой силой. Аналитический способ решения этой проблемы - http://mathworld.wolfram.com/LeastSquaresFittingPerpendicularOffsets.html. Меня не интересует быстрое или оптимальное решение.
Вместо этого нацельтесь на наиболее подходящую линию Чебычева, которая минимизирует максимальное расстояние от точек до линии. Это лучше сочетается с выпуклыми свойствами корпуса. <час /> PDF скачать лекцию Ион Петре .
