Geometric path problems with violations

DOI10.1007/S00453-016-0263-3MaRDI QIDQ1709576zbMATH OpenOpenAlexFDO

Authors Anil Maheshwari, Subhas C. Nandy, Drimit Pattanayak, Sasanka Roy, Michiel Smid

Publication date 6 April 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-016-0263-3

zbMATH Keywords

geometrygraphshortest pathsimple polygonsrectilinear polygonsviolations

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Approximate Shortest Paths in Polygons with Violations
• Approximate shortest paths in polygons with violations
• Shortest paths in the plane with obstacle violations
• Shortest paths in the plane with obstacle violations
• scientific article; zbMATH DE number 1256695

Cites work

• scientific article; zbMATH DE number 6792403 (Why is no real title available?)
• AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Applications of generalized matrix searching to geometric algorithms
• Computing minimum length paths of a given homotopy class
• Euclidean shortest paths. Exact or approximate algorithms.
• Fast algorithms for diameter-optimally augmenting paths
• Fibonacci heaps and their uses in improved network optimization algorithms
• Improving the Stretch Factor of a Geometric Network by Edge Augmentation
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Low-Dimensional Linear Programming with Violations
• Matrix Searching with the Shortest-Path Metric
• On geometric optimization with few violated constraints
• Optimal Search in Planar Subdivisions
• Optimal shortest path queries in a simple polygon
• Rectilinear shortest paths in the presence of rectangular barriers
• Triangulating a simple polygon in linear time
• Visibility Algorithms in the Plane
• k-violation linear programming

Cited in

(3)

• Approximate Shortest Paths in Polygons with Violations
• Shortest paths in the plane with obstacle violations
• Approximate shortest paths in polygons with violations

This page was built for publication: Geometric path problems with violations

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