Computing Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness
Questo lavoro analizza la complessità computazionale fine della distanza di Hausdorff tra insiemi di punti sotto traslazioni, rivelando come dimensione, simmetria (distanza diretta vs. indistinta) e discrezione (continuo vs. discreto) influenzino in modo intricato i limiti superiori e inferiori del tempo di esecuzione, fornendo nuovi algoritmi quasi-lineari e dimostrando la durezza condizionale per diverse varianti del problema.