Самый быстрый способ найти максимально возможную площадь треугольника

Question

Представим себе, что у нас есть множество точек в плоскости, каждая из которых описывается парой целых координат. Есть ли способ найти треугольник с вершинами в этих точках с максимально возможной площадью быстрее, чем с помощью алгоритма O (n^3)?

Answer 1

1. Найти выпуклый корпус.
2. Для каждой пары точек (A, B), лежащих на выпуклой оболочке, найдите третью точку C, дающую максимальную площадь треугольнику ABC. Это можно сделать, используя двоичный поиск в O (log n).

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

Шаг двоичного поиска выглядит следующим образом. Возьмите три последовательные точки C, C ', C' 'в середине интервала точек. Вычислите три области CAB, C'AB, C''AB. Если C 'является самым большим из трех, это глобальный максимум, и поиск завершен. Если C является наибольшим, максимум находится в левой половине интервала. Если C '' является наибольшим, максимум находится в правой половине. (Edit: note, новый интервал должен содержать C 'на одном из концов).

Существует алгоритм, который работает в O (n^2 log n).

Редактировать 2: ответ на вопрос this question показывает, как сделать это значительно быстрее. Вы можете комбинировать оба подхода, чтобы сделать еще лучше (в O (log n) после того, как выпуклая оболочка построена, хотя со строительством корпуса все еще O (n log n)).