0

For some project in computer vision I have N points in high-dimensional space. I want to select k of them that will be "the most distinguishable" from each other. For example, it can translate to sum of distances between chosen points is maximum. Or it can be that volume of polyhedron is maximum. But generally anything that has some intuition behind can go.

As expected I want to find these representative points.

There are two questions:

  • What definition for "the most distinguishable" points is more commonly used? Do they change the algorithm used to find those points?
  • What is the algorithm to find the points? It highly reminds me maximal weighted clique problem. Is it NP-hard problem? In this case can we make some good approximation against optimal solution?
Sergey Ivanov
  • 3,719
  • 7
  • 34
  • 59

1 Answers1

1

The way you define "the most distinguishable" will definitely affect the algorithm you'll want to use. for example, you can define "the most distinguishable" as the set with the maximal sum of distances between any two points in the set, but you could also define it as the set with the maximal minimum distance between any two points. these are two completely different problems.

As for algorithms, as I've said, that depends on your definition. If you're looking to find the K farthest points, you should look into this question. This problem is NP-Complete, but you may get some ideas about how to approach the problem.

Community
  • 1
  • 1
Ron Teller
  • 1,880
  • 1
  • 12
  • 23
  • I don't see any proof or convincing argument that the problem "K farthest points" is NP-complete in the question or answers you linked to – Niklas B. Feb 17 '14 at 16:53