Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2017
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/1707.04071 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
Sommario:
- 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].