Дано: Дано множество из N точек в 2D-плоскости (координаты x и y) и множество из N радиусов, соответствующих каждой точке. Мы будем называть диск точки диском с центром в точке с ее радиусом.
Проблема: Сгруппируйте точки. Кластер точек таков, что каждая точка ЛИБО попадает в диск, по крайней мере, одной другой точки в кластере ИЛИ, по крайней мере, еще одна точка в кластере попадает в его диск. Кластеры отдельных точек не считаются кластерами.
Мне нужен алгоритм для эффективного вычисления этого (желательно без использования сложных методов пространственного хеширования, таких как kd-деревья). Я могу согласиться на время выполнения O (N ^ 2), но определенно не больше, чем O (N ^ 3). Я чувствую, что это должно быть просто, но я увлекся невзаимной природой моего состояния кластеризации.
По сути, я ищу заполнить прототип функции C:
int cluster_points(
size_t n,
point_t *pt, // length n list of points
double *radius, // length n list of radii for each point
int *cluster, // length n list of cluster indexes; -1 if not clustered
size_t *ncluster // number of clusters (number of distinct non -1 entries in cluster)
);
Это не домашняя работа. Это нужно мне как часть матричного алгоритма кластеризации комплексных чисел.