Optical clustering

This paper presents a definition of ‘optical clusters’ which is derived from the concept of optical resolution. The clustering problem (induced by this definition) is transformed such that the application of well known Computational Geometry methods yields efficient solutions. One result (which can be extended to different classes of objects and metrices) is the following: Given a setS ofN disjoint line segments inE ².

1. The optical clusters with respect to a given separation parameterr∈R can be computed in timeO(Nlog² N).
2. Given an interval [a, b] for the numberm(S, r) of optical clusters which we want to compute, then timeO(N log² N)[O(Nlog² N+CN)] suffices to compute the interval [R(b),R(a)]={r∈R/m(S,r)∈[a,b]} [allC optical clusterings withR(b)≦ r≦R(a)].