Maximal Parallelograms in Convex Polygons - A Novel Geometric Structure
Kai Jin · arXiv (Cornell University) · 2015
We propose a novel geometric structure, called $Nest(P)$, which is induced by $P$ and is an arrangement of $\Theta(n^2)$ segments, each of which is parallel to an edge of $P$. This structure admits several interesting and nontrivial properties, which follow from two fundamental properties in geometry, namely, convexity and parallelism. Moreover, we give a perfect application of this structure in the following geometric optimization problem: Given a convex polygon $P$ with $n$ edges, compute the parallelograms in $P$ with maximal area. We design an $O(n\log^2n)$ time algorithm for computing all these parallelograms, which improves over a previous known quadratic time algorithm. Concretely, we show that $Nest(P)$ captures the essential nature of the maximal area parallelograms, and the optimization problem we considered reduces to answering $O(n)$ location queries on $Nest(P)$. Moreover, using a few nontrivial algorithmic tricks, we answer each of these queries in $O(\log^2n)$ time. This should avoid an explicit construction of $Nest(P)$, which takes $\Omega(n^2)$ time.