Låt P vara en uppsättning av h pairwise-söndra polygonala hinder med totalt n hörn i planet. I detta dokument, vi anser problemet med att bygga en datastruktur som snabbt kan beräkna en L1 kortaste hinder-undvikande väg mellan två frågepunkter s och t. Vi bygger en datastruktur av storlek där k är antalet kanter på utmatningsvägen. Observera att n+h 2 ·log 2 h· 4 ε log h = O(n+h 2+ε ) för varje konstant ε > 0. Vi utökar också våra tekniker till den viktade rectilinear versionen där "obstacles" av P är rectilinear regioner med "vikter" och tillåter L1 vägar att resa genom dem med viktade kostnader. Vår algoritm besvarar varje fråga i O(log n + k) tid med en datastruktur av storlek O(n 2 · log n · 4 ε log n ) som är byggd i O(n 2 · log 2 n · 4 ε log n ) tid.
Nyligen, Chen et al. REF minskade frågetiden till O(log n) genom att bygga en datastruktur av storlek O(n + h 2 · log h · 4 ε log h ) i O(n + h 2 · log 2 h · 4 ε log h ) tid.
Two-Point L1 Shortest Path Queries in the Plane
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}