An algorithm to find maximum area polygons circumscribed about a convex polygon
| Autor: | Susanna Dann, Zsolt Lángi, Géza Tóth, Markus Ausserhofer |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Conjecture
Applied Mathematics Regular polygon Metric Geometry (math.MG) Computer Science::Computational Geometry Convex polygon Vertex (geometry) Mathematics - Metric Geometry 52A38 52B60 68W01 62H12 FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Mathematics::Metric Geometry Combinatorics (math.CO) Special case Algorithm Mathematics |
| DOI: | 10.48550/arxiv.1706.08152 |
| Popis: | A convex polygon Q is circumscribed about a convex polygon P if every vertex of P lies on at least one side of Q. We present an algorithm for finding a maximum area convex polygon circumscribed about any given convex n-gon in O(n^3) time. As an application, we disprove a conjecture of Farris. Moreover, for the special case of regular n-gons we find an explicit solution. Comment: 11 pages, 7 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|