Eliminating gaps in rotated images?

So it seems that rotating an image at anything other than multiples of 90 degree angles produces 'gaps' (at least going from 0 - 360). I've spent an hour or so thinking of ways to compensate for it, but I can't really imagine anything other than a really complicated heuristic. Also, are there any angles (perhaps smaller than 1 degree) that can be used to prevent this? Google hasn't been very helpful, either, since I really don't know the technical term is for this problem.

Any help would be appreciated!

EDIT:

Now that I think of it, this a similar problem to alaising; ie, any line drawn at any angle other than modulo 90 degrees on a display is going to appear 'stepped'. So I could probably perform a 'nearest neighbor' type calculation whenever the X or Y coordinate changes.