Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds

A poset is a lattice if every pair of elements has a unique least upper bound (join) and a unique greatest lower bound (meet). For a locally finite, totally ordered set $O$, Boldi and Vigna [8] show that the antichain completion ${ℰ}_O$ forms a complete lattice. This structure, known as the Clarke–Cormack–Burkowski lattice, is named after the work of Clarke, Cormack, and Burkowski on minimal-interval semantics in information retrieval [12].

Let $O$ be a locally finite, totally ordered set, so ${ℰ}_O$ is a CCB lattice. Each $𝒜\in {ℰ}_O$ is a family of intervals of $O$ in which no interval properly contains another. For a family $ℱ$ of intervals, let ${\min }_{\subseteq }(ℱ)≔\{I\in ℱ\mid \mathrm{\nexists }J\in ℱ\text{ with }J⊊I\}$ be the set of inclusion-minimal intervals in $ℱ$. The join and meet of $𝒜,ℬ\in {ℰ}_O$ are defined, respectively, as

See Figure 3 for an illustration of the partial order, meet, and join of two antichains.

Boldi and Vigna also show that ${ℰ}_O$ is a completely distributive lattice: arbitrary meets distribute over arbitrary joins in this lattice. In particular, for any family ${({𝒜}_i)}_{i\in I}\subseteq {ℰ}_O$ and any $ℬ\in {ℰ}_O$, we have $\left({\bigvee }_{i\in I}{𝒜}_i\right)\wedge ℬ={\bigvee }_{i\in I}\left({𝒜}_i\wedge ℬ\right)$.

For a vertical cut $c$, the sets ${\min }_{\subseteq }({ℐ}_c(P_L))$ and ${\min }_{\subseteq }({ℐ}_c(P_R))$ are antichains of intervals, since no interval in each set properly contains another. By Observation 3, these antichains suffice to decide whether the strips incident to $c$ can be merged. In fact, the equality $\text{opt}(P)=\text{opt}(P_L)+\text{opt}(P_R)-1$ holds if and only if the meet ${\min }_{\subseteq }({ℐ}_c(P_L))\wedge {\min }_{\subseteq }({ℐ}_c(P_R))$ contains an interval of length at most $1$. Thus, in our dynamic program, we only need to maintain, for each subpolygon $Q$ with vertical edge $c$, the antichain $\mathrm{𝖠𝗇𝗍}(Q,c)≔{\min }_{\subseteq }\left({ℐ}_c(Q)\right)$. In other words, $\mathrm{𝖠𝗇𝗍}(Q,c)$ is the set of inclusion-minimal $x$-intervals of strips incident to $c$ across all optimal strip partitions of $Q$.

At first glance, these antichains appear to be families of intervals of $ℝ$, which is not locally finite. However, as we will show, once we fix some $\epsilon \ge 0$, every interval that arises in our algorithm has endpoints of the form $x(p)+m$ or $x(p)+m\pm \epsilon$, where $p$ is a vertex of $P$ and $m\in \mathbb{Z}$. Thus all endpoints lie in

a locally finite, totally ordered set. Consequently, every antichain maintained by our dynamic program lies in the CCB lattice ${ℰ}_{\mathbb{Z}(P,\epsilon )}$. This lattice is completely distributive.

We transform the dual graph $G$ of $V$ into a rooted binary tree $\tilde{G}$ by locally refining each star centered at a trapezoid. Let $\mathrm{\Delta }\in V$ be a trapezoid in $V$ with subproblem structure $(Q_{\mathrm{\Delta }},e_{\mathrm{\Delta }},\overrightarrow{\eta }(e_{\mathrm{\Delta }}))$, and assume without loss of generality that $\overrightarrow{\eta }(e_{\mathrm{\Delta }})=\mathrm{𝗋𝗂𝗀𝗁𝗍}$. Suppose $\mathrm{\Delta }$ has $p$ children incident to its left side and $q$ children on its right. Let ${({\mathrm{\Delta }}_i^L,e_i^L,\overrightarrow{\eta }(e_i^L))}_{i=1}^p$ (resp. ${({\mathrm{\Delta }}_j^R,e_j^R,\overrightarrow{\eta }(e_j^R))}_{j=1}^q$) be the subproblem structures associated with its left (resp. right) children. By construction, each $\overrightarrow{\eta }(e_i^L)=\mathrm{𝗋𝗂𝗀𝗁𝗍}$ and each $\overrightarrow{\eta }(e_i^R)=\mathrm{𝗅𝖾𝖿𝗍}$.

