Пусть задано дискретное множество точек на плоскости и надо найти точку наиболее близкую к ним. В качестве критерия близости будем рассматривать некоторую норму вектора отклонений.

Для 1-нормы это будет сумма расстояний от заданных точек до оптимальной. Для частных случаев, когда к-во точек меньше пяти, применяются специальные методы. Алгоритмы для 3 и 4 точек были взяты из этой книги. Для случаев, когда точек больше 4, применяется разновидность метода "тяжёлого шарика":

Def<Vector2d> getNearPoint1 ( CArrRef<Vector2d> point, double eps = 0 );

Для 2-нормы оптимальной точкой будет среднее арифметическое данных точек ( центр масс ):

Def<Vector2d> getNearPoint2 ( CArrRef<Vector2d> point );

Для бесконечной нормы оптимальной точкой будет центр минимальной охватывающей окружности:

Def<Vector2d> getNearPointU ( CArrRef<Vector2d> point );

Примеры использования этих функций можно посмотреть в приложении DEMO.

Описание шаблона классов CArrRef находится здесь.
Описание шаблона классов Def находится здесь.
Описание класса Vector2d находится здесь.

Исходники находятся в approx2d.cpp