Computing Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness
该论文通过细粒度复杂性分析,揭示了在计算平移下的 豪斯多夫距离时,维度、对称性(有向与无向)及离散性(连续与离散)之间复杂的相互作用,并针对连续有向情形提出了不对称的时间复杂度结果、证明了 时有向与无向变体的条件性分离,以及指出了离散情形在 时归约至 3SUM 问题从而限制了基于正交向量假设的下界证明。