4551
правка
Связное доминирующее множество: различия между версиями
Материал из WEGA
Связное доминирующее множество (посмотреть исходный код)
Версия от 14:41, 23 января 2013
, 23 января 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
В этом построении главным образом используются техники неадаптивного разбиения и сдвига. В общем случае ход действий примерно таков: вначале квадрат, содержащий все вершины исходного графа единичных дисков, разделяется на решетку из небольших ячеек. Каждая из этих ячеек далее разбивается на две области – центральную и граничную. Центральная область состоит из точек, находящихся на расстоянии h от границы ячейки. Граничная область состоит из точек, расстояние от которых до границы ячейки составляет не более h + 1. Таким образом, эти области перекрываются. После этого минимальное объединение связных доминирующих множеств вычисляется в каждой ячейке для связных компонент центральной области ячейки. Основная задача состоит в том, чтобы доказать, что объединение всех таких минимальных объединений не превышает минимального связного доминирующего множества для всего графа. Для вершин, не принадлежащих к центральным областям, для вычисления доминирующего множества используется часть 8-аппроксимации, лежащая в граничных областях. Вместе с упоминавшимся ранее объединением она образует связное доминирующее множество для всего исходного графа единичных дисков. Перемещая решетку для получения разбиения по разным координатам, можно получить разбиение с граничной областью, имеющей очень малую верхнюю границу. | В этом построении главным образом используются техники неадаптивного разбиения и сдвига. В общем случае ход действий примерно таков: вначале квадрат, содержащий все вершины исходного графа единичных дисков, разделяется на решетку из небольших ячеек. Каждая из этих ячеек далее разбивается на две области – центральную и граничную. Центральная область состоит из точек, находящихся на расстоянии h от границы ячейки. Граничная область состоит из точек, расстояние от которых до границы ячейки составляет не более h + 1. Таким образом, эти области перекрываются. После этого минимальное объединение связных доминирующих множеств вычисляется в каждой ячейке для связных компонент центральной области ячейки. Основная задача состоит в том, чтобы доказать, что объединение всех таких минимальных объединений не превышает минимального связного доминирующего множества для всего графа. Для вершин, не принадлежащих к центральным областям, для вычисления доминирующего множества используется часть 8-аппроксимации, лежащая в граничных областях. Вместе с упоминавшимся ранее объединением она образует связное доминирующее множество для всего исходного графа единичных дисков. Перемещая решетку для получения разбиения по разным координатам, можно получить разбиение с граничной областью, имеющей очень малую верхнюю границу. | ||
Приведем более детальное описание процесса построения. | |||
Пусть дан исходный связный граф единичных дисков G = (V, E), располагающийся в квадрате <math>Q = \big\{ (x, y) | 0 \le x \le q, 0 \le y \le q \big\}\ </math>, где <math>q \le |V|</math>. Для построения приближенного решения с коэффициентом эффективности <math>1 + \varepsilon\ </math> для <math>\varepsilon\ > 0</math> выберем целое число <math>m = O((1/ \varepsilon\ )ln(1/ \varepsilon\ ))</math>. Пусть <math>p = \mathcal{b} q/m \mathcal{c} + 1</math>. Рассмотрим квадрат <math>\bar{Q} = \big\{ (x, y) | - m \le x \le mp, - m \le y \le mp \big\} </math>. Разобьем <math>\bar{Q}</math> на <math>(p + 1) \times (p + 1)</math> решеток таким образом, что каждая ячейка представляет собой квадрат <math>m \times m</math>, за исключением верхней и правой границ; следовательно, никакие две ячейки не перекрываются друг с другом. Обозначим это разбиение квадрата <math>\bar{Q}</math> как P(0) (см. рис.). В общем случае разбиение P(a) получается из P(0) в результате сдвига нижнего левого угла Q из точки (—m,—m) в точку (—m + a,—m+ a). Заметим, что в результате сдвига из P(0) в P(a) для <math>0 \le a \le m</math> квадрат Q оказывается покрыт разбиением. | |||
[[Файл:CDS_1.jpg]] | [[Файл:CDS_1.jpg]] | ||
| Строка 30: | Строка 34: | ||
Для каждой ячейки e (представляющей собой квадрат <math>m \times m</math>) <math>C_e(d) \; </math> обозначает множество точек в e, удаленных от границы на расстояние не менее d; <math>C_e(0) \; </math> представляет саму ячейку e. Обозначим <math>B_e(d) = C_e(0) - C_e(d) \; </math>. Зафиксируем положительное целое число <math>h = 7 + 3 \mathcal{b} log_2(4m^2/ \pi\ ) \mathcal{c} </math>. Назовем <math>C_e(h) \; </math> ''центральной областью'' ячейки e, а <math>B_e(h + 1) \; </math> – ''граничной областью'' ячейки e. Таким образом, центральная и граничная области каждой ячейки перекрываются на полосу единичной ширины. | |||
