Günter Rote:

A new metric between polygons, and how to compute it (extended abstract)

In: "Automata, Languages and Programming". Proceedings of the 19th International Colloquium on Automata, Languages, and Programming (ICALP 92), Wien, Austria, July 1992. Editor: W. Kuich. Lecture Notes in Computer Science 623, Springer-Verlag, 1992, pp. 404-415.


The bounded Lipschitz distance can be used as a distance measure between polygons or between functions.  It has several properties which make it attractive to use from the viewpoint of applications like pattern matching or quality control of woven fabrics.  There are several alternative definitions of the metric, some of which are interesting in their own right. The bounded Lipschitz distance is related to the Monge-Kantorovich mass transfer problem, whose history goes back to 18th century work of G. Monge and to L. Kantorovitch.

We also give an algorithm for computing the metric, and we discuss possible implementations.

  PostScript file (gzippedpdf file
other papers about this subject
Last change: May 4, 2001.