Fréchet avstånd är ett välstuderat och mycket populärt mått på likhet av två kurvor. Många varianter och förlängningar har studerats sedan Alt och Godau införde denna åtgärd till beräkningsgeometri 1991. Deras ursprungliga algoritm för att beräkna Fréchet avstånd av två polygonala kurvor med n hörn har en körtid av O(n 2 log n). Mer än 20 år senare, state of the art algoritmer för de flesta varianter tar fortfarande tid mer än O(n 2 / log n), men inga matchande lägre gränser är kända, inte ens under rimlig komplexitet teoretiska antaganden. För att få en villkorlig lägre gräns antar vi i detta dokument den starka exponentiella tidshypotesen eller, mer exakt, att det inte finns någon O * ((2 − δ) N ) algoritm för CNF-SAT för någon δ > 0. Enligt detta antagande visar vi att Fréchet-avståndet inte kan beräknas i starkt subkvadratisk tid, dvs. med tiden O(n 2−δ ) för alla δ > 0. Detta innebär att det är lika svårt att hitta snabbare algoritmer för Fréchet-avståndet som att hitta snabbare CNF-SAT-algoritmer, och förekomsten av en starkt subquadratisk algoritm kan anses osannolik. Vårt resultat håller för både det kontinuerliga och det diskreta Fréchet-avståndet. Vi utökar huvudresultatet i olika riktningar. Baserat på samma antagande vi (1) visar icke-existens av en starkt subkvadratisk 1.001- approximation, (2) presentera snäva nedre gränser i fall antalet hörn av de två kurvorna är obalanserade, och (3) undersöka realistiska indata antaganden (c-packade kurvor).
Nya resultat visar att om man antar stark exponentiell tidshypotes, starkt subquadratiska tid algoritmer är omöjliga REF för Fréchet.
Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails
{'venue': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'journal': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}