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

Computing the similarity of two point sets is a ubiquitous task in medicalimaging, geometric shape comparison, trajectory analysis, and many moresettings. Arguably the most basic distance measure for this task is theHausdorff distance, which assigns to each point from one set the closest pointin the other set and then evaluates the maximum distance of any assigned pair.A drawback is that this distance measure is not translational invariant, thatis, comparing two objects just according to their shape while disregardingtheir position in space is impossible.  Fortunately, there is a canonical translational invariant version, theHausdorff distance under translation, which minimizes the Hausdorff distanceover all translations of one of the point sets. For point sets of size $n$ and$m$, the Hausdorff distance under translation can be computed in time $\tildeO(nm)$ for the $L_1$ and $L_\infty$ norm [Chew, Kedem SWAT'92] and $\tilde O(nm(n+m))$ for the $L_2$ norm [Huttenlocher, Kedem, Sharir DCG'93].  As these bounds have not been improved for over 25 years, in this paper weapproach the Hausdorff distance under translation from the perspective offine-grained complexity theory. We show (i) a matching lower bound of$(nm)^{1-o(1)}$ for $L_1$ and $L_\infty$ (and all other $L_p$ norms) assumingthe Orthogonal Vectors Hypothesis and (ii) a matching lower bound of$n^{2-o(1)}$ for $L_2$ in the imbalanced case of $m = O(1)$ assuming the 3SUMHypothesis.

Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation