## Abstract

Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any ε > 0, we compute a rigid motion such that the area of overlap is at least 1 -ε times the maximum possible overlap. Our algorithm uses O(l/ε) extreme point and line intersection queries on P and Q, plus O((1/ε^{2})log(1/ε)) running time. If only translations are allowed, the extra running time reduces to O((1/ε) log(1/ε)). If P and Q are convex polygons with n vertices in total, the total running time is O((1/ε) logn+(1/ε^{2}) log(1/ε)) for rigid motions and O((1/ε) log n + (1/ε) log(1/ε)) for translations.

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

Pages | 356-363 |

Number of pages | 8 |

DOIs | |

State | Published - 2005 |

Event | 21st Annual Symposium on Computational Geometry, SCG'05 - Pisa, Italy Duration: Jun 6 2005 → Jun 8 2005 |

### Other

Other | 21st Annual Symposium on Computational Geometry, SCG'05 |
---|---|

Country/Territory | Italy |

City | Pisa |

Period | 06/6/05 → 06/8/05 |

## Keywords

- Approximation algorithm
- Convex shape
- Pattern matching
- Sublinear algorithm

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics