A divide-and-conquer based preprocessing for routing in a simple polygon

DOI10.1007/S10878-025-01345-9MaRDI QIDQ6912363zbMATH OpenFDO

Authors Siddharth Gaur, Rajasekhar Inkulu

Publication date 22 October 2025

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10878-025-01345-9

zbMATH Keywords

approximation algorithmscomputational geometrygeometric routinggeometric shortest paths

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites work

• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• A trade-off between space and efficiency for routing tables
• Approximate distance oracles
• Compact routing schemes with improved stretch
• Compact routing with minimum stretch
• Competitive local routing with constraints
• Computational geometry. Algorithms and applications.
• Constrained routing between non-visible vertices
• Efficient construction of a bounded-degree spanner with low weight
• Euclidean shortest paths in the presence of rectilinear barriers
• Geometric Spanner Networks
• scientific article; zbMATH DE number 1629819 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 910885 (Why is no real title available?)
• scientific article; zbMATH DE number 7650244 (Why is no real title available?)
• Improved routing strategies with succinct tables
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• New constructions of SSPDs and their applications
• New routing techniques and their applications
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On sparse spanners of weighted graphs
• Optimal shortest path queries in a simple polygon
• Planar spanners and approximate shortest path queries among obstacles in the plane
• Routing among convex polygonal obstacles in the plane
• Routing among convex polygonal obstacles in the plane
• Routing in polygonal domains
• Spanners for geodesic graphs and visibility graphs
• The complexity of geodesic spanners

Cited in

(1)

• Routing among convex polygonal obstacles in the plane using a simplified domain

This page was built for publication: A divide-and-conquer based preprocessing for routing in a simple polygon

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