First, we construct a binary tree $T_L$ whose leaves are the left children of $\mathrm{\Delta }$. If $p=0$, we do not create $T_L$; if $p=1$, then $T_L$ is a single node ${\mathrm{\Delta }}_1^L$. For $p\ge 2$, we create $(p-1)$ new internal nodes $u_2,\mathrm{\dots },u_p$ and set each $u_i$ as the parent of ${\mathrm{\Delta }}_i^L$ and $u_{i-1}$ for each $i=2,\mathrm{\dots },p$, with $u_1:={\mathrm{\Delta }}_1^L$. Symmetrically, we construct a binary tree $T_R$ for the right children of $\mathrm{\Delta }$.

Next, we remove all edges from $\mathrm{\Delta }$ to its children in $G$. If $T_L$ exists (i.e., $p\ge 1$), we attach the root of $T_L$ as the sole child of $\mathrm{\Delta }$. If $T_R$ exists, let $w$ be a new internal node whose children are the root of $T_R$ and $\mathrm{\Delta }$; otherwise, let $w:=\mathrm{\Delta }$. If $\mathrm{\Delta }$ has a parent $z$ in $G$, we replace the edge between $z$ and $\mathrm{\Delta }$ by an edge between $z$ and $w$. The case $\overrightarrow{\eta }(e_{\mathrm{\Delta }})=\mathrm{𝗅𝖾𝖿𝗍}$ is handled symmetrically. See Figure 5 for an illustration.

Processing all trapezoids in postorder replaces every star subgraph in $G$ with a binary tree. At each step, only the adjacency between $\mathrm{\Delta }$ and its children changes; the subtrees rooted at those children remain intact. This refinement adds only $O(n)$ new internal nodes in total, and $\tilde{G}$ can be constructed in $O(n)$ time. We refer to the original nodes of $G$ as trapezoid nodes and the new internal nodes as bridge nodes. By construction, every trapezoid node in $\tilde{G}$ has at most one child, and every bridge node has exactly two children.

We lift the subproblem structures defined for nodes of $G$ to the nodes of the refined tree $\tilde{G}$. For each non-root node $u$, we associate a triple $(Q_u,e_u,\overrightarrow{\eta }(e_u))$, where $Q_u$ is a weakly simple subpolygon of $P$, $e_u$ is a vertical edge on $\partial Q_u$, and $\overrightarrow{\eta }(e_u)\in \{\mathrm{𝗅𝖾𝖿𝗍},\mathrm{𝗋𝗂𝗀𝗁𝗍}\}$ is the outward normal direction of $e_u$ with respect to $Q_u$. If $u$ is a trapezoid node corresponding to a trapezoid $\mathrm{\Delta }\in V$, we inherit its subproblem structure by setting $(Q_u,e_u,\overrightarrow{\eta }(e_u)):=(Q_{\mathrm{\Delta }},e_{\mathrm{\Delta }},\overrightarrow{\eta }(e_{\mathrm{\Delta }}))$.

Suppose that $u$ is a bridge node with children $v$ and $w$. Assume that $(Q_v,e_v,\overrightarrow{\eta }(e_v))$ and $(Q_w,e_w,\overrightarrow{\eta }(e_w))$ are already defined. Let $s$ be the minimal vertical segment spanning both $e_v$ and $e_w$, and define $Q_u:=Q_v\cup s\cup Q_w$. If $\overrightarrow{\eta }(e_v)=\overrightarrow{\eta }(e_w)$, then $u$ is a same-side bridge. We set $e_u:=s$ and $\overrightarrow{\eta }(e_u):=\overrightarrow{\eta }(e_v)$. In this case, $Q_u$ has boundary edges that touch each other without crossing, so $Q_u$ is only weakly simple.

