A note on the unsolvability of the weighted region shortest path problem

DOI10.1016/J.COMGEO.2014.02.004MaRDI QIDQ2249044zbMATH OpenOpenAlexFDO

Authors Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, Megan Owen, Michiel Smid

Publication date 27 June 2014

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

computational geometryGalois theorysubdivisionunsolvabilityweighted region shortest paths

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Abstract: Let S be a subdivision of the plane into polygonal regions, where each region has an associated positive weight. The weighted region shortest path problem is to determine a shortest path in S between two points s, t in R^2, where the distances are measured according to the weighted Euclidean metric-the length of a path is defined to be the weighted sum of (Euclidean) lengths of the sub-paths within each region. We show that this problem cannot be solved in the Algebraic Computation Model over the Rational Numbers (ACMQ). In the ACMQ, one can compute exactly any number that can be obtained from the rationals Q by applying a finite number of operations from +, -, imes, div, sqrt[k]{}, for any integer k >= 2. Our proof uses Galois theory and is based on Bajaj's technique.

Recommendations

• The weighted region problem
• Approximate shortest homotopic paths in weighted regions
• Path refinement in weighted regions
• An efficient approximation algorithm for weighted region shortest path problem
• Approximate shortest paths in anisotropic regions

Cites work

• A survey of geodesic paths on 3D surfaces
• Determining approximate shortest paths on weighted polyhedral surfaces
• Galois group computation for rational polynomials
• Geodesics in CAT(0) cubical complexes
• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 3965441 (Why is no real title available?)
• scientific article; zbMATH DE number 1461254 (Why is no real title available?)
• scientific article; zbMATH DE number 1424303 (Why is no real title available?)
• Similarity of polygonal curves in the presence of outliers
• The algebraic degree of geometric optimization problems
• The algebraic degree of semidefinite programming
• The weighted region problem

Cited in

(10)

• Path refinement in weighted regions
• An (n^d) lower bound on the number of cell crossings for weighted shortest paths in d-dimensional polyhedral structures
• On approximating shortest paths in weighted triangular tessellations
• Similarity of polygonal curves in the presence of outliers
• On approximating shortest paths in weighted triangular tessellations
• Path planning in a weighted planar subdivision under the Manhattan metric
• A Steiner-point-based algorithm for approximate shortest paths in weighted equilateral-triangle meshes
• Computing shortest paths amid non-overlapping weighted disks
• Spanner for the 0/1/ weighted region problem
• Exact solutions to the weighted region problem

This page was built for publication: A note on the unsolvability of the weighted region shortest path problem

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