## Abstract

Our goal is to find an approximate shortest path for a point robot moving in a planar subdivision with n vertices. Let ρ ≤ 1 be a real number. Distances in each face of this subdivision are measured by a convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius 1/ρ. Different convex distance functions may be used for different faces, and obstacles are allowed. These convex distance functions may be asymmetric. For any ε ε{lunate} (0, 1) and for any two points v_{s} and v_{s} we give an algorithm that finds a path from v_{s} to v_{d} whose cost is at most (1+ε) times the optimal. Our algorithm runs in O(ρ^{2} log ρ/ε^{2} n^{3} log (ρn/ε)) time. This bound does not depend on any other parameters; in particular it does not depend on the minimum angle in the subdivision. We give applications to two special cases that have been considered before: the weighted region problem and motion planning in the presence of uniform flows. For the weighted region problem with weights in [1, ρ] ∪ {∞}, the time bound of our algorithm improves to O(ρ logρ/ε n^{3} log (ρn/ε)).

Original language | English (US) |
---|---|

Pages (from-to) | 802-824 |

Number of pages | 23 |

Journal | SIAM Journal on Computing |

Volume | 38 |

Issue number | 3 |

DOIs | |

State | Published - Nov 7 2008 |

## Keywords

- Approximation algorithm
- Computational geometry
- Convex distance function
- Shortest path
- Weighted region

## ASJC Scopus subject areas

- Computer Science(all)
- Mathematics(all)