Find all points with a distance less than d to a (potentially not convex) polygon I have a polygon P, that may or may not be convex. Is there an algorithm that will enable me to find the collection of points A that are at a distance less than d from P?
Is A in turn always a polygon?
Does the solution change materially if we try to solve the problem on the surface of a sphere instead of on a Euclidean plane?

I heard Ravi Vakil give a series of plenary talks at an MAA conference on this question.  The talks were entitled "The Mathematics of Doodling."  He generalized the question, though, by asking what happens in the limit when you start with some set in the plane and then iterate the process of finding the set of points at a distance $r$ from the current set.  Some interesting mathematics came out as he showed that the resulting sequence of points gets more and more circular.
There's a good picture of him doing this here on the MAA website.
He also has a series of related problems that he developed for the Stanford Math Circle available here.
Also according to his website, he has an article, "The Mathematics of Doodling," that will be appearing in the February 2011 issue of the American Mathematical Monthly.  (Update: The article has just appeared in print.  The rest of the reference is Vol. 118(2), pp. 116-129.)
