About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Information Processing Letters
Paper
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.