Geometric path problems with violations

DOI10.1007/s00453-016-0263-3zbMath1383.68093OpenAlexW2566564112MaRDI QIDQ1709576

Subhas C. Nandy, Sasanka Roy, Anil Maheshwari, Drimit Pattanayak, Michiel H. M. 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)

Related Items

Approximate Shortest Paths in Polygons with Violations, Unnamed Item

Cites Work

• Unnamed Item
• Applications of generalized matrix searching to geometric algorithms
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Rectilinear shortest paths in the presence of rectangular barriers
• Triangulating a simple polygon in linear time
• Computing minimum length paths of a given homotopy class
• \(k\)-violation linear programming
• Optimal shortest path queries in a simple polygon
• On geometric optimization with few violated constraints
• Euclidean Shortest Paths
• Fast Algorithms for Diameter-Optimally Augmenting Paths
• Improving the Stretch Factor of a Geometric Network by Edge Augmentation
• Optimal Search in Planar Subdivisions
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Matrix Searching with the Shortest-Path Metric
• AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
• Fibonacci heaps and their uses in improved network optimization algorithms
• Low-Dimensional Linear Programming with Violations
• Visibility Algorithms in the Plane