Finding k points with a smallest enclosing square

Smid, Michiel

アイテム詳細

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

一時保存へ追加

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

公開

報告書

Finding k points with a smallest enclosing square

MPS-Authors

/persons/resource/persons45509

Smid, Michiel
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.

フルテキスト (公開)

MPI-I-92-152.pdf
(全文テキスト（全般）), 7MB

付随資料 (公開)

There is no public supplementary material available

引用

Smid, M.(1992). Finding k points with a smallest enclosing square (MPI-I-92-152). Saarbrücken: Max-Planck-Institut für Informatik.

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

要旨

An algorithm is presented that, given a set of $n$ points in the plane and an integer $k$, $2 \leq k \leq n$, finds $k$ points with a smallest enclosing axes-parallel square. The algorithm has a running time of $O(n \log n + kn \log^{2} k)$ and uses $O(n)$ space. The previously best known algorithm for this problem takes $O(k^{2} n \log n)$ time and uses $O(kn)$ space.