A technique for solving the polygon inclusion problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2017
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911846549684224 |
|---|---|
| author | Jin, Kai Zhu, Taikun Luo, Ruixi |
| author_facet | Jin, Kai Zhu, Taikun Luo, Ruixi |
| contents | We propose a technique called Rotate-and-Kill for solving the polygon inclusion and circumscribing problems. By applying this technique, we obtain $O(n)$ time algorithms for computing (1) the maximum area triangle in a given $n$-sided convex polygon $P$, (2) the minimum area triangle enclosing $P$, (3) the minimum area triangle enclosing $P$ touching edge-to-edge, i.e. the minimum area triangle that is the intersection of three half-planes out of the $n$ half-planes defining $P$, and (4) the minimum perimeter triangle enclosing $P$ touching edge-to-edge.
Our algorithm for computing the maximum area triangle is simpler than the alternatives given in [Chandran and Mount, IJCGA'92] and [Kallus, arXiv'17]. Our algorithms for computing the minimum area or perimeter triangle enclosing $P$ touching edge-to-edge improve the $O(n\log n)$ or $O(n\log^2n)$ time algorithms given in [Boyce \emph{et al.}, STOC'82], [Aggarwal \emph{et al.}, Algorithmica'87], [Aggarwal and J. Park., FOCS'88], [Aggarwal \emph{et al.}, DCG'94], and [Schieber, SODA'95]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1707_04071 |
| institution | arXiv |
| publishDate | 2017 |
| record_format | arxiv |
| spellingShingle | A technique for solving the polygon inclusion problems Jin, Kai Zhu, Taikun Luo, Ruixi Computational Geometry I.3.5 We propose a technique called Rotate-and-Kill for solving the polygon inclusion and circumscribing problems. By applying this technique, we obtain $O(n)$ time algorithms for computing (1) the maximum area triangle in a given $n$-sided convex polygon $P$, (2) the minimum area triangle enclosing $P$, (3) the minimum area triangle enclosing $P$ touching edge-to-edge, i.e. the minimum area triangle that is the intersection of three half-planes out of the $n$ half-planes defining $P$, and (4) the minimum perimeter triangle enclosing $P$ touching edge-to-edge. Our algorithm for computing the maximum area triangle is simpler than the alternatives given in [Chandran and Mount, IJCGA'92] and [Kallus, arXiv'17]. Our algorithms for computing the minimum area or perimeter triangle enclosing $P$ touching edge-to-edge improve the $O(n\log n)$ or $O(n\log^2n)$ time algorithms given in [Boyce \emph{et al.}, STOC'82], [Aggarwal \emph{et al.}, Algorithmica'87], [Aggarwal and J. Park., FOCS'88], [Aggarwal \emph{et al.}, DCG'94], and [Schieber, SODA'95]. |
| title | A technique for solving the polygon inclusion problems |
| topic | Computational Geometry I.3.5 |
| url | https://arxiv.org/abs/1707.04071 |