4446
правок
Декомпозиция на значительно удаленные пары для графа единичных дисков: различия между версиями
Материал из WEGA
Декомпозиция на значительно удаленные пары для графа единичных дисков (посмотреть исходный код)
Версия от 11:09, 16 марта 2018
, 16 марта 2018→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Кластеризация == Постановка задачи == '''Нотация''' Пусть дан…») |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
'''Нотация''' | '''Нотация''' | ||
Пусть дано конечное множество точек A в пространстве | Пусть дано конечное множество точек A в пространстве <math>\mathbb{R}^d</math>. Назовем его ''ограничивающим прямоугольником'' R(A) d-мерный гиперпрямоугольник <math>[a_1, b_1] \times [a_2, b_2 ] \times ... \times [a_d, b_d] \;</math>, содержащий A и имеющий минимальную протяженность по каждому измерению. | ||
Два множества точек A и B называются ''значительно удаленными'' относительно коэффициента удаленности s > 0, если существуют вещественное число r > 0 и две d-мерных сферы <math>C_A \;</math> и <math>C_B \;</math> радиуса r каждая, такие, что выполняются следующие соотношения. | |||
1. <math>C_A \cap C_B = \empty</math> | |||
2. <math>C_A \;</math> содержит ограничивающий прямоугольник R(A) множества A | |||
3. <math>C_B \;</math> содержит ограничивающий прямоугольник R(B) множества B | |||
Здесь |CACB| обозначает наименьшее евклидово расстояние между двумя точками в | 4. <math>|C_A C_B| \ge s \cdot r</math>. | ||
Здесь |CACB| обозначает наименьшее евклидово расстояние между двумя точками в <math>C_A \;</math> и <math>C_B \;</math>, соответственно. Пример приведен на рис. 1. Пусть даны ограничивающие прямоугольники R(A)и R(B). Для проверки, являются ли множества A и B значительно удаленными относительно s, требуется всего O(d) времени. | |||
