Enumerating the k closest pairs mechanically

Smid, Michiel; Lenhof, Hans-Peter

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

報告書

Enumerating the k closest pairs mechanically

MPS-Authors

/persons/resource/persons45509

Smid, Michiel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44909

Lenhof, Hans-Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

92-118_ch.pdf
(全文テキスト（全般）), 9MB

付随資料 (公開)

There is no public supplementary material available

引用

Smid, M., & Lenhof, H.-P.(1992). Enumerating the k closest pairs mechanically (MPI-I-92-118). Saarbrücken: Max-Planck-Institut für Informatik.

引用: https://hdl.handle.net/11858/00-001M-0000-0014-B6F1-3

要旨

Let $S$ be a set of $n$ points in $D$-dimensional space, where $D$ is a constant, and let $k$ be an integer between $1$ and $n \choose 2$. An algorithm is given that computes the $k$ closest pairs in the set $S$ in $O(n \log n + k)$ time, using $O(n+k)$ space. The algorithm fits in the algebraic decision tree model and is, therefore, optimal.