Assumption to make on data so that we can have an approximation of the final number of representatives Let $t$ be a distance threshold (user-defined parameter). $X$ is a dataset containing some $p$-dimensional data-points. $L$ is a list of representative-data collected from $X$. Given the following simple algorithm (in pseudocode):
L = []
for each x in X:
   d = min dist(x, c), for c in L
   if d > t:
      add x to L

What is the weakest thing we can assume on the data, so that we would be able to determine the complexity in terms of the final size of $L$ (i.e. $|L|$)?
 A: Here's just one of possibly many assumptions I suspect is necessary: your data are continuous. ordinal data sometimes have uneven distances between values (ranks) when they represent limited information about an underlying, continuous distribution. Therefore you wouldn't want to assume that $d>t$ if $t$ is meant to represent a threshold distance on that underlying, continuous distribution. For example, if $x=1$ and $c=3$, the $d=2$ (if this does happen to be the min dist in $L$) can represent a very different distance than if $x=12$ and $c=14$ in terms of the underlying continuous distribution. Say that underlying distribution is finishing time for a footrace, and the values of $x$ and $c$ represent the order in which the runners cross the finish line. It's not at all uncommon for one person to cross the finish line far ahead of the competition, or vice versa.
Again, this is just one of probably many assumptions that may be necessary, depending largely on what you want the threshold to mean.
