When Convexity meets Parallelism - A Novel Geometric Structure and Its Application in an Optimization Problem∗
Kai Jin · arXiv (Cornell University) · 2015
We consider the following geometric optimization problem: given a convex polygon $P$, compute the parallelograms in $P$ with maximal area. To solve it, we invent 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$, where $n$ represents the number of edges in $P$. We prove several nontrivial properties of $Nest(P)$, which incorporate two fundamental properties in geometry, namely, convexity and parallelism, and are of independent interests in convex and discrete geometry. We show that the structure $Nest(P)$ captures the essential nature of the maximal area parallelograms, and the original optimization problem can be reduced to answering $O(n)$ location queries on $Nest(P)$. Finally, by solving these queries efficiently, we design nearly linear time algorithm for the original problem. We emphasize that the efficiency of our algorithm is outstanding compared with several related works in computational geometry, and the techniques develop in this paper may be useful for solving other related problems. In addition, we believe that the novel structure $Nest(P)$ with its wonderful properties may find more applications in other disciplines.