on the maximum triangle problem

Given a set p of n points in the plane, the maximum triangle problem asks for nding a triangle with three vertices in p that encloses the maximum number of points from p. while the problem is easily solvable in o(n3) time, it has been open whether a subcubic solution is possible. in this paper, we show that the problem can be solved in o(n3) 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+nh2) runtime, where h is the size of the convex hull of p.