Traveling the boundary of Minkowski sums

Abstract

We consider the problem of traveling the contour of the set of all points 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 length of P is L, there is a closed roundtrip that visits all points of the contour and has length no longer than 2L + 2π. This result carries over in a more general setting: if R is a compact convex shape with interior points and boundary length ℓ, we can travel the boundary of the Minkowski sum P ⊕ R on a closed roundtrip no longer than 2L + ℓ. © 1998 Elsevier Science B.V. All rights reserved.