Optimal algorithms for complete linkage clustering in d dimensions

Drago Krznaric, Christos Levcopoulos

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceedingPeer review

    Sammanfattning

    It is shown that the complete linkage clustering of n points in R-d, where d greater than or equal to 1 is a constant, can be computed in optimal O(nlogn) time and linear space, under the L-1 and L-infinity-metrics. Furthermore, for every other fixed L-t-metric, it is shown that it can be approximated within an arbitrarily small constant factor in O(nlogn) time and linear space.
    Originalspråkengelska
    Titel på värdpublikationTheoretical Computer Science
    FörlagElsevier
    Sidor139-149
    Volym286
    DOI
    StatusPublished - 2002

    Publikationsserier

    Namn
    Nummer1
    Volym286
    ISSN (tryckt)0304-3975

    Ämnesklassifikation (UKÄ)

    • Datavetenskap (datalogi)

    Fingeravtryck

    Utforska forskningsämnen för ”Optimal algorithms for complete linkage clustering in d dimensions”. Tillsammans bildar de ett unikt fingeravtryck.

    Citera det här