MPI-INF/SWS Research Reports 1991-2021
2. Number - only D1
MPI-I-92-152
Finding k points with a smallest enclosing square
Smid, Michiel
November 1992, 8 pages.
.Status: available - back from printing
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.
-
MPI-I-92-152.pdf
- Attachement: MPI-I-92-152.pdf (6669 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1992-152
BibTeX@TECHREPORT{Smid92,
AUTHOR = {Smid, Michiel},
TITLE = {Finding k points with a smallest enclosing square},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-92-152},
MONTH = {November},
YEAR = {1992},
ISSN = {0946-011X},
}