Original title: Linear-time Algorithms for Largest Inscribed Quadrilateral
Authors: Keikha, Vahideh
Document type: Research reports
Year: 2020
Language: eng
Series: Technical Report, volume: V-1283
Abstract: 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.
Keywords: extreme area k-gon; Maximum-area quadrilateral
Rights: This work is protected under the Copyright Act No. 121/2000 Coll.

Institution: Institute of Computer Science AS ČR (web)
Original record: http://hdl.handle.net/11104/0314384

Permalink: http://www.nusl.cz/ntk/nusl-432419


The record appears in these collections:
Research > Institutes ASCR > Institute of Computer Science
Reports > Research reports