English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We give algorithms for computing coresets for $(1+\varepsilon)$-approximate$k$-median clustering of polygonal curves (under the discrete and continuousFr\'{e}chet distance) and point sets (under the Hausdorff distance), when thecluster centers are restricted to be of low complexity. Ours is the first suchresult, where the size of the coreset is independent of the number of inputcurves/point sets to be clustered (although it still depends on the maximumcomplexity of each input object). Specifically, the size of the coreset is$\Theta\left(\frac{k^3lm^{\delta}d}{\varepsilon^2}\log\left(\frac{kl}{\varepsilon}\right)\right)$ for any $\delta > 0$, where $d$ is theambient dimension, $m$ is the maximum number of points in an input curve/pointset, and $l$ is the maximum number of points allowed in a cluster center. Weformally characterize a general condition on the restricted space of clustercenters -- this helps us to generalize and apply the importance samplingframework, that was used by Langberg and Schulman for computing coresets for$k$-median clustering of $d$-dimensional points on normed spaces in$\mathbb{R}^d$, to the problem of clustering curves and point sets using theFr\'{e}chet and Hausdorff metrics. Roughly, the condition places an upper boundon the number of different combinations of metric balls that the restrictedspace of cluster centers can hit. We also derive lower bounds on the size ofthe coreset, given the restriction that the coreset must be a subset of theinput objects.

Coresets for $k$-median clustering under Fr\'{e}chet and Hausdorff distances