Group:Theory Lunch
Title: Quadratic Algorithm for Finding Maximum Area Parallelogram inside a Convex Polyg
Speaker: Kai Jin, Guang Yang University
Time: 2010-11-25 12:00-2010-11-25 13:30
Venue: FIT 1-222


Title: Quadratic Algorithm for Finding Maximum Area Parallelogram inside a Convex Polygon

Abstract: It is well known that finding Maximum-Area-Parallelogram (MAP) inside a convex polygon is equivalent to finding MAP inscribed on it. So it's not hard to solve it in biquadratic time. By showing a unique hyperbola-structure of which the inscribed parallelogram keeps an invariant area, we detach two enumerative variables and turn a two-dimensional search into two one-dimensional search respectively. We managed to improve the algorithm to cubic time. Furthermore, by applying the rotating-technique introduced in \cite{toussaint1983solving} on the movement of the boundary of the center point we finally present an algorithm in quadratic time.

Since parallelogram is the most simple central symmetric polygon, it's feasible to approximate central symmetric curves by parallelograms. We proved that the area of MAP in a convex central symmetrical figure $F$ is always larger than $2/\pi\approx 0.6366$ times the area of $F$. Moreover this ratio is tight if and only if $F$ is an ellipse.

Title: Generalizing Reingold's s-t connectivity in LOGSPACE result.

Abstract: I will show some attempts on extending Reingold's technique for directed graphs and general RL problems, and partial results follows.

In 2005, Reingold proved that undirected s-t connectivity in deterministic logspace L, by reducing an arbitrary undirected graph to an expander graph. It becomes interesting that how far Reingold's technique goes on to derandomize general problems in RL, as well as how to reduce directed graphs to expanders.

I would like to introduce a kind of generalization to show that s-t connectivity and path searching restricted in biregular directed graph(more than undirected graph) can be solved in L. The path searching algorithm also implies a pseudorandom generator from consistently labelled biregular graphs.

Short Bio: