Extended Quality (eQual): Radial Threshold Clustering Based on <i>n</i> -ary Similarity

We are transforming Radial Threshold Clustering (RTC), an <i>O</i>(<i>N</i>²) algorithm, into Extended Quality Clustering (eQual), an <i>O</i>(<i>N</i>) algorithm with several novel features. Daura et al.'s RTC algorithm is a partitioning clustering algorithm that groups similar frames together based on their similarity to the seed configuration. RTC has two main issues: it scales as <i>O</i>(<i>N</i>²), making it inefficient for large frame counts, and its clustering results depend on the order of input frames whenever there is a tie in the most populated cluster. To address the first issue, we have increased the speed of the seed selection by using <i>k</i>-means++ to select the seeds of the available frames. To address the second issue and make the results invariant with respect to frame order, the densest and most compact cluster is chosen using the extended similarity indices. The new algorithm is able to cluster in linear time and produce more compact and separate clusters.