We show that there is no $(1+\eps)$-approximation algorithm for
the problem of covering points in the plane by minimum number of
fat triangles of similar size (with the minimum angle of the
triangles being close to $45$ degrees). Here, the available
triangles are prespecified in advance. Since a constant factor
approximation algorithm is known for this problem
\cite{cv-iaags-07}, this settles the approximability of this
problem.
We also investigate some related problems, including cover by
friendly fat shapes, and independent set of triangles in three
dimensions.
Postscript,
PDF.
Last modified: Mon Aug 17 10:39:13 CDT 2009