УДК 519.146

Рассмотрение задачи о покрытии плоскости компактными многообразиями

Савинов Сергей Николаевич – младший научный сотрудник ООО «Лаборатория метеотехнологий».

Аннотация: В статье рассматривается задача о покрытии двумерного евклидова пространства компактными выпуклыми многообразиями. Определяются характеристики такого покрытия, нижние пределы этих характеристик и зависимость от размерностных параметров, а также охарактеризовано хроматическое число.

Ключевые слова: Двумерное многообразие, хроматическое число.

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

1. Построение минимальной монохроматической решетки.

На плоскости имеется множество отдельных компактных выпуклых областей, пусть задано условие - максимальный параметр а распределения компактных областей, такой что на расстоянии равном этому параметру нет точек, принадлежащих этим компактным областям. Возможно построить распределение выпуклых областей, так что будет выполнено условие параметра а и будет достигнуто максимальное покрытие плоскости. Максимальная площадь замкнутой области с выполнением условия параметра может быть только круг с диаметром величиной 2r = a . Выполнение условия параметра между компактными областями достигается образованием круговой окрестности в виде круга с добавочным радиусом величиной a (r = 2a) (рисунок 1, фигура a), максимально плотное расположение кругов равных диаметров на плоскости представляется в узлах решетки минимальной ячейкой которой является ромб со сторонами 2а (рисунок 1, фигура b). Это будет минимальная монохроматическая решетка, в которой при выполнении параметра а достигается максимальная плотность цвета для плоскости  (отношение площади трех секторов круга в вершинах треугольника радиусом 1/2а к площади равностороннего треугольника со стороной 2а).

Рисунок 1.

Хроматическое число есть минимальное количество минимальных монохроматических решеток полностью покрывающих плоскость компактными областями с допущением любого их расположения и пересечения (при сохранении структуры каждой решетки). Поскольку происходит наложение равноразмерных и равносимметричных решеток на плоскости, в каждой ячейке имеется только часть другой решетки – то есть оценка количества таких решеток может быть оценено по частям в одной ячейке.

Учитывая плотность покрытия одной монохроматической решетки, количество решеток для полного покрытия плоскости составляет без пересечений 4,41 решетки (χ> 4).

2. Покрытие многоугольника минимальным количеством кругов.

2.1 Конгруэнтное покрытие.

В данной статье под конгруэнтным покрытием понимается покрытие многоугольника меньшими конгруэнтными многоугольниками, число которых есть параметр конгруэнтного покрытия. Меньшие многоугольники расположены симметрично и плотно, так что выполняется правило: допускаются только контакты «ребро-ребро» или «вершина-вершина». Конгруэнтное покрытие является самым минимально возможным симметричным разделением многоугольника.

Определение минимального количества кругов покрывающих данный многоугольник производится по соотнесению покрывающих кругов с многоугольниками конгруэнтно покрывающими данный многоугольник.

При соизмерении круга с многоугольником (при соотношении количества 1/1), для выполнения правила «вершина-вершина» (вершины как наиболее удаленные точки от центра многоугольника), все вершины многоугольника должны лежать на окружности, поскольку наименьшая область контакта окружностей есть точка (точка совмещающая вершины многоугольников) – то есть минимальный круг максимально покрывающий многоугольникявляется описанным вокруг этого многоугольника (имеющий все его вершины на окружности).

Таким образом, минимальное количество (J) площадей кругов полностью покрывающих данный многоугольник M (с допустимостью пересечения окружностей) равно количеству малых многоугольников mконгруэнтно покрывающих данный многоугольник M, если каждый малый конгруэнтный многоугольник соизмерим с кругом по максимуму и минимуму. Величина  определяется отношением площади описанного кругом многоугольника к площади покрываемого многоугольника  (1).

Например, минимальное число кругов радиуса r покрывающих квадрат с стороной n, при 2r = n. Круг покрывает соизмеримый квадрат имеющий вершины на его окружности, если квадрат имеет сторону 0,7, площадь кругов покрывающих квадрат равно J=1,41. Целочисленная величина количества кругов есть округляемая дробь до следующего целого числа, то есть для квадрата равно 2. Величина 2 есть удельное количество площадей кругов покрывающих каждый квадрат при конгруэнтном покрытии ими плоскости, то есть образовании ими решетки стремящейся к бесконечности.

Например, для равностороннего треугольника со стороной A, покрытие кругами радиуса r, определяется соотношением (2) при A=4r J=5,333… площадей кругов или количество 6 кругов.

 

2.2 Соотнесение круга с ромбом.

Вершины ромба не могут быть расположены на описывающей его окружности, для минимального круга две из вершин находятся внутри окружности. Возможна такая описанная вокруг ромба окружность с частью вершин за пределами круга, а частью внутри круга, что при конгруэнтном расположении нескольких ромбов вне одних кругов покрыты другими кругами. В этом случае радиус описанной окружности будет средним геометрическим обеих полуосей ромба, то есть составлять 0,93B (B – большая полуось ромба). Таким образом, для ромба J=6,166, что соответствует количеству кругов 7 (рисунок 1, фигура c).

2.3 Индекс уникальности.

Предыдущие рассуждения относились к учету параметра а внутри замкнутой области покрывающей плоскость. Возможно учесть параметр a в отношении границ компактных областей (круг радиусом r), образующий круговую окрестность, соответственно общим радиусом . Окрестность определяет область уникальности для заданной группы компактных областей, принадлежащих ей. Соотношение площади окрестности к площади замкнутой области  (если эти площади конгруэнтны между собой и тождественны для всех компактных областей) определяет отношение числа групп (уникальных областей) к числу покрывающих компактных областей в двумерном пространства (плоскость) (3). Индекс уникальности есть сортировочное соотношение определяющее количество групп, поэтому является целочисленной величиной и может быть применен в отношении также целочисленной величины рассматриваемого количества областей.

Если свойством уникальности является цвет, то выражение  выражает долю полихромности для множества областей. Например, если рассмотреть указанную прежде окрестность величиной , то индекс уникальности принадлежащей её области с данным цветом составит 0,111…, индекс полихромности 0,888…, в случае минимальной монохроматической решетки, ромбическая ячейка которой минимально покрывается 7 круговыми областями (J = 6,166…), количество различных цветов составит 7 (6,222…).

Список литературы

1. Элементы комбинаторной и дифференциальной топологии. В.В.Прасолов.//М. Изд. МЦНМО. - 2004.
2. Торические действия в топологии и комбинаторике. В.М.Бухштабер, Т.Е.Панов.//М. Изд. МЦНМО. - 2004.
3. Лекции по алгебраической топологии. Основы теории гомотопий.М. М. Постников.// М. Наука. - 1984.
4. Топология. Г. Зейферт, В. Трельфалль.// М.НИЦ. - 2001 год.