VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • On ▫$k$▫-means for segments and polylines [Elektronski vir]
    Cabello, Sergio ; Giannopoulos, Panos
    We study the problem of ▫$k$▫-means clustering in the space of straight-line segments in ▫$\mathbb{R}^{2}$▫ under the Hausdorff distance. For this problem, we give a ▫$(1+\varepsilon)$▫-approximation ... algorithm that, for an input of ▫$n$▫ segments, for any fixed ▫$k$▫, and with constant success probability, runs in time ▫$O(n+ \varepsilon^{-O(k)} + \varepsilon^{-O(k)}\cdot \log^{O(k)} (\varepsilon^{-1}))$▫. The algorithm has two main ingredients. Firstly, we express the ▫$k$▫-means objective in our metric space as a sum of algebraic functions and use the optimization technique of Vigneron to approximate its minimum. Secondly, we reduce the input size by computing a small size coreset using the sensitivity-based sampling framework by Feldman and Langberg. Our results can be extended to polylines of constant complexity with a running time of ▫$O(n+ \varepsilon^{-O(k)})$▫.
    Vir: 31st Annual European Symposium on Algorithms [Elektronski vir] : ESA 2023, September 4–6, 2023, Amsterdam, The Netherlands (14 str.)
    Vrsta gradiva - prispevek na konferenci ; neleposlovje za odrasle
    Leto - 2023
    Jezik - angleški
    COBISS.SI-ID - 164055811

    Povezava(-e):

    https://drops.dagstuhl.de/opus/volltexte/2023/18681/
    DOI

Vnos na polico