## Abstract

Given a planar convex set C, we give sublinear approximation algorithms to determine approximations of the largest axially symmetric convex set S contained in C, and the smallest such set S′ that contains C. More precisely, for any ε>0, we find an axially symmetric convex polygon Q⊂C with area |Q|>(1-ε)|S| and we find an axially symmetric convex polygon Q′ containing C with area |Q′|<(1+ε)|S′|. We assume that C is given in a data structure that allows to answer the following two types of query in time C ^{T}: given a direction u, find an extreme point of C in direction u, and given a line ℓ, find C∩ℓ. For instance, if C is a convex n-gon and its vertices are given in a sorted array, then C ^{T}=O(logn). Then we can find Q and Q′ in time O(ε ^{-1/2}C ^{T}+ε ^{-3/2}). Using these techniques, we can also find approximations to the perimeter, area, diameter, width, smallest enclosing rectangle and smallest enclosing circle of C in time O(ε ^{-1/2}C ^{T}).

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

Pages (from-to) | 152-164 |

Number of pages | 13 |

Journal | Computational Geometry: Theory and Applications |

Volume | 33 |

Issue number | 3 |

DOIs | |

State | Published - Feb 1 2006 |

## Keywords

- Approximation
- Axial symmetry
- Shape matching

## ASJC Scopus subject areas

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