A new metric between polygons, and how to compute it (extended abstract). (English) Zbl 1427.68337

Rote, Günter

Kuich, Werner (ed.), Automata, languages and programming. 19th international colloquium, Wien, Austria, July 13–17, 1992. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 623, 404-415 (1992).

Summary: 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. There are several alternative definitions of the metric, some of which are interesting in their own right. We also give an algorithm for computing the metric, and we discuss possible implementations.
For the entire collection see [Zbl 1369.68031].

MSC:

68U05

Computer graphics; computational geometry (digital and algorithmic aspects)

References:

[1]	A. V. Aho, J. E. Hopcroft, and J. D. Ullman: The Design and! Analysis of Computer Algorithms, Addison-Wesley, 1974. · Zbl 0326.68005
[2]	E. Arkin, L. P. Chew, D. P. Huttenlocher, K. Kedem, and J. S. B. Mitchell: An efficiently computable metric for comparing polygonal shapes, in: SODA’90, Proc. 1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, January 1990, Society for Industrial and Applied Mathematics, Philadelphia 1990, pp. 129-137. · Zbl 0800.68949
[3]	M. J. Atallah: A linear time algorithm for the Hausdorff distance between convex polygons, Inform. Process. Lett.17 (1983), 207-209. · Zbl 0527.68051
[4]	M. D. Atkinson, J.-R. Sack, N. Santoro, T. Strothotte: Min-max heaps and generalized priority queues, Commun. ACM29 (1986), 996-1000. · Zbl 0642.68055
[5]	H. Booth: Flows in Series-Parallel Networks, Ph. D. dissertation, Department of Computer Science, Princeton University, 1990.
[6]	P. Cox, H. Maitre, M. Minoux, C. Ribeiro: Optimal matching of convex polygons, Pattern Recognition Letters9 (1989), 327-334. · Zbl 0800.68758
[7]	H. N. Gabow and R. E. Tarjan: A linear-time algorithm for a special case of disjoint set union, J. Comput. Syst. Sci.30 (1985), 209-221. · Zbl 0572.68058
[8]	P. Hackh: Quality control of artificial fabrics, Forschungsbericht, Arbeitsgruppe Technomathematik, Universität Kaiserslautern, 1990.
[9]	H. Imai: A geometric fitting problem of two corresponding sets of points on a line, IEICE Trans. Fund. Electron. Commun. Comput. Sci.E 74 (1991), 665-667 plus Hiroshi Imai’s picture on p. 668.
[10]	L. Kantorovitch: On the translocation of masses, Comptes Rendues (Doklady) de l’Académie des Sciences de l’URSS37 (1942), 199-201.
[11]	L. V. Kantorovich and G. Sh. Rubinshtein: On a space of completely additive functions (in Russian), Vestnik Leningrad. Univ.13, 7 (1958), 52-59. · Zbl 0082.11001
[12]	K. Mehlhorn and S. Näher: Bounded ordered dictionaries in O(log log N) time and O(n) space. Inform. Proc. Lett.35 (1990), 183-189. · Zbl 0702.68042
[13]	G. Monge: Mémoire sur la théorie des déblais et des remblais, Mémoires de l’Académie Royale des Sciences, Paris, 1781, 666-704 and pl. XVIII-XIX; see also: Sur les déblais et les remblais, Histoire de l’Académie Royale des Sciences, Paris, 1781, 34-38.
[14]	H. Neunzert and B. Wetton: Pattern recognition using measure space metrics, Forschungsbericht Nr. 28, Arbeitsgruppe Technomathematik, Universität Kaiserslautern, 1987.
[15]	M. Ohmura, S. Wakabayashi, J. Miyao, and N. Yoshida: Improvement of one-dimensional placement in VLSI design (in Japanese), Trans. List. Electron. Commun. Eng. JapanJ73-A, 11 (1990), 1858-1866.
[16]	S. T. Rachev: The Monge-Kantorovich mass transfer problem and its stochastic applications (in Russian), Teor. Veroyatn. Primen.29 (1984), 625-653; English translation: Theory Prob. Appl. 29 (1984), 647-676. · Zbl 0565.60010
[17]	S. T. Rachev: Probability Metrics and the Stability of Stochastic Models, Wiley, Chichester 1991. · Zbl 0744.60004
[18]	R. E. Tarjan and J.