not sure if this is the right place to ask this but here it goes.
Let's assume I have some 2D points dataset consisting of facial landmarks, and I want to cluster these based on similarity so that I can refer to a notion of "prototype" of a facial expression.
As a measure between one point set and another I could be using a sum of euclidean distances.
Is there a way to obtain a set of prototypes without passing through the landmarks $O(n^2)$ times?
To better explain what I'm thinking, let's say I'm processing a video frame by frame.
I start with the landmarks of the first frame, and I put it in my list of prototypes because I have no other reference.
Following this, for each subsequent frame, I compare it with the first "prototype" and if it's below a certain similarity threshold I assume it's not unique enough and skip it, and so until I find one set of landmarks that are dissimilar enough, so now I have two "prototypes".
From this point onward, I need to do the similarity check with two "prototypes", and so on.
Another caveat is that I would also like to be able to store the "prototype" that the current frame matches the most.
I will also need to do a second pass through a second clip for a similar matching with the "prototypes" identified in the first pass.
Is there a more efficient way to do this, other than the naive approach?
