Том 22, номер 6, 2015 г., Стр. 5–28

УДК 519.7
Галиев Ш. И., Хорьков А. В.
Многократные покрытия кругами равностороннего треугольника, квадрата и круга

Аннотация:
Рассмотрены задачи k-кратного, k ≥ 1, покрытия равностороннего треугольника, квадрата и круга n равными кругами наименьшего возможного радиуса r^*_n,k. Представлены математические модели задач покрытия и алгоритмы их решения. Найдены оптимальные покрытия при некоторых значениях n и k, 1 < k ≤ n. Численными методами получены значения r_n,k радиусов кругов, при которых обеспечивается требуемое k-кратное покрытие указанных фигур для n ≤ 15 и 1 < k ≤ n.
Ил. 4, табл. 3, библиогр. 39.

Ключевые слова: многократное покрытие равными кругами, оптимизация покрытий, равносторонний треугольник, квадрат, круг, задача о минимальном покрытии.

DOI: 10.17377/daio.2015.22.482

Галиев Шамиль Ибрагимович ¹
Хорьков Александр Владимирович ¹
1. Казанский национальный исследовательский технический университет им. А. Н. Туполева,
ул. К. Маркса, 10, 420011 Казань, Россия
е-mail: sh.galiev@mail.ru, aLex22fcrk@yandex.ru

Статья поступила 17 марта 2015 г.
Исправленный вариант — 20 августа 2015 г.

Литература

[1] Алдын-оол Т. А., Ерзин А. И., Залюбовский В. В. Покрытие плоской области случайно распределенными сенсорами // Вестн. НГУ. Сер. Математика, механика, информатика. 2010. Т. 10, вып. 4. C. 7–25.

[2] Астраков С. Н., Ерзин А. И., Залюбовский В. В. Сенсорные сети и покрытие плоскости кругами // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 3. С. 3–19.

[3] Астраков С. Н., Ерзин А. И. Построение эффективных моделей покрытия при мониторинге протяженных объектов // Вычисл. технологии. 2010. Т. 17, № 1. С. 26–34.

[4] Брусов В. С., Пиявский С. А. Вычислительный алгоритм оптимального покрытия плоских областей // Журн. вычисл. математики и мат. физики. 1971. Т. 11, № 2. С. 304–312.

[5] Галиев Ш. И. Направления убывания для минимаксиминных задач // Журн. вычисл. математики и мат. физики. 1994. Т. 34, № 3. С. 323–343.

[6] Галиев Ш. И., Заботин В. И. О непрерывном обзоре поверхности Земли // Исслед. Земли из космоса. 1983. № 1. С. 117–120.

[7] Галиев Ш. И., Карпова М. А. Оптимизация многократного покрытия ограниченного множества кругами // Журн. вычисл. математики и мат. физики. 2010. Т. 50, № 4. С. 757–769.

[8] Галиев Ш. И., Карпова М. А. Многократные покрытия квадрата кругами. I // Вестн. КГТУ им. А. Н. Туполева. 2013. № 1. С. 86–93.

[9] Галиев Ш. И., Карпова М. А. Многократные покрытия квадрата кругами. II // Вестн. КГТУ им. А. Н. Туполева. 2013. № 2-1. С. 88–92.

[10] Галиев Ш. И., Хорьков А. В. Некоторые экстремальные многократные покрытия квадрата кругами // Вестн. КГТУ им. А. Н. Туполева. 2014. № 2. С. 154–159.

[11] Еремеев А. В., Заозёрская Л. А., Колоколов А. А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискрет. анализ и исслед. операций. Сер. 2. 2009.
Т. 7, № 2. С. 22–46.

[12] Кузюрин Н. Н. О сложности построения асимптотически оптимальных покрытий и упаковок // Докл. РАН. 1998. Т. 363, № 1. С. 11–13.

[13] Можаев Г. В. Задача о непрерывном обзоре поверхности Земли и кинематически правильные спутниковые системы // Косм. исслед. 1972. Т. 10, № 6. С. 833–840.

[14] Тахонов И. И. О некоторых задачах покрытия плоскости кругами // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 1. С. 84–102.

[15] Хачай М. Ю., Поберий М. И. Вычислительная сложность и аппроксимируемость серии геометрических задач о покрытии // Тр. ин-та математики и механики УРО РАН. 2012. Т. 18, № 3. С. 247–260.

[16] Шенмайер В. В. Задача о минимальном шаре, охватывающем k точек // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 1. С. 93–99.

[17] Ammari H. M. Challenges and opportunities of connected k-covered wireless sensor networks. Berlin; Heidelberg: Springer-Verl., 2009. 342 p.

[18] Bertsimas D., Vohra R. Rounding algorithms for covering problems // Math. Program. Ser. A. 1998. Vol. 80, No. 1. P. 63–89.

[19] Bezdek K. Über einige Kreisüberdeckungen // Beitr. Algebra Geom. 1983. Vol. 14. P. 7–13.

[20] Brimberg J., Drezner Z. A new heuristic for solving the p-median problem in the plane // Comput. Oper. Res. 2013. Vol. 40, No. 1. P. 427–437.

[21] Chvatal V. A greedy heuristic for the set covering // Math. Oper. Res. 1979. Vol. 4, No. 1. P. 233–235.

[22] Drezner Z. Facility location: A survey of applications and methods. New York: Springer-Verl., 1995. 571 p.

[23] Erzin A. I., Astrakov S. N. Min-density stripe covering and applications in sensor networks // Proc. 2011 Int. Conf. Comput. Sci. Its Appl. (Santander, Spain, June 20–23, 2011). Pt. III. Heidelberg: Springer-Verl., 2011. P. 152–162. (Lect. Notes Comput. Sci.; Vol. 6784).

[24] Garey M. R., Johnson D. S. Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman, 1979. 339 p.

[25] Hall N. G., Hochbaum D. S. A fast approximation algorithm for the multicovering problem // Discrete Appl. Math. 1986. Vol. 15, No. 1. P. 35–40.

[26] Hefeeda M., Bagheri M. Randomized k-coverage algorithms for dense sensor networks // Proc. 26th IEEE Int. Conf. Comput. Commun. INFOCOM-2007 (Anchorage,AK, Vay 6–12, 2007). Piscataway: IEEE, 2007. P. 2376–2380.

[27] Kononov A., Sevastianov S., Sviridenko M. A сomplete 4-parametric complexity classification of short shop scheduling problems // J. Scheduling. 2012. Vol. 15. P. 427-446.

[28] Krotoszynski S. Covering a disk with smaller disks // Stud. Sci. Math. Hung. 1993. Vol. 28, No. 3–4. P. 277–283.

[29] Megiddo N., Supowit K. J. On the complexity of some common geometric location problems // SIAM J. Comput. 1984. Vol. 13, No. 1. P. 182–196.

[30] Melissen H. Loosest circle coverings of an equilateral triangle // Math. Mag. 1997. Vol. 70, No. 2. P. 119–125.

[31] Melissen J. B. M., Schuur P. C. Improved coverings of a square with six and eight equal circles // Electron. J. Comb. 1996. Vol. 3, No. 1/R32. P. 1–10.

[32] Melissen J. B. M., Schuur P. C. Covering a rectangle with six and seven circles // Discrete Appl. Math. 2000. Vol. 99, No. 1–3. P. 149–156.

[33] Nurmela K. J. Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles // Exp. Math. 2000. Vol. 9, No. 2. P. 241–250.

[34] Nurmela K. J., Östergard P. R. J. Covering a square with up to 30 equal circles // Res. Rep. A62 Lab. Technology Helsinki Univ. 2000. Available at http://www.tcs.hut.fi/old/reports/A62abstract.html. Accessed Oct. 20, 2015.

[35] Tabirca T., Yang L. T., Tabirca S. Smallest number of sensors for k-covering // Int. J. Comput. Commun. Control. 2013. Vol. 8, No. 2. P. 312–319.

[36] Tarnai T., Gáspár Zs. Covering a square by equal circles // Elem. Math. 1995. Vol. 50. P. 167–170.

[37] Tóth G. F. Packing and covering // Handbook of discrete and computational geometry. Boca Raton, FL: CRC Press, 1997. P. 19–41.

[38] Tóth G. F. Thinnest covering of circle by eight, nine and ten congruent circles // Comb. Comput. Geom. New York: Cambridge Univ. Press, 2005. P. 361–376. (Math. Sci. Res. Inst. Publ.; Vol. 52).

[39] Verblunsky S. On the least number of unit circles which can cover a square // J. London Math. Soc. 1949. Vol. 24, No. 3. P. 164–170.