Optimization of the Hausdorff distance between sets in Euclidean space

V. N. Ushakov ; A. S. Lakhtin ; P. D. Lebedev

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 3, pp. 291-308

Résumé

Set approximation problems play an important role in many research areas; for example, approximation problems for solvability sets and reachable sets of control systems are intensively studied in differential game theory and optimal control theory. In N. N. Krasovskii and A. I. Subbotin's investigations devoted to positional differential games, one of the key problems was the problem of identification of solvability sets, which are maximal stable bridges. This problem can be solved exactly in rare cases only; in most cases, the question of the approximate calculation of solvability sets arises. In papers by A. B. Kurzhanskii and F. L. Chernousko and their colleagues, reachable sets were approximated by ellipsoids and parallelepipeds. In the present paper, we consider problems in which it is required to approximate a given set by arbitrary polytopes. Two sets, polytopes $A$ and $B$, are given in Euclidean space. It is required to find a position of the polytopes that provides a minimum Hausdorff distance between them. Though the statement of the problem is geometric, methods of convex and nonsmooth analyze are used for its investigation. One of the approaches to dealing with planar sets in control theory is their approximation by families of disks of equal radii. A basic component of constructing such families is a best $n$-net and its generalizations, which were described, in particular, by A. L. Garkavi. The authors designed an algorithm for constructing best nets based on decomposing a given set into subsets and calculating their Chebyshev centers. Qualitative estimates for the deviation of sets from their best $n$-nets as $n$ grows to infinity were given in the general case by A. N. Kolmogorov. We derive a numerical estimate for the Hausdorff deviation of one class of sets. Examples of constructing of the best $n$-nets are given.

Détail

Mots-clés : Hausdorff distance, polygon
Keywords: best $n$-net, disk cover.

Bibliographie

[1] Krasovskii N. N., Subbotin A. I., Pozitsionnye differentsialnye igry, Nauka, M., 1974, 456 pp. | MR | Zbl

[2] Kurzhanskii A. B., Filippova T. F., “Ob opisanii mnozhestva vyzhivayuschikh traektorii differentsialnogo vklyucheniya”, Dokl. AN SSSR, 289:1 (1986), 38–41 | MR

[3] Kurzhanski A. B., Filippova T. F., “On the theory of trajectory tubes – a mathematical formalism for uncertain dynamics, viability and control”, Advances in nonlinear dynamics and control, A report from Russia, Progr. Systems Control Theory, 17, Birkhauser, Boston, 1993, 122–188 | MR

[4] Kurzhanski A. B., Valyi I., Ellipsoidal calculus for estimation and control, Birkhauser, Boston, 1997, 220 pp. | MR | Zbl

[5] Chernousko F. L., Otsenivanie fazovogo sostoyaniya dinamicheskikh sistem. Metod ellipsoidov, Nauka, M., 1988, 320 pp. | MR | Zbl

[6] Chernousko F. L., “Ellipsoidalnye otsenki oblasti dostizhimosti upravlyaemykh sistem”, Prikl. matematika i mekhanika, 45:1 (1981), 11–19 | MR

[7] Chernousko F. L., Ovseevich A. I., “Properties of the optimal ellipsoids approximating the reachable sets of uncertain systems”, J. Optimization Theory Appl., 120:2 (2004), 223–246 | DOI | MR | Zbl

[8] Ushakov V. N., Matviichuk A. R., Lebedev P. D., “Defekt stabilnosti v igrovoi zadache o sblizhenii v moment”, Vestn. Udmurt. un-ta. Matematika, mekhanika, kompyuternye nauki, 2010, no. 3, 87–103

[9] Ushakov V. N., Lebedev P. D., Matviichuk A. R., Malev A. G., “Differentsialnye igry s fiksirovannym momentom okonchaniya i otsenka stepeni nestabilnosti mnozhestv v etikh igrakh”, Tr. MIAN, 277, 2012, 275–287 | MR | Zbl

[10] Khausdorf F., Teoriya mnozhestv, Kom kniga, M., 2006, 304 pp.

[11] Lakhtin A. S., Ushakov V. N., “Zadacha optimizatsii khausdorfova rasstoyaniya mezhdu dvumya vypuklymi mnogogrannikami”, Sovremennaya matematika i ee prilozheniya, 9, 2003, 60–67 | MR

[12] Lakhtin A. S., Ushakov V. N., “Minimization of Hausdorf distance between convex polyhedrons”, J. Math. Sci., 126:6 (2005), 1553–1560 | DOI | MR | Zbl

[13] Rokafellar R., Vypuklyi analiz, Mir, M., 1973, 472 pp.

[14] Sukharev A. G., Timokhov A. V., Fedorov V. V., Kurs metodov optimizatsii, Nauka, M., 1986, 326 pp. | MR | Zbl

[15] Shor N. Z., Metody minimizatsii nedifferentsiruemykh funktsii i ikh prilozheniya, Naukova dumka, Kiev, 1979, 200 pp. | MR | Zbl

[16] Polyak B. T., Vvedenie v optimizatsiyu, Nauka, M., 1983, 382 pp. | MR

[17] Lebedev P. D., Ushakov A. V., “Approksimatsiya mnozhestv na ploskosti optimalnymi naborami krugov”, Avtomatika i telemekhanika, 2012, no. 3, 79–90

[18] Lebedev P. D., Bukharov D. S., “Approksimatsiya mnogougolnikov nailuchshimi naborami krugov”, Izv. Irkut. gos. un-ta. Matematika, 2013, no. 3, 72–87 | Zbl

[19] Lebedev P. D., Uspenskii A. A., Ushakov V. N., “Algoritmy nailuchshei approksimatsii ploskikh mnozhestv naborami krugov”, Vest. Udmurt. universiteta. Matematika. Mekhanika. Kompyuternye nauki, 2013, no. 4, 88–99

[20] Garkavi A. L., “O suschestvovanii nailuchshei seti i nailuchshego poperechnika mnozhestva v banakhovom prostranstve”, Uspekhi mat. nauk, 15:2 (1960), 210–211

[21] Garkavi A. L., “O nailuchshei seti i nailuchshem sechenii mnozhestv v normirovannom prostranstve”, Izv. AN SSSR. Ser. matematicheskaya, 26:1 (1962), 87–106 | MR | Zbl

[22] Garkavi A. L., “O chebyshevskom tsentre i vypukloi obolochke mnozhestva”, Uspekhi mat. nauk, 19:6 (1964), 139–145 | MR | Zbl

[23] Sosov E. N., “Metricheskoe prostranstvo vsekh $N$-setei geodezicheskogo prostranstva”, Uchen. zap. Kazan. gos. un-ta. Ser. fiz.-mat. nauk, 15, no. 4, 2009, 136–149

[24] Kolmogorov A. N., “O nekotorykh asimptoticheskikh kharakteristikakh vpolne ogranichennykh metricheskikh prostranstv”, Dokl. AN SSSR, 108:3 (1956), 385–388 | MR | Zbl

[25] Kolmogorov A. N., Tikhomirov V. M., “$\varepsilon$-entropiya i $\varepsilon$-emkost mnozhestv v funktsionalnykh prostranstvakh”, Uspekhi mat. nauk, 14:2(86) (1959), 3–86 | MR | Zbl

[26] Leikhtveis K., Vypuklye mnozhestva, per. s nem. V. A. Zalgallera, T. V. Khachaturovoi, ed. V. A. Zalgaller, Nauka, M., 1985, 335 pp., (von Leichtweiss K., Konvexe Mengene) | MR

[27] Piyavskii S. A., “Ob optimizatsii setei”, Izv. AN SSSR. Tekhn. kibernetika, 1968, no. 1, 68–80

[28] Brusov V. S., Piyavskii S. L., “Vychislitelnyi algoritm optimalnogo pokrytiya oblastei ploskosti”, Zhurn. vychisl. matematiki i mat. fiziki, 11:2 (1971), 304–312 | Zbl

[29] Preparata F., Sheimos M., Vychislitelnaya geometriya, Mir, M., 1989, 478 pp. | MR | Zbl

[30] Galiev Sh. I., Karpova M. A., “Optimizatsiya mnogokratnogo pokrytiya ogranichennogo mnozhestva krugami”, Zhurn. vychisl. matematiki i mat. fiziki, 50:4 (2010), 757–769 | MR | Zbl

[31] Erich's Packing Center, [Site], URL: http://www2.stetson.edu/~efriedma/packing.html

[32] Bychkov I. V., Maksimkin N. N., Khozyainov I. S., Kiselev L. V., “O zadache patrulirovaniya granitsy akvatorii, okhranyaemoi gruppoi podvodnykh apparatov”, Tekhnicheskie problemy osvoeniya mirovogo okeana, Materialy 5-oi Vseros. nauch.-tekhn. konf., Vladivostok, 2013, 424–429

[33] Stepanov N. N., Sfericheskaya trigonometriya, OGIZ, L.–M., 1948, 154 pp. | Zbl

[34] Kazakov A. L., Lempert A. A., “Ob odnom podkhode k resheniyu zadach optimizatsii, voznikayuschikh v transportnoi logistike”, Avtomatika i telemekhanika, 2011, no. 7, 50–57 | MR | Zbl

[35] Kazakov A. L., Lempert A. A., Bukharov D. S., “K voprosu o segmentatsii logisticheskikh zon dlya obsluzhivaniya nepreryvno raspredelennykh potrebitelei”, Avtomatika i telemekhanika, 2013, no. 6, 87–100 | MR

[36] Lempert A. A., Kazakov A. L., Bukharov D. S., “Matematicheskaya model i programmnaya sistema dlya resheniya zadachi razmescheniya logisticheskikh ob'ektov”, Upravlenie bolshimi sistemami, 41, 2013, 270–284