Я ищу способ найти линию (красная), которая оптимально (наименьшая площадь) ограничивает набор 2d точек (черные звезды). 
У меня проблемы с поиском в Google, но следующие термины кажутся связанными:
- минимальная ограничивающая линия на интервале
- минимальная ограничивающая конус / пирамида / трапеция
- это упрощенный случай нахождения выпуклой оболочки или многоугольника - уже известны три стороны.
- минимизация хи2 / линейная регрессия
- фронт Парето
Если я предполагаю, что синяя линия определена между (xmin, 0) и (xmax, 0), то я могу параметризовать линию двумя точками: (xmin, ymin) и (xmax, ymax), где ymin и ymax - неизвестные параметры.
Мне нужно придерживаться
yi <= (xi - xmin) * (ymax - ymin) / (xmax - xmin) + ymin
для каждой точки (xi, yi). Это тривиально подразумевает, что ymin должен быть больше, чем yi точки xmin, а ymax должен быть больше, чем yi точки xmax.
Я хочу минимизировать область:
min: A = |ymax - ymin| / 2 * (xmax - xmin)
который упрощается до
min: (ymax - ymin)^2
Нужно ли мне решать эту проблему с помощью (не -?) линейного программирования, исчерпывающего поиска (проверить n * (n-1) / 2 комбинации строк) или есть простой и быстрые алгоритмы c решение?
Я также знаю, что линия будет иметь положительный наклон для моей проблемы. Я думаю, я могу использовать это, чтобы устранить точки с критерием доминирования Парето: любая точка (xi, yi) может удалить точку (xj, yj), если xj> xi, но yj