Fréchet avstånd ger ett naturligt och intuitivt mått för den populära uppgiften att beräkna likheten mellan två (polygonala) kurvor. Medan en enkel algoritm beräknar det i nära-kvadratisk tid, en starkt subkvadratisk algoritm kan inte existera om Strong Exponential Time Hypothesis misslyckas. Ändå är snabba praktiska genomföranden av Fréchet-avståndet, särskilt för realistiska ingångskurvor, mycket önskvärda. Detta har även lett till en utsedd tävling, ACM SIGSPAIAL GIS Cup 2017: Här var utmaningen att genomföra en näraliggande datastruktur under Fréchet avstånd. Flaskhalsen i de tre främsta genomförandena visade sig vara exakt beslutsförfarandet för Fréchet-avståndet. I detta arbete presenterar vi ett snabbt, certifierande genomförande för att bestämma Fréchet avstånd, för att 1) komplettera sin pessimistiska värsta fall hårdhet genom en empirisk analys av realistiska indata och (2) förbättra den senaste tekniken för GIS Cup utmaningen. Vi utvärderar vår implementering experimentellt på ett stort riktmärke bestående av flera datamängder (inklusive handskrivna tecken och GPS-banor). Jämfört med den vinnande implementeringen av GIS Cup, får vi driftstidsförbättringar på upp till två storleksordningar för beslutsförfarandet och upp till en faktor på 30 för frågor till nästan granne datastrukturen. Beräkningsteori → Beräkningsgeometri, beräkningsteori → Utformning och analys av algoritmer
Algoritmteknik för Fréchet avstånd REF beskriver en förbättrad version av en av de bästa algoritmerna som utvecklades av deltagarna i GIS Cup 2017.
Walking the Dog Fast in Practice: Algorithm Engineering of the Fr\'echet Distance
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}