Název: Linear-time Algorithms for Largest Inscribed Quadrilateral
Autoři: Keikha, Vahideh
Typ dokumentu: Výzkumné zprávy
Rok: 2020
Jazyk: eng
Edice: Technical Report, svazek: V-1283
Abstrakt: Let P be a convex polygon of n vertices. We present a linear-time algorithm for the problem of computing the largest-area inscribed quadrilateral of P. We also design the parallel version of the algorithm with O(log n) time and O(n) work in CREW PRAM model, which is quite work optimal. Our parallel algorithm also computes all the antipodal pairs of a convex polygon with O(log n) time and O(log2n+s) work, where s is the number of antipodal pairs, that we hope is of independent interest. We also discuss several approximation algorithms (both constant factor and approximation scheme) for computing the largest-inscribed k-gons for constant values of k, in both area and perimeter measures.
Klíčová slova: extreme area k-gon; Maximum-area quadrilateral
Práva: Dílo je chráněno podle autorského zákona č. 121/2000 Sb.

Instituce: Ústav informatiky AV ČR (web)
Původní záznam: http://hdl.handle.net/11104/0314384

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-432419


Záznam je zařazen do těchto sbírek:
Věda a výzkum > AV ČR > Ústav informatiky
Zprávy > Výzkumné zprávy