## 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(1/) 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 that are given in an array or balanced tree, the total running time is O((1/)logn+(1/^{2})log(1/)) for rigid motions and O((1/)logn+(1/)log(1/)) for translations.

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

Pages (from-to) | 3-15 |

Number of pages | 13 |

Journal | Computational Geometry: Theory and Applications |

Volume | 37 |

Issue number | 1 SPEC. ISS. |

DOIs | |

State | Published - Jan 1 2007 |

## Keywords

- Approximation algorithm
- Convex shape
- Geometric pattern matching
- Sublinear algorithm

## ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics