Том 21, номер 1, 2014 г., Стр. 84–102

УДК 519.8
И. И. Тахонов
О некоторых задачах покрытия плоскости кругами

Аннотация:
Исследуются регулярные покрытия плоскости кругами. В таких покрытиях плоскость разбивается на правильные многоугольные плитки и все плитки покрываются одинаково. Под плотностью регулярного покрытия понимается отношение площади частей кругов, покрывающих плитку, к площади этой плитки. Ищутся наименее плотные покрытия кругами четырёх, пяти и шести радиусов. Установлены нижние границы на плотность, зависящие от радиусов входящих в покрытие кругов. Для некоторых известных покрытий показана их оптимальность в соответствующих классах. Построены новые покрытия, оптимальные в своих классах при дополнительных ограничениях на радиусы кругов. 
Ил. 14, библиогр. 15.

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

Тахонов Иван Иванович ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: takhonov@gmail.com

Статья поступила 29 декабря 2012 г.
Исправленный вариант — 19 апреля 2013 г.

Литература

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

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

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

[4] Ерзин А. И., Плотников Р. В. Максимизация времени функционирования покрытий в условиях ограниченности ресурсов их элементов // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, № 6. - C. 17–32.

[5] Ерзин А. И., Плотников Р. В., Шамардин Ю. В. О некоторых полиномиально разрешимых случаях и приближённых алгоритмах для задачи построения оптимального коммуникационного дерева // Дискрет. анализ и исслед. операций - 2013. - Т. 20, № 1. - C. 12–27.
Erzin A. I., Plotnikov R. V., Shamardin Yu. V. On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem // J. Appl. Industr. Math. - 2013. - Vol. 7, N2. - P. 142–152.

[6] Тот Л. Ф. Расположения на плоскости, на сфере и в пространстве. - М.: Физматгиз, 1958. - 364 c.

[7] Cardei M.,Wu J., Lu M. Improving netwotk lifetime using sensors with adjustible sensing ranges // Int. J. Sensor Networks. - 2006. - Vol. 1, N 1–2. - P. 41–49.

[8] Erzin A., Astrakov S. Min-density stripe covering and applications in sensor networks // Berlin; Heidelberg: Springer-Verl., 2011. - P. 152–162. (Lect. Notes Comput. Sci.; Vol. 6784).

[9] Erzin A., Plotnikov R. Wireless sensor network’s lifetime maximization problem in case of given set of covers // Berlin; Heidelberg: Springer-Verl., 2011. - P. 44–57. (Lect. Notes Comput. Sci.; Vol. 6786).

[10] Kershner R. The number of circles covering a set // Amer. J. Math. - 1939. - Vol. 61, N 3. - P. 665–671.

[11] Nguen N. D., Zalyubovsky V., Ha M. Th., Le T. D., Choo H. Energy-efficient models for coverage problem in sensor networks with adjustable ranges // Ad Hoc & Sensor Wireless Networks. - 2012. - Vol. 16. - P. 1–28.

[12] Toth F. G. Covering the plane with two kinds of circles // Discrete Comput. Geometry. - 1995. - Vol. 13, N 3. - P. 445–457.

[13] Wu J., Dai F. Virtual backbone construction in MANETs using adjustable transmission ranges // IEEE Trans. Mobile Comput. - 2006. - Vol. 5, N 9. - P. 1188–1200.

[14] Wu J., Yang S. Energy-efficient node scheduling models in sensor networks with adjustible ranges // Int. J. Foundat. Comput. Sci. - 2005. - Vol. 16, N 1. P. 3–17.

[15] Zalyubovskiy V., Erzin A., Astrakov S., Choo H. Energy-efficient area coverage by sensors with adjustable ranges // Sensors. - 2009. - Vol. 9. - P. 2446–2460.