TRAVELING THE BOUNDARY OF MINKOWSKI SUMS

We consider the problem of traveling the contour of the set of all poi nts that are within distance 1 of a connected planar curve arrangement P, forming an embedding of the graph G. We show that if the overall l ength of P is L, there is a closed roundtrip that visits all points of the contour and has length no longer than 2L + 2 pi. This result carr ies over in a more general setting: if R is a compact convex shape wit h interior points and boundary length l, we can travel the boundary of the Minkowski sum P + R on a closed roundtrip no longer than 2L + l. (C) 1998 Elsevier Science B.V. All rights reserved.