Matrix Searching with the Shortest-Path Metric

DOI10.1137/S0097539793253577MaRDI QIDQ4376191zbMATH OpenOpenAlexFDO

Authors John Hershberger, Subhash Suri

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) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• Geometric applications of a matrix-searching algorithm
• Applications of generalized matrix searching to geometric algorithms
• An Almost Linear Time Algorithm for Generalized Matrix Searching
• Computing geodesic furthest neighbors in simple polygons
• scientific article; zbMATH DE number 4051002

Cited in

(19)

• Maximal distortion of geodesic diameters in polygonal domains
• Rectilinear link diameter and radius in a rectilinear polygonal domain
• Applications of generalized matrix searching to geometric algorithms
• Convex hulls in polygonal domains
• A linear-time algorithm for the geodesic center of a simple polygon
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• \(L_{1}\) shortest path queries in simple polygons
• An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
• Rectilinear link diameter and radius in a rectilinear polygonal domain
• scientific article; zbMATH DE number 7559212 (Why is no real title available?)
• The geodesic diameter of polygonal domains
• Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
• Geometric path problems with violations
• Computing the geodesic centers of a polygonal domain
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain
• Pareto envelopes in simple polygons
• External matrix multiplication and all-pairs shortest path
• \(L_1\) geodesic farthest neighbors in a simple polygon and related problems
• The geodesic farthest-point Voronoi diagram in a simple polygon

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376191)