de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Finding k points with a smallest enclosing square

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45509

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

Locator
There are no locators available
Fulltext (public)

MPI-I-92-152.pdf
(Any fulltext), 7MB

Supplementary Material (public)
There is no public supplementary material available
Citation

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


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B712-2
Abstract
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.