Matrix Searching with the Shortest-Path Metric

DOI10.1137/S0097539793253577zbMath0885.68086OpenAlexW2016984768MaRDI QIDQ4376191

Subhash Suri, J. E. Hershberger

Publication date: 10 February 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539793253577

zbMATH Keywords

shortest pathsgeodesic diametergeometric matchingfarthest neighborsmatrix searching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Data structures (68P05)

Related Items (18)

Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Computing the geodesic centers of a polygonal domain ⋮ The geodesic diameter of polygonal domains ⋮ An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons ⋮ Maximal distortion of geodesic diameters in polygonal domains ⋮ Geometric path problems with violations ⋮ Computing the \(L_1\) geodesic diameter and center of a polygonal domain ⋮ \(L_{1}\) shortest path queries in simple polygons ⋮ Unnamed Item ⋮ Diffuse reflection radius in a simple polygon ⋮ A linear-time algorithm for the geodesic center of a simple polygon ⋮ PARETO ENVELOPES IN SIMPLE POLYGONS ⋮ Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Unnamed Item ⋮ The geodesic farthest-point Voronoi diagram in a simple polygon ⋮ \(L_1\) geodesic farthest neighbors in a simple polygon and related problems ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time

This page was built for publication: Matrix Searching with the Shortest-Path Metric