Самый большой треугольник от ряда точек [дубликат]

Вот мысль о том, как уменьшить это до O(n² log n). Я ничего не знаю о вычислительной геометрии, поэтому отмечу это как community wiki; пожалуйста, не стесняйтесь улучшать это.

Предварительно обработайте выпуклый корпус, найдя для каждой точки диапазон наклонов прямых, проходящих через эту точку, таких, что множество полностью лежит по одну сторону от прямой. Затем инвертируйте это отношение: постройте интервальное дерево для наклонов с точками в листовых узлах, так, чтобы при запросе наклона находились точки, через которые проходит касательная.

Если на выпуклом корпусе нет наборов из трех или более коллинеарных точек, то для каждого склона существует не более четырех точек (по две с каждой стороны), но в случае коллинеарных точек мы можем просто игнорировать промежуточные точки.

Теперь пройдитесь итерацией по всем парам точек (P,Q) на выпуклом корпусе. Мы хотим найти точку R такую, чтобы треугольник PQR имел максимальную площадь. Принимая PQ за основание треугольника, мы хотим максимизировать высоту, находя R как можно дальше от прямой PQ. Прямая, проходящая через R параллельно PQ, должна быть такой, чтобы все точки лежали по одну сторону от нее, поэтому мы можем найти ограниченное число кандидатов за время O(log n), используя предварительно построенное дерево интервалов.

Чтобы улучшить эту задачу на практике, выполните ветвление и связывание на множестве пар точек: найдите верхнюю границу для высоты любого треугольника (например, максимальное расстояние между двумя точками) и отбрасывайте любую пару точек, расстояние между которыми, умноженное на эту верхнюю границу, меньше, чем самый большой треугольник, найденный до сих пор.

Навскидку, возможно, вы могли бы сделать что-то, связанное с сеткой/разделением коллекции точек на группы? Возможно... разделить точки на три группы (не уверен, что в данном случае это лучший способ), отбросить те точки в каждой группе, которые находятся ближе к двум другим группам, чем другие точки в той же группе, а затем использовать оставшиеся точки для нахождения наибольшего треугольника, в котором может быть одна вершина в каждой группе? Это фактически упростит ситуацию, когда все точки лежат на окружности, потому что вы просто сосредоточитесь на точках, которые находятся вблизи центра дуг, содержащихся в каждой группе, так как они будут наиболее удалены от двух других групп.

Однако я не уверен, что это даст правильный результат для определенных треугольников/распределений точек. Могут возникнуть ситуации, когда результирующий треугольник не будет иметь оптимальную площадь, либо потому что группировка и/или выбор вершин не оптимален. Что-то в этом роде.

В любом случае, это мои мысли по данной проблеме. Надеюсь, я хотя бы смог дать вам идеи о том, как над ней работать.

Как насчет того, чтобы отбрасывать по одной точке из выпуклого корпуса? Начиная с выпуклого корпуса, вычислите площадь треугольника, образованного каждой тройкой соседних точек (p1p2p3, p2p3p4 и т.д.). Найдите треугольник с минимальной площадью, затем отбросьте середины трех точек, которые образовали этот треугольник. (Другими словами, если треугольник с наименьшей площадью - p3p4p5, отбросьте P4.) Теперь у вас есть выпуклый многоугольник с N-1 точками. Повторяйте ту же процедуру, пока не останется три точки. Это должно занять O(N^2) времени.

Я нисколько не удивлюсь, если найдется какой-то патологический случай, когда это не работает, но я ожидаю, что это будет работать в большинстве случаев. (Другими словами, я не доказал этого, и у меня нет источника, на который можно было бы сослаться)

Я думаю, что здесь может применяться метод вращающихся суппортов .

Не знаю, поможет ли это, но если выбрать две точки из выпуклого корпуса и повернуть все точки корпуса так, чтобы соединительная линия этих двух точек была параллельна оси x, то либо точка с максимальной, либо точка с минимальной координатой y образует треугольник с наибольшей площадью вместе с двумя точками, выбранными первыми.

Конечно, после проверки одной точки для всех возможных базовых линий, ее можно удалить из списка.