Optical clustering (Q1100928)

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 set S of N disjoint line segments in \(E^ 2\). (a) The optical clusters with respect to a given separation parameter \(r\in {\mathbb{R}}\) can be compared in time O(N log\({}^ 2 N)\). (b) Given an interval [a,b] for the number m(S,r) of optical clusters which we want to compute, then time O(N log\({}^ 2 N)\) [O(N log\({}^ 2 N+CN)]\) suffices to compute the interval \([R(b),R(a)]:=\{r\in {\mathbb{R}} |\) m(S,r)\(\in [a,b]\}\) [all C optical clusterings with R(b)\(\leq r\leq R(a)]\).