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.

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


Actions:
Download: [img] Postscript - Preprinted Version
Download (143kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 4 (Google Scholar) | 1 (Web of Science)
Uncontrolled Keywords: Cauchy's formula contour lines geometric inequalities geometric optimization hamiltonian cycles Minkowski sum motion planning
Subjects:
  • 28-XX Measure and integration > 28Axx Classical measure theory > 28A75 Length, area, volume, other geometric measure theory

  • 51-XX Geometry > 51Mxx Real and complex geometry > 51M16 Inequalities and extremum problems

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C30 Nonlinear programming

    		•
    Divisions: Mathematical Institute
    Related URLs:
    Deposit Information:
    ZAIK Number: zpr97-254
    Depositing User: Archive Admin
    Date Deposited: 02 Apr 2001 00:00
    Last Modified: 19 Dec 2011 09:45
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/254