If $\overrightarrow{\eta }(e_v)\ne \overrightarrow{\eta }(e_w)$, then $u$ is a cross-side bridge. In this case, $Q_u$ is always simple and one of $e_v,e_w$ properly contains the other. If $e_v⊊e_w$, we set $e_u:=e_w\setminus e_v$ and $\overrightarrow{\eta }(e_u):=\overrightarrow{\eta }(e_w)$; otherwise, $e_u:=e_v\setminus e_w$ and $\overrightarrow{\eta }(e_u):=\overrightarrow{\eta }(e_v)$. Figure 6(a-b) illustrates the subproblem structures at bridge nodes.

For the root node $\rho$ of $\tilde{G}$, which corresponds to the leaf $\overline{\mathrm{\Delta }}$ of $G$, the region $Q_{\rho }=P$ has no vertical interface on its boundary. Then, we cannot directly define a subproblem structure for $\rho$. Let $e$ be the vertical side of $\overline{\mathrm{\Delta }}$ that is not incident to any other trapezoid of $V$. Note that $e$ may be a single vertex if $\overline{\mathrm{\Delta }}$ is a triangle. In this degenerate case, we conceptually replace $e$ with a very short vertical segment, obtained by extending it slightly in both vertical directions. This extension preserves the $x$-interval of $\overline{\mathrm{\Delta }}$, keeps $P$ simple, and does not affect any strip partition of $P$. We set $e_{\rho }:=e$ and define $\overrightarrow{\eta }(e_{\rho })$ as $\mathrm{𝗅𝖾𝖿𝗍}$ if $e$ lies on the left side of $\overline{\mathrm{\Delta }}$, or $\mathrm{𝗋𝗂𝗀𝗁𝗍}$ if $e$ lies on the right side. This yields the subproblem structure $(Q_{\rho },e_{\rho },\overrightarrow{\eta }(e_{\rho }))$ for the root node $\rho$. See Figure 6(c).

By Lemma 4, every node $u$ of $\tilde{G}$ has an associated subproblem structure $(Q_u,e_u,\overrightarrow{\eta }(e_u))$. If $u$ is a trapezoid node or a cross-side bridge node, then $Q_u$ is simple. If $u$ is a same-side bridge node, however, $Q_u$ is only weakly simple. To handle all subproblems in the simple polygon setting, we convert $Q_u$ into a simple polygon by attaching a thin triangular cap along $e_u$ on the outside of $Q_u$.

Let $q_u$ be any point on the edge $e_u$, excluding its endpoints. For sufficiently small $\epsilon >0$, let $q_u(\epsilon )$ be the point obtained by shifting $q_u$ by $\epsilon$ units in the direction of $\overrightarrow{\eta }(e_u)$. Let $T_u(\epsilon )$ be the triangle with base $e_u$ and apex $q_u(\epsilon )$.

Let ${(x_i)}_{i=1}^n$ be the $x$-coordinates of the vertices of $P$, and let $\mathbb{Z}(P,0):=\{x_i+m\mid i\in [n],m\in \mathbb{Z}\}$. Let $\delta >0$ be the minimum positive distance between two distinct points of $\mathbb{Z}(P,0)$. From Lemma 5, for each node $u$, there exists ${\epsilon }_0(u)>0$ such that $Q_u\cup T_u(\epsilon )$ is simple for all . Choose a particular $\epsilon >0$ satisfying $\epsilon \le {\min }_u{\epsilon }_0(u)$ and . Note that $\delta$ and $\epsilon$ are not computed explicitly; we only fix such values conceptually.

