4488
правок
Декомпозиция на значительно удаленные пары для графа единичных дисков: различия между версиями
Материал из WEGA
Декомпозиция на значительно удаленные пары для графа единичных дисков (посмотреть исходный код)
Версия от 11:16, 23 марта 2018
, 23 марта 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
Здесь | | Здесь <math>|C_A C_B| \;</math> обозначает наименьшее евклидово расстояние между двумя точками в <math>C_A \;</math> и <math>C_B \;</math>, соответственно. Пример приведен на рис. 1. Пусть даны ограничивающие прямоугольники R(A)и R(B). Для проверки, являются ли множества A и B значительно удаленными относительно s, требуется всего O(d) времени. | ||
| Строка 28: | Строка 28: | ||
Пусть дано множество S из n точек в пространстве <math>\mathbb{R}^d</math>. [[Декомпозиция на значительно удаленные пары|Декомпозицией S на значительно удаленные пары]] относительно коэффициента удаленности s является последовательность пар <math>(A_1, B_1), (A_2, B_2), ..., (A_m, B_m) \;</math>, такая, что | Пусть дано множество S из n точек в пространстве <math>\mathbb{R}^d</math>. [[Декомпозиция на значительно удаленные пары|Декомпозицией S на значительно удаленные пары]] относительно коэффициента удаленности s является последовательность пар <math>(A_1, B_1), (A_2, B_2), ..., (A_m, B_m) \;</math>, такая, что | ||
1. <math>A_i, B_i \subset S \;</math> для i = 1 | 1. <math>A_i, B_i \subset S \;</math> для i = 1...m | ||
2. <math>A_i \;</math> и <math>B_i \;</math> являются значительно удаленными относительно s для i = | 2. <math>A_i \;</math> и <math>B_i \;</math> являются значительно удаленными относительно s для i = 1...m | ||
3. Для любых точек <math>a, b \in S, a \ne b \;</math>, существует уникальный индекс i в интервале 1 | 3. Для любых точек <math>a, b \in S, a \ne b \;</math>, существует уникальный индекс i в интервале 1...m, такой, что имеет место либо <math>a \in A_i \;</math> и <math>b \in B_i \;</math>, либо <math>b \in A_i \;</math> и a <math>\in B_i \;</math>. | ||
