Algorithms for the construction of an optimal cover for sets in three-dimensional Euclidean space

V. N. Ushakov ; P. D. Lebedev

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 2, pp. 276-288

Résumé

The problem of an optimal cover of sets in three-dimensional Euclidian space by the union of a fixed number of equal balls, where the optimality criterion is the radius of the balls, is studied. Analytical and numerical algorithms based on the division of a set into Dirichlet domains and finding their Chebyshev centers are suggested for this problem. Stochastic iterative procedures are used. Bounds for the asymptotics of the radii of the balls as their number tends to infinity are obtained. The simulation of several examples is performed and their visualization is presented.

Détail

Keywords: Hausdorff deviation, best $n$-net, ball cover, Chebyshev center.

Bibliographie

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

[2] Ushakov V.N., Lavrov N.G., Ushakov A.V., “Konstruirovanie reshenii v zadache o sblizhenii statsionarnoi upravlyaemoi sistemy”, Tr. In-ta matematiki i mekhaniki UrO RAN, 20:4 (2014), 277–286

[3] Ushakov V.N., Malev A.G., “K voprosu o defekte stabilnosti v igrovoi zadache o sblizhenii”, Tr. In-ta matematiki i mekhaniki UrO RAN, 16:1 (2010), 199–222

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

[5] Chernousko F.L., Otsenivanie fazovogo sostoyaniya dinamicheskikh sistem, Nauka, M., 1988, 384 pp. | MR

[6] Aronov B., Ezra E. , and Sharir M., “Small-size $\varepsilon$-nets for axis-parallel rectangles and boxes”, SIAM J. Comput., 39:7 (2010), 3248–3282 | DOI | MR | Zbl

[7] Lauen S., “Geometric set cover and hitting sets for polytopes in $R^3$”, 25th Int. Symp. Theoretical Aspects of Comput. Sci., 1, 2008, 479–490 | MR | Zbl

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

[9] Lebedev P.D., Uspenskii A.A., Ushakov V.N., “Algoritmy nailuchshei approksimatsii ploskikh mnozhestv naborami krugov”, Vest. Udmurt. un-ta (Matematika. Mekhanika. Kompyuternye nauki.), 2013, no. 4, 88–99 | Zbl

[10] Ushakov V.N., Lakhtin A.S., Lebedev P.D., “Optimizatsiya khausdorfova rasstoyaniya mezhdu mnozhestvami”, Tr. In-ta matematiki i mekhaniki UrO RAN, 20:3 (2014), 291–308

[11] Raigorodskii A.M., “Vokrug gipotezy Borsuka”, Sovremennaya matematika. Fundamentalnye napravleniya, 23 (2007), 147–164 | MR

[12] Katzarowa-Karanowa P., “Uber ein euklidisch-geometrisches Problem von B. Grunbaum”, Arch. Math., 18:6 (1967), 663–672 | DOI | MR | Zbl

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

[14] 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 | Zbl

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

[16] 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

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

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

[19] Belobrov P.K., “K voprosu o chebyshevskom tsentre mnozhestva”, Izv. vyssh. ucheb. zavedenii. Matematika, 1964, no. 1 (38), 3–9 | MR | Zbl

[20] Sosov E.N., “Nailuchshee priblizhenie v metrike Khausdorfa vypuklogo kompakta sharom”, Mat. zametki, 76:2 (2004), 226–236 | DOI | MR | Zbl

[21] | MR

[22] Dubrovin B.A., Novikov S.P., Fomenko A.T., Sovremennaya geometriya. Metody i prilozheniya, 2-e izd., pererab., Nauka, Gl. red. fiz.-mat. lit., M., 1986, 760 pp. | MR

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

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

[25] Mestetskii L.M., Nepreryvnaya morfologiya binarnykh izobrazhenii: figury, skelety, tsirkulyary, Fizmatlit, M., 2009, 288 pp.

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

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

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

[29] Tot L.F., Raspolozheniya na ploskosti, na sfere i v prostranstve, Goc. izd-vo fiz.-mat. lit., M., 1958, 365 pp.

[30] Chen K., Dzhiblin P., Irving A., MATLAB v matematicheskikh issledovaniyakh, Mir, M., 2001, 346 pp.

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

[32] Shorikov A.F., “Algoritm resheniya zadachi aposteriornogo minimaksnogo otsenivaniya sostoyanii diskretnykh dinamicheskikh sistem. I”, Avtomatika i telemekhanika, 1996, no. 7, 130–143 | MR | Zbl

[33] Shorikov A.F., “Algoritm resheniya zadachi aposteriornogo minimaksnogo otsenivaniya sostoyanii diskretnykh dinamicheskikh sistem. II”, Avtomatika i telemekhanika, 1996, no. 9, 139–150 | MR | Zbl