Now we define the capped subpolygon $Q_u^{\epsilon }:=Q_u\cup T_u(\epsilon )$, which is a simple polygon. Figure 6 illustrates how the cap $T_u(\epsilon )$ attaches to $e_u$ for each node type. Let ${\text{opt}}^{\epsilon }(Q_u)$ denote the minimum number of strips in an optimal strip partition of $Q_u^{\epsilon }$. Among all optimal strip partitions of $Q_u^{\epsilon }$, let ${𝒮}^{\epsilon }(Q_u,e_u)$ be the set of strips incident to the apex $q_u(\epsilon )$, and define ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_u,e_u):={\min }_{\subseteq }\{I_x(S)\mid S\in {𝒮}^{\epsilon }(Q_u,e_u)\}$, where $I_x(S)$ is the interval obtained by projecting $S$ onto the $x$-axis. Then ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_u,e_u)$ is an antichain of intervals. By definition, every interval in ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_u,e_u)$ is realized as the $x$-projection of a strip incident to $q_u(\epsilon )$ in some optimal partition of $Q_u^{\epsilon }$. Although the family ${𝒮}^{\epsilon }(Q_u,e_u)$ may be infinite, Algorithm 1 and Lemma 9 together imply that ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_u,e_u)$ is finite. We define the dynamic-programming subproblem ${\text{OSP}}^{\epsilon }(Q_u,e_u)$ to be the task of computing both ${\text{opt}}^{\epsilon }(Q_u)$ and ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_u,e_u)$. The pair $({\text{opt}}^{\epsilon }(Q_u),{\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_u,e_u))$ is called the DP state at node $u$; its first entry is the value component, and its second entry is the antichain component.

Let $u$ be a trapezoid node corresponding to a trapezoid $\mathrm{\Delta }$. If $u$ has a child $v$ in $\tilde{G}$, the DP state $({\text{opt}}^{\epsilon }(Q_v),{\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_v,e_v))$ has already been computed. If $u$ is a leaf, we introduce a virtual child $v$ by taking $e_v$ to be the vertical side of $\mathrm{\Delta }$ opposite to $e_u$, letting $Q_v$ be the degenerate trapezoid consisting of $e_v$, and setting $\overrightarrow{\eta }(e_v)=\overrightarrow{\eta }(e_u)$; then ${\text{opt}}^{\epsilon }(Q_v)=1$ and ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_v,e_v)$ consists of a single interval of length $\epsilon$ adjacent to $x(e_v)$.

The update at a trapezoid node proceeds as follows. Let $[a,b]$ be the $x$-interval of $\mathrm{\Delta }$, where $a=x(e_v)$ and $b=x(e_u)$. For each strip $S\in {𝒮}^{\epsilon }(Q_v,e_v)$, we remove the old cap $T_v(\epsilon )$, insert $\mathrm{\Delta }$ into the polygon, and then attach the new cap $T_u(\epsilon )$ along $e_u$. If $[\mathrm{\ell },r]$ is the $x$-interval of $S$, then the extended strip has $x$-interval $[\min \{\mathrm{\ell },a\},\max \{r,b+\epsilon \}]$, which is exactly the interval obtained by taking the meet of $\{[\mathrm{\ell },r]\}$ with $\{[a,b+\epsilon ]\}$. Thus, the inclusion-minimal $x$-intervals of all feasible extensions are exactly ${\mathrm{Filter}}_1\left({\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_v,e_v)\wedge \{[a,b+\epsilon ]\}\right)$.

If at least one extended strip survives, then we do not introduce any new cut at $u$. If none survive, then no strip can be extended through $\mathrm{\Delta }$ without violating the unit-width constraint. Let $[\mathrm{\ell },r]$ be the $x$-interval of the rightmost strip in ${𝒮}^{\epsilon }(Q_v,e_v)$. If no extended strip survives, we insert a series of vertical cuts in $\mathrm{\Delta }\cup T_u(\epsilon )$ at $x$-coordinates $\mathrm{\ell }+1,\mathrm{\ell }+2,\mathrm{\dots }$, decomposing the extended region into unit-width strips (with the last piece possibly shorter than $1$). We then increase ${\text{opt}}^{\epsilon }(Q_u)$ by the number of new strips, and define ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_u,e_u)$ to consist of the single $x$-interval of the rightmost suffix strip incident to $q_u(\epsilon )$.

Let $u$ be a bridge node of $\tilde{G}$ with children $v$ and $w$. At a bridge node, we consider pairs of strips $S_v\in {𝒮}^{\epsilon }(Q_v,e_v)$ and $S_w\in {𝒮}^{\epsilon }(Q_w,e_w)$, and ask whether they can be combined into a single strip incident to $q_u(\epsilon )$. By the choice of $\epsilon$, the $x$-interval of each of $S_v$ and $S_w$ already contains $[x(e_u)-\epsilon ,x(e_u)+\epsilon ]$. Hence, replacing the child caps $T_v(\epsilon ),T_w(\epsilon )$ with the cap $T_u(\epsilon )$ does not change either $x$-interval.

