## 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 all ϵ ∈ (0, 1), and for any two points v_{s} and v_{d}, we give an algorithm that finds a path from v_{s} to v_{d} whose cost is at most (1 + ϵ) times the minimum cost. 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) |
---|---|

Title of host publication | Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 |

Publisher | Association for Computing Machinery |

Pages | 766-774 |

Number of pages | 9 |

Volume | 07-09-January-2007 |

ISBN (Electronic) | 9780898716245 |

State | Published - 2007 |

Externally published | Yes |

Event | 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States Duration: Jan 7 2007 → Jan 9 2007 |

### Other

Other | 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 |
---|---|

Country | United States |

City | New Orleans |

Period | 01/7/07 → 01/9/07 |

## ASJC Scopus subject areas

- Software
- Mathematics(all)