New similarity measures between polylines with applications to morphing and polygon sweeping

We introduce two new related metrics, the geodesic width and the link width, for measuring the "distance" between two nonintersecting polylines in the plane. If the two polylines have n vertices in total, we present algorithms to compute the geodesic width of the two polylines in O(n(2) log n) time using O(n(2)) space and the link width in O(n(3) log n) time using O(n(2)) working space where n is the total number of edges of the polylines.