For a same-side bridge, this combination is obtained by removing the caps $T_v(\epsilon )$ and $T_w(\epsilon )$, gluing the two strips along $e_u$, and attaching the cap $T_u(\epsilon )$. For a cross-side bridge, we remove the two caps, take the union of the resulting strips, and attach $T_u(\epsilon )$ along $e_u$. In either case, if $[\mathrm{\ell },r]$ and $[{\mathrm{\ell }}^{\prime },r^{\prime }]$ are the $x$-intervals of $S_v$ and $S_w$, respectively, then the combined region has $x$-interval $[\min \{\mathrm{\ell },{\mathrm{\ell }}^{\prime }\},\max \{r,r^{\prime }\}]$. Thus, the inclusion-minimal $x$-intervals of all feasible combinations are exactly ${\mathrm{Filter}}_1\left({\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_v,e_v)\wedge {\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_w,e_w)\right)$.

If at least one pair of strips yields a feasible strip, then no additional cut is introduced at $u$, and the feasible combined strips form ${𝒮}^{\epsilon }(Q_u,e_u)$. Otherwise, we insert a vertical cut near $e_u$ so that strips from the two child subproblems cannot be combined across $u$. The strips from $Q_v$ and $Q_w$ are then extended separately to $q_u(\epsilon )$. Hence, ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_u,e_u)={\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_v,e_v)\vee {\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_w,e_w)$.

We now describe how new cuts are placed when strips cannot be merged or extended at a node $u$ without violating the unit-width constraint.

If $u$ is a trapezoid node, no strip extends through its trapezoid $\mathrm{\Delta }$, so we place vertical cuts in $\mathrm{\Delta }\cup T_u(\epsilon )$. They start at $x=\mathrm{\ell }+1$, where $[\mathrm{\ell },r]$ is the interval with the maximum left endpoint in ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_v,e_v)$, and continue at unit distance. See Figure 7(a).

Now suppose that $u$ is a bridge node with children $v$ and $w$. If some strip in ${𝒮}^{\epsilon }(Q_v,e_v)$ can merge with one in ${𝒮}^{\epsilon }(Q_w,e_w)$ into a unit-width strip, no new cut is added at $u$. Otherwise, we place a single vertical cut near $e_u$ to prevent any strip from $Q_v$ from merging with a strip from $Q_w$, so that all strips are extended to $q_u(\epsilon )$ separately. See Figure 7(b–c).

The position of this cut depends on the bridge type and on the child from which each $x$-interval in ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_u,e_u)$ originates. For a same-side bridge, the cut is placed along $e_w$ if the interval comes from ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_v,e_v)$ and along $e_v$ if it comes from ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_w,e_w)$. For a cross-side bridge, either $e_v⊊e_w$ or $e_w⊊e_v$. Assume $e_v⊊e_w$. If the interval comes from ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_w,e_w)$, the cut is placed along $e_v$. Otherwise it is placed inside $Q_w$ at $x$-distance $\epsilon$ from $e_u$, blocking any strip from $Q_w^{\epsilon }$ from reaching $q_u(\epsilon )$; see Figure 7(c). The case $e_w⊊e_v$ is symmetric. Note that inserting these cuts at bridge nodes does not increase the $x$-interval of any strip from $Q_v^{\epsilon }$ or $Q_w^{\epsilon }$; we prove this in the proof of Lemma 6.

Every interval appearing in an antichain ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_u,e_u)$ has endpoints of the form $x(p)+m$ or $x(p)+m\pm \epsilon$, where $p$ is a vertex of $P$ and $m\in \mathbb{Z}$. Thus all endpoints lie in the locally finite, totally ordered set $\mathbb{Z}(P,\epsilon )$, and each antichain maintained by our DP is an element of the Clarke–Cormack–Burkowski lattice ${ℰ}_{\mathbb{Z}(P,\epsilon )}$. The update rules are written using meet ($\wedge$) and join ($\vee$) in this lattice, and the outputs of these operations remain in ${ℰ}_{\mathbb{Z}(P,\epsilon )}$.

Since $\epsilon >0$ is chosen sufficiently small, the values $\text{opt}(Q_u)$ and ${\text{opt}}^{\epsilon }(Q_u)$ differ by at most one. This difference occurs only when, in every optimal partition of $Q_u^{\epsilon }$, the only strip incident to $q_u(\epsilon )$ is the cap $T_u(\epsilon )$; in this case we have ${\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_u,e_u)=\{[x(e_u),x(e_u)+\epsilon ]\}$.

In the DP state, we store an endpoint of the form $x(p)+m$ or $x(p)+m\pm \epsilon$ as the value $x(p)+m$ together with a single bit indicating whether the $\epsilon$–offset is present. Since $\epsilon >0$ is chosen sufficiently small, all order and width tests used by the algorithm can be decided from the base values and the flags. For example, if $a,b\in \mathbb{Z}(P,0)$ and $m\in \mathbb{Z}$, then

By Lemma 6, Algorithm 1 correctly computes $({\text{opt}}^{\epsilon }(Q_{\rho }),{\mathrm{𝖠𝗇𝗍}}^{\epsilon }(Q_{\rho },e_{\rho }))$ at the root $\rho$ of $\tilde{G}$, where $Q_{\rho }=P$. By the discussion above on the relation between ${\text{opt}}^{\epsilon }(Q_u)$ and $\text{opt}(Q_u)$, we obtain $\text{opt}(P)$ from this pair in constant time.

We show that the additional cuts placed at trapezoid and bridge nodes admit a lossless encoding from which all cut descriptors in the optimal partition can be reconstructed in $O(n)$ time using $O(n)$ extra space. Importantly, we can generate this encoding during the DP without increasing the asymptotic running time.

One might suspect that we can discard some intervals from an antichain component before passing information to its parent. This is impossible in general: if we discard even one interval before passing the DP state upward, the reduced state no longer determines the optimum.

Let $Q$ be a simple polygon and let $e$ be a vertical edge of $Q$. Let $\overrightarrow{\eta }(e)\in \{\text{left},\text{right}\}$ denote the outward normal direction of $e$. Let $𝒫(Q,e)$ be the set of all simple polygons $P$ for which there exists a simple polygon $R$ such that $P=Q\cup R$ and $Q\cap R\subseteq e$. In other words, $𝒫(Q,e)$ consists of all simple polygons that contain $(Q,e,\overrightarrow{\eta }(e))$ as a subproblem structure in the orthogonal strip partition problem.

Let $\mathrm{𝖠𝗇𝗍}(Q,e)$ be the antichain component computed by Algorithm 1 for the subproblem structure $(Q,e,\overrightarrow{\eta }(e))$. A certificate for $(Q,e,\overrightarrow{\eta }(e))$ is a subset $𝒲\subseteq \mathrm{𝖠𝗇𝗍}(Q,e)$ with the following property: there exists an algorithm that, for every $P\in 𝒫(Q,e)$, computes $\text{opt}(P)$ from given $𝒲$, $\text{opt}(Q)$, and the remaining region $P\setminus Q$. The certificate complexity of $(Q,e,\overrightarrow{\eta }(e))$ is $\min \{|𝒲|\mid 𝒲\text{ is a certificate for }(Q,e,\overrightarrow{\eta }(e))\}$. This viewpoint is standard in lower bound arguments [4], and shows whether pruning $\mathrm{𝖠𝗇𝗍}(Q,e)$ loses information necessary to determine $\text{opt}(P)$.

Although keeping all intervals in the antichain component often appears redundant, Lemma 8 shows that one cannot safely prune intervals in general. There exist instances in which every interval is necessary; hence any greedy approach that discards intervals using only information available in the subproblem fails on some instance.

We now show that no sublinear-time algorithm exists for the value or reporting version, so our algorithm is optimal up to a logarithmic factor. If the input polygon is given as an array of vertices in boundary order and each query reveals one input vertex at unit cost, then any algorithm requires $\mathrm{\Omega }(n)$ time in the worst case.