An algorithm to find maximum area polygons circumscribed about a convex polygon
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2017
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917619327565824 |
|---|---|
| author | Ausserhofer, Markus Dann, Susanna Lángi, Zsolt Tóth, Géza |
| author_facet | Ausserhofer, Markus Dann, Susanna Lángi, Zsolt Tóth, Géza |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1706_08152 |
| institution | arXiv |
| publishDate | 2017 |
| record_format | arxiv |
| spellingShingle | An algorithm to find maximum area polygons circumscribed about a convex polygon Ausserhofer, Markus Dann, Susanna Lángi, Zsolt Tóth, Géza Metric Geometry Combinatorics 52A38, 52B60, 68W01, 62H12 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. |
| title | An algorithm to find maximum area polygons circumscribed about a convex polygon |
| topic | Metric Geometry Combinatorics 52A38, 52B60, 68W01, 62H12 |
| url | https://arxiv.org/abs/1706.08152 |