Routing in Polygonal Domains

DOI10.4230/LIPIcs.ISAAC.2017.10zbMath1457.68202arXiv1703.09533OpenAlexW2783321216MaRDI QIDQ5136225

Paul Seiferth, Wolfgang Mulzer, Marcel Roeloffzen, Yannik Stein, Max Willert, Man-Kwun Chiu, André van Renssen, Birgit Vogtenhuber, Bahareh Banyassady, Matias Korman

Publication date: 25 November 2020

Full work available at URL: https://arxiv.org/abs/1703.09533

zbMATH Keywords

routing schemepolygonal domainsYao graphsmall stretch

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (2)

Bounded-degree spanners in the presence of polygonal obstacle ⋮ Compact Routing in Unit Disk Graphs

Cites Work

• Unnamed Item
• Compact and low delay routing labeling scheme for unit disk graphs
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Visibility of disjoint polygons
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Corrections to Lee's visibility polygon algorithm
• A new algorithm for shortest paths among obstacles in the plane
• An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
• Routing in unit disk graphs
• Compact Routing with Minimum Stretch
• New Routing Techniques and their Applications
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Improved routing strategies with succinct tables
• Labelling and Implicit Routing in Networks
• Visibility of a simple polygon
• Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles
• Competitive Local Routing with Constraints
• Approximate distance oracles
• On Shortest Paths in Polyhedral Spaces
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Shortest paths in the plane with polygonal obstacles
• TRIANGULATING DISJOINT JORDAN CHAINS
• A trade-off between space and efficiency for routing tables
• Compact routing schemes with low stretch factor
• Compact routing schemes with improved stretch
• Compact oracles for reachability and approximate distances in planar digraphs
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
• Close to linear space routing schemes

This page was built for publication: Routing in Polygonal Domains