A Simple Yet Fast Algorithm for the Closest-Pair Problem Using Sorted Projections on Multi-Dimensions


Dalkılıç M. E. , Ergun S.

28th International Symposium on Computer and Information Sciences (ISCIS), Paris, Fransa, 28 - 29 Ekim 2013, cilt.264, ss.23-34 identifier identifier

  • Cilt numarası: 264
  • Doi Numarası: 10.1007/978-3-319-01604-7_3
  • Basıldığı Şehir: Paris
  • Basıldığı Ülke: Fransa
  • Sayfa Sayıları: ss.23-34

Özet

We present a simple greedy algorithm, QuickCP, for finding the closest-pair of points on a plane. It is based on the observation that if two points are close to each other, then it is very likely that their sorted projections to x-axis and/or to y-axis will reflect that closeness. Therefore we order our search starting from the pairs with closest x-projections (and closest y-projections) to find the closest pair quickly and make a fast exit. Empirical data up to 2(26) (over 60 million points) indicates that this approach quickly detects the closest pair and it is, on average 70% faster than the classical divide-and-conquer algorithm registering, to the best of our knowledge, the fastest recorded solution times in the literature for the planar closest-pair problem. A second contribution of our work is that QuickCP can be used as part of the divide-and-conquer algorithms to handle small sub-problems. Measurements on data up to 2(26) points show that this co-operation speeds up the basic divide-and-conquer algorithm on average 50%.