En yakın nokta problemleri için projeksiyon tabanlı yaklaşımlar üzerine bir çalışma

Bu tezde en yakın çift problemi için yeni bir çözüm öneren yakın zamanda sunulmuş QuickCP algoritması (Dalkılıç ve Ergun, 2012) tekdüze, üstel ve normal dağılımlarda incelenmiştir. Veri noktaları çizgisel sıralanma sergilediğinde QuickCP algoritmasının performansı önemli ölçüde düştüğünden, QuickCP algoritmasının rastgeleleştririlmiş QuickCP adında yeni bir sürümü geliştirilmiştir. QuickCP algoritmasının rasgeleleştirme süreci, Gram-Schmidt metoduyla elde edilen ortonormal baz vektörler kullanmaktadır. QuickCP ve rastgeleleştirilmiş QuickCP algoritmaları, noktaların en yakın çiftini bulmak için klasik Böl ve Fethet algoritması ile Kaba Kuvvet algoritmasına karşı çok boyutlu uzaylarda ve farklı dağılımlarda test edilmiştir. QuickCP ve Kaba Kuvvet algoritmalarının çok boyutlu uzaylara genişletilmesi kolay iken, klasik Böl ve Fethet algoritması ile rastgeleleştirilmiş QuickCP algoritmalarının çok boyutlu uzaylara genişletilmesi bu çalışmanın bir parçası olarak geliştirilmiştir. Geniş ölçüde yapılan karşılaştırmalar 2, 3, 4 ve 5 boyutlu öklit uzaylarında rastgeleleştirilmiş QuickCP algoritmasının çizgisel sıralamalı dağılımlar dâhil tüm dağılımlarda rakiplerinden daha iyi performans sergilediğini göstermektedir.