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?

It will not be a polygon.  If you think about the original polygon being a square of side s, the set A is a square of side s+2d, but with the corners rounded.  The corners become quarter circles with radius d and centered on the original corners of the square.
For a general polygon the situation is much the same.  Draw a parallel to the sides offset by d.  Then round the outer corners with a circular arc of radius d centered on the original corners and tangent to the new parallels.  The meeting points will be the intersection of the new line parallel to one side and the extension of the other side of the corner.  The inner corners will stay corners but get less deep and eventually disappear if d is large enough..
