## Abstract

We introduce a technique for computing approximate solutions to optimization problems, if X is the set of feasible solutions, the standard goal of approximation algorithms is to compute x ∈ X that is an ε-approximate solution in the following sense: d(x) ≤ (1 + ε)d(x*) where x* ∈ X is an optimal solution, d: X → ℝ≥_{≥0} is the optimization function to be minimized, and ε > 0 is an input parameter. Our approach is to first devise algorithms that compute pseudo ε-approximate solutions satisfying the bound d(x) ≤ d(x*_{R}) +εR where R > 0 is a new input parameter. Here x_{R}* denotes an optimal solution in the space X_{R} of R-constrained feasible solutions. The parameterization provides a stratification of X in the sense that (1) X_{R} ⊆ X_{R′}, for R < R′ and (2) X_{R} = X for R sufficiently large. We first describe a highly efficient scheme for converting a pseudo ε-approximation algorithm into a true ε-approximation algorithm. This scheme is useful because pseudo approximation algorithms seem to be easier to construct than ε-approximation algorithms. We then apply our technique to two problems in robotics: (A) Euclidean Shortest Path (3ESP), namely the shortest path for a point robot amidst polyhedral obstacles in 3D, and (B) d_{1}-optimal motion for a rod moving amidst polygonal obstacles in 2D. Previously, no true ε-approximation algorithm for (B) was known. For (A), our new solution is not only simpler than two previous solutions but also has a lower complexity (in the algebraic model) measured in terms of the input precision. Note that (A) and (B) are the simplest NP-hard motion planning problems in 3-D and 2-D respectively.

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

Pages | 170-178 |

Number of pages | 9 |

DOIs | |

State | Published - 2002 |

Event | Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) - Barcelona, Spain Duration: Jun 5 2002 → Jun 7 2002 |

### Other

Other | Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) |
---|---|

Country | Spain |

City | Barcelona |

Period | 6/5/02 → 6/7/02 |

## Keywords

- Approximation algorithms
- Binary search
- Euclidean shortest path
- NP-hard problem
- Optimal motion planning
- Pseudo approximation
- Robot motion planning
- d-optimal motion

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics