de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Finding k points with a smallest enclosing square

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45509

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-92-152.pdf
(beliebiger Volltext), 7MB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


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