kd-match

Finding the correspondances between catalogues of objects has long been a goal of astronomy. Generally, one first must place both catalgoues on the same coordinate system and then search in two dimensions for the nearest neighbour in the second catalogue of each object in the first catalogue. Often one does not know the coordinate transformation between the catalogues initially, so part of the first step is to determine this transformation. Finding the transformation between the coordinate systems also basicially involves a search for objects that correspond to each other in each catalgoue and are invariant under the transformation. Groth (1986) introduced the technique of looking for similar trian- gles in two catalogues. The property of similarity is invari- ant under translation, rotation, magnification and inversion. The algorithm outlined in this paper uses the ratio of sides as the invariant under the coordinate transformation as in Valdes et al. (1995) and searches for several triangles with similar transformations. In the end even a small catalogue can result in a large number of triangles to search in a cat- alogue: N(N − 1)(N − 2)/6 or on the order of N_1^3 N_2^3 comparisions to make. Several authors (e.g. Valdes et al. 1995) have outlined techniques to accelerate the calculation of the triangles (O(N2) vs. O(N3)) at the expense of storing information and accelerating the search process which decreases the prefactor on O(N13N23) by presorting the triangles (Valdes et al. 1995), weighting the triangles by the magnitudes of the stars (Scholl 1994), culling the triangles to compare (P ́al & Bakos 2006) or quitting after only a fraction of the triangles have been compared and a sufficiently good fit is determined (Tabur 2007).

Both finding the matching triangles and later the matching objects in the catalogues require finding neigh- bours in a two-dimensional space. If the space were one dimensional, one would use a binary tree to search in log N time. Bentley (1975) developed a generalisation of the binary tree for arbitrary number of dimensions, the k-d tree. In this case k equals two. This algorithm dramatically speeds the search over the two dimensions, and runs the search for the astrometry.net algorithm (Lang et al. 2010). In particular, the process of finding the nearest neighbour in the two cat- alogues is sped up from O(N1N2) to O [(N1 + N2) log N2]. For the triangle search the improvement is even more dra- matic from O(N13N23) to O (N13 + N23) log N2 .

The dramatic acceleration of the determination of the transformation encourages a generalisation of the triangle matching technique of Groth (1986). In particular the property of similarity of triangles is invariant under translation, rotation, magnification and inversion but not shearing. If there is an significant shearing between the two coordinate systems, a triangle matching algorithm will fail. However, it is straightforward to generalise this techinque for a general affine transformation. Such a transformation will preserve the ratio of areas, so the new technique is to build quadrilaterals from sets of four objects in each catalogue and calculate the ratio of areas of the triangles that comprise the quadrilaterals. Only two of the three area ratios are independent so the final search is again two dimensional. However, the number of quadrilaterals is huge N (N − 1)(N − 2)(N − 3)/24 or on the order of N14N24 direct comparisons to make. The k-d tree accelerates this quadrilateral search dramatically to O (N4 + N4) log N2 , so it is even faster than the customary direct search over triangles.