Approximation algorithms for a triangle enclosure problem
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.
|Conference||23rd Annual Canadian Conference on Computational Geometry, CCCG 2011|
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.