Monotonicity and Aggarwal et al.’s matrix searching-based O(nlogn) algorithm for the LECR problem lead to the following:
: The LR in an n-vertex vertically separated, horizontally convex polygon can be found in O(n log n) time.
: Produce a vertically separated, horizontally convex polygon for the merge step of divide-and-conquer.
LR Algorithm for a General Polygon
: If V’ and E’ are y-monotone, then M defined by our LR-measure (“area”) is totally monotone.