Problem: Given a set of points $S = \{(x_1, y_1), (x_2, y_2),\cdots,(x_n, y_n)\}$ in $\mathbb{R}^2$ and a distance threshold $\tau$, find a subset of $S$ such that (1) the Euclidean distance between any two points of the subset is not greater than $\tau$, and (2) the subset is maximum.

In a related post, Eppstein mentions that the problem can be solved in $O(n^3\log n)$. I wonder

  • Is there any improvement of the complexity since then?

  • If we instead enumerate the maximal ones, can it be in PTIME?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy