Geometric clusterings

V. Capoyleas, G. Rote, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    81 Citations (Scopus)
    2 Downloads (Pure)

    Abstract

    A k-clustering of a given set of points in the plane is a partition of the points into k subsets ("cluster"). For any fixed k, we can find a k-clustering which minimizes any monotone function of the diameters or the radii of the clusters in polynomial time. The algorithm is based on the fact that any two clusters in an optimal solution can be separated by a line.
    Original languageEnglish
    Pages (from-to)341-356
    Number of pages16
    JournalJournal of Algorithms
    Volume12
    Issue number2
    DOIs
    Publication statusPublished - 1991

    Fingerprint

    Dive into the research topics of 'Geometric clusterings'. Together they form a unique fingerprint.

    Cite this