Traveling the Boundary of Minkowski Sums

Fekete, Sandor P. and Pulleyblank, William R. (1998) Traveling the Boundary of Minkowski Sums.
Published in: Information Processing Letters Vol. 66 (4). pp. 171-174.


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, forming an embedding of the graph G. We show that if the overall length of the curve arrangement is L, there is a closed roundtrip that visits all points of the contour and has length no longer than 2L+2pi. We also give a generalization: If C is a compact convex shape with interior points and boundary length ell, we can travel the boundary of the Minkowski sum G+C on a closed roundtrip no longer than 2L+ell.

Download: [img] Postscript - Preprinted Version
Download (143kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-254
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45