Group:Lunch Meeting
Title: Testing Boolean Function Monotonicity, Finding the Maximum Area Parallelogram in
Speaker: Chenggang Wu, Kai Jin
Time: 2011-10-20 12:00-2011-10-20 14:00
Venue: FIT 1-222

Abstract:

Speaker: Chenggang Wu
====================
Title: Testing Boolean Function Monotonicity

Abstract:

 

This talk is divided into two parts. In the first part I will survey previous results in testing function monotonicity. In the second part I will introduce some partial results for Boolean function monotonicity, both for upper bound and lower bound.

 

--------------------------------------
Speaker: Kai Jin
================

Title: Finding the Maximum Area Parallelogram in a convex polygon

Abstract:

 

We consider the problem of finding the maximum area parallelogram (MAP) in a convex polygon. Last semester I've showed the MAP must be "anchored". And there are two types of anchored parallelogram in a convex polygon, called opposite-free type and adjacent-anchored type. Thus we divide this problem into two sub cases. For the case the MAP is of opposite-free type, we gave an O(n^2) time algorithm; However, for the other case we only gave a trivial O(n^2logn) time algorithm. We claimed we believed this could also be solved in O(n^2) since it seems "easier than the other case". We now have a solution to this case in O(n^2) time.

 

Recently (under Haitao Wang's suggestion) I tried to attack this problem further and reduce the run-time to O(nlogn). We came up with an algorithm that almost works in O(nlog n) except for a very special case. Actually, the major part of the preivous O(n^2) time algorithm also did not handle the speical case, and there is a trivial O(n^2) time algorithm for this special case. This trival algorithm looks very different from the major one, and we do not know how to improve it to O(nlogn) time.

 

Thus, currently we aim at improving it also to O(nlogn) time. We need your help!