MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 249 characters in body

Edit: The answer below is somewhat obsolete, due to the recent paper of Noga Alon, where he establishes the first non-trivial lower bounds for strong epsilon-nets.

Old answer: This answer uses some terminology from discrete geometry. The definitions, and more background material can be found in, for example, "Discrete geometry" by Jiří Matoušek chapters 9 and 10. Less thorough introduction can be consulted without going to the library.

If one drops the requirement that set has to have asymptotic density, and merely asks for the set to have a constant density on some large (but fixed) ball, and restricts the triangles to live inside that ball, the problem does not become much easier. In that case problem asks for a construction of an 1/r-net of size O(r) for the family of all triangles with respect to the Lebesgue measure on [0,1]^2 (or equivalently for a construction of 1/r-net for a grid {1,..,N}x{1,...,N} for large N). The upper bound of r*log r on the size of the net follows from finiteness of Vapnik Chervonenkis dimension. For general range spaces with finite VC dimension the logarithmic factor is necessary. However, there is by now several results that remove or reduce the logarithmic factor in "geometrically interesting range spaces" (as a sample, here is a result for axis-parallel boxes). Unfortunately, as far as I know these developments do not include the space of triangles in the plane (I might be wrong; you should check with one of the experts).

Showing non-existence of small 1/r-nets for this problem is certainly open, and likely to be hard. The only currently known lower bound on 1/r-nets for any geometric problem whatsoever is in my paper with Matoušek and Nivasch, and is for the family of all the convex sets. However, there instead of a grid {1,...,N}x{1,...,N} that is featured in this problem, the construction is a kind of highly stretched grid.

1

This answer uses some terminology from discrete geometry. The definitions, and more background material can be found in, for example, "Discrete geometry" by Jiří Matoušek chapters 9 and 10. Less thorough introduction can be consulted without going to the library.

If one drops the requirement that set has to have asymptotic density, and merely asks for the set to have a constant density on some large (but fixed) ball, and restricts the triangles to live inside that ball, the problem does not become much easier. In that case problem asks for a construction of an 1/r-net of size O(r) for the family of all triangles with respect to the Lebesgue measure on [0,1]^2 (or equivalently for a construction of 1/r-net for a grid {1,..,N}x{1,...,N} for large N). The upper bound of r*log r on the size of the net follows from finiteness of Vapnik Chervonenkis dimension. For general range spaces with finite VC dimension the logarithmic factor is necessary. However, there is by now several results that remove or reduce the logarithmic factor in "geometrically interesting range spaces" (as a sample, here is a result for axis-parallel boxes). Unfortunately, as far as I know these developments do not include the space of triangles in the plane (I might be wrong; you should check with one of the experts).

Showing non-existence of small 1/r-nets for this problem is certainly open, and likely to be hard. The only currently known lower bound on 1/r-nets for any geometric problem whatsoever is in my paper with Matoušek and Nivasch, and is for the family of all the convex sets. However, there instead of a grid {1,...,N}x{1,...,N} that is featured in this problem, the construction is a kind of highly stretched grid.