Before revision:  Achieving this running time requires proving several new structural properties of the MAP. Our algorithm actually computes all the locally maximal area parallelograms (LMAPs). In addition to the algorithm , we prove that the LMAPs interleave each other, thus  the number of LMAPs is bounded by O(n).
After revision:  Achieving this running time requires proving several new structural properties of the LMAPs. As an additional result , we prove that the LMAPs interleave each other, thus the number of LMAPs is bounded by O(n).