Есть ли известный эффективный алгоритм для нахождения ближайшей группы из трех точек в облаке?
Это похоже на ближайшую пару проблем точек, но я ищу три точки вместо двух.
Edit
Определение "ближайшего" будет влиять на сложность алгоритма. Как отметил Jack, поиск минимального треугольника области 3sum-hard и в любом случае не очень подходит для моего приложения.
Я надеюсь, что существует более эффективный алгоритм поиска минимального периметра (т.е. | AB | + | AC | + | BC |) треугольник или что-то подобное (например, минимум | AB | ² + | AC | ² + | BC | ².) Я не знаю, почему это должно быть 3sum-hard, поскольку существование 3 коллинеарных точек в другом месте не повлияет на результат.
Примечание. Мои точки имеют восемь измерений, поэтому любой алгоритм, ограниченный меньшим размером, не подходит.