On the Maximum Triangle Problem

Given a set P of n points in the plane, the maximum triangle problem asks for finding a triangle with three vertices in P that encloses the maximum number of points from P. While the problem is easily solvable in O(n³) time, it has been open whether a subcubic solution is possible. In this paper, we show that the problem can be solved in o(n³) time, using a reduction to min-plus matrix multiplication. We also provide some improved approximation algorithms for the problem, including a 4-approximation algorithm running in O(n log n log h) time, and a 3-approximation algorithm with O(nh log n + nh²) runtime, where h is the size of the convex hull of P.