# 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?

-

What you seek is known as the offset curve of a polygon. Here is the Wikipedia article. This is closely related to the Minkowski sum construction, in this case the Minkowski sum of a polygon and a disk. As others already indicated, the offset of a polygon is not in general a polygon. There is a substantial literature on the topic, which can be reached with these key phrases. There are algorithms; none are easy. Here is one: "An offset algorithm for polyline curves," Computers in Industry, Volume 58,Issue 3 (April 2007).

-
Thanks for putting me in touch with the literature. Honestly, I do not think I would have ever guessed those keywords. I'm not surprised that none of the algorithms are easy, computational geometry is always a pain ;) I'm considering some numeric shortcuts at the moment too. – drxzcl Oct 22 '10 at 14:20
Surely the offset of a polygon is never a polygon? – TonyK Feb 7 '11 at 21:48
TonyK: You are right; my description was sloppy. – Joseph O'Rourke Feb 8 '11 at 19:52

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..

-

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.)

-