Задано: Учитывая множество N точек в 2D плоскости (координаты x и y) и множество N радиусов, соответствующих каждой точке. Мы будем ссылаться на точечный диск как диск, центрированный в точке с его радиусом.
Проблема: Скопируйте точки. Кластер точек таков, что каждая точка EITHER попадает в диск по меньшей мере одной другой точки в кластере ИЛИ, по крайней мере, одна другая точка в кластере попадает в ее диск. Кластеры отдельных точек не считаются кластерами.
Мне нужен алгоритм для его эффективного вычисления (желательно, не прибегая к сложным методам пространственного хэширования, таким как 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)
);
Это не домашнее задание. Мне нужно это как часть матричного алгоритма кластеризации комплексных чисел.
