= Monotone boundary representation of a grid order ideal
{title2=$B=\{(x,y):0\leq x<r_y\},\quad r_0\geq r_1\geq\cdots$}
For an <order ideal> in a finite rectangular grid with coordinatewise <partial order>, occupied cells in each row form a left prefix. Their lengths form a nonincreasing <sequence> $r_y$. Conversely, any nonincreasing sequence of valid row lengths specifies exactly one such <order ideal>, giving an <abstraction function> with no redundant per-cell information.
Removing all occupied cells with $x\geq a$ and $y\geq b$ replaces $r_y$ by $\min(r_y,a)$ for $y\geq b$ and leaves earlier rows unchanged. The new lengths remain nonincreasing: affected rows preserve their mutual order, and the first affected row only decreases. For a legal removal, the boundary immediately below it was already at least $a$. A cached <sum> of row lengths can be updated by subtracting the decreases. This yields constant-time membership and count queries, linear storage, and an update linear in the number of affected rows.
Back to article page
