Vi presenterar en datastruktur som gör det möjligt att förbehandla en rektilinjär polygon med n hörn så att, för två frågepunkter, den kortaste vägen i den rektilinjära länken eller L 1 -metrisk kan rapporteras i tid O(log n + k) där k är länklängden på den kortaste vägen. Om bara avståndet är av intresse, minskar frågetiden till O(log n). Dessutom, om frågepunkterna är två hörn, avståndet kan rapporteras i tid O(1) och en kortaste väg kan konstrueras i tid O (1 + k). Datastrukturen kan beräknas i tid O(n) och behöver O(n) lagring. Som en applikation presenterar vi en linjär tid algoritm för att beräkna diametern på en enkel rektilinear polygon w.r.t. L1-metrisken.
Förbehandlingstiden och utrymmet reducerades båda till O(n) av Schuierer REF (med O(log n) frågetid).
An Optimal Data Structure for Shortest Rectilinear Path Queries in a Simple Rectilinear Polygon
{'venue': 'Internat. J. Comput. Geom. Appl', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}