Loading...
Please wait, while we are loading the content...
Similar Documents
Unsolvability of the Weighted Region Shortest Path Problem I
| Content Provider | Semantic Scholar |
|---|---|
| Author | Carufel, Jean-Lou De Grimm, Carsten Maheshwari, Anil Owen, Megan Smid, Michiel |
| Copyright Year | 2012 |
| 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 ∈ S, 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). The ACMQ can compute exactly any number that can be obtained from the rationals Q by applying a finite number of operations from +, −, ×, ÷, k √ , for any integer k ≥ 2. Our proof uses Gröbner bases and Galois theory, and is based on Bajaj’s technique. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://people.scs.carleton.ca/~michiel/unsolvable.pdf |
| Alternate Webpage(s) | http://comet.lehman.cuny.edu/owen/pub/weighted_paths.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
