In this paper we present an original algorithm and data structures to solve the Bichromatic Closest Pair problem in metrics <$E L sub 1>. We got O(n) time for the case of sets, each of which is coincided with the set of its maximums regarding to dominance, and O(nlogn) time in general. In addition, we offer a modification randomized Khuller and Matthias algorithm\cite{b3}, which improves performance. So, Khuller and Matias algorithm approximates minimal distance with the closeness of multiplicative constant, that is if d-minimal distance, and <$E d sup *>-approximation, then <$E d sup *~symbol Г~d~symbol Г~ad sup *>, where a >> 1. In standard situation, a = 4, but this result can be perfected to 1 + e, for any e >> 0, keeping the linear time algorithm.

Індекс рубрикатора НБУВ: З970.630

Рубрики:

Комп'ютерна геометрія

Шифр НБУВ: Ж23887 Пошук видання у каталогах НБУВ 

---

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"