## Abstract

Given a convex polygon P with n vertices, we present algorithms to determine approximations of the largest axially symmetric convex polygon S contained in P, and the smallest such polygon S′ that contains P. More precisely, for any ε > 0, we can find an axially symmetric convex polygon Q ⊂ P with area |Q| > (1 - ε)|S| in time O(n + 1/ε^{3/2}), and we can find an axially symmetric convex polygon Q′ containing P with area |Q′| < (1 + ε)|S′| in time O(n+(1/ε^{2})log(1/ε)). If the vertices of P are given in a sorted array, we can obtain the same results in time O((1/√ε) log n+1/ε^{3/2}) and O((1/ε) log n+(1/ε^{2}) log(1/ε)) respectively.

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

Pages (from-to) | 259-267 |

Number of pages | 9 |

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

Volume | 3106 |

State | Published - 2004 |

Externally published | Yes |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)