Given a set S of n points in the plane, we want to find a triangle, with vertices in S, such that the number of points of S enclosed by it is maximum. A solution can be found by considering all (n 3 ) triples of points in S. We show that, by considering only triangles with at least 1, 2, or 3 vertices on the convex hull of S, we obtain various approximation algorithms that run in o(n3) time.

Additional Metadata
Conference 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
Citation
Douïeb, K. (Karim), Eastman, M. (Matthew), Maheshwari, A, & Smid, M. (2011). Approximation algorithms for a triangle enclosure problem. Presented at the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011.