## Abstract

Let P be a path between two points s and t in a polygonal subdivision T with obstacles and weighted regions. Given a relative error tolerance ε ∈(0,1), we present the first algorithm to compute a path between s and t that can be deformed to P without passing over any obstacle and the path cost is within a factor 1 + ε of the optimum. The running time is O(h ^{3}/ε^{2} kn polylog(k, n, 1/ε)), where k is the number of segments in P and h and n are the numbers of obstacles and vertices in T, respectively. The constant in the running time of our algorithm depends on some geometric parameters and the ratio of the maximum region weight to the minimum region weight.

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

Title of host publication | Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings |

Pages | 109-120 |

Number of pages | 12 |

Edition | PART 2 |

DOIs | |

State | Published - 2010 |

Event | 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of Duration: Dec 15 2010 → Dec 17 2010 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Number | PART 2 |

Volume | 6507 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 |
---|---|

Country/Territory | Korea, Republic of |

City | Jeju Island |

Period | 12/15/10 → 12/17/10 |

### Bibliographical note

Funding Information:The research of Cheng and Jin was supported by the Research Grant Council, Hong Kong, China (project no. 612107).

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)