Med tanke på två polygonala kurvor i planet, det finns många sätt att definiera en uppfattning om likhet mellan dem. Ett mått som är mycket populärt är Fréchet-avståndet. Eftersom det har föreslagits av Alt och Godau 1992, har många varianter och förlängningar studerats. Inte desto mindre, ännu mer än 20 år senare, den ursprungliga O(n 2 log n) algoritm av Alt och Godau för beräkning av Fréchet avståndet förblir state of the art (här n betecknar antalet hörn på varje kurva). Detta har fått Helmut Alt att anta att det tillhörande beslutsproblemet är 3SUM-hårdt. I det senaste arbetet, Agarwal et al. visa hur man bryter den kvadratiska barriären för den diskreta versionen av Fréchet-avståndet, där man tar hänsyn till sekvenser av punkter i stället för polygonala kurvor. Vi bygger på deras arbete, ger vi en randomiserad algoritm för att beräkna Fréchet avståndet mellan två polygonala kurvor i tid O(n 2 ε log n(log log n) 3/2 ) på en pekarmaskin och i tid O(n 2 (log log n) 2 ) på ett ord RAM. Dessutom visar vi att det finns ett algebraiskt beslutsträd för beslutsproblemet på djup O(n 2−ε ), för vissa ε > 0. Detta ger bevis för att beslutsproblemet kanske inte är 3SUM-hårdt trots allt och avslöjar en spännande ny aspekt av detta välstuderade problem.
Nyligen, Buchin et al. REF visar att det finns ett verkligt algebraiskt beslutsträd för att lösa Fréchet-problemet med subkvadratdjup, vilket tyder på att så kanske inte är fallet.
Four soviets walk the dog -- with an application to Alt’s conjecture
{'venue': 'ArXiv', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}