Consider binary search for finding extremal points of a convex polygon in the given direction.

Let Q be a convex polygon, represented by the vertices of its boundary in clockwise order, say, for example, $Q=p_1,p_2,\ldots,p_n$ with $p_1=p_n$ and $n\ge 3$, and let $\vec\ell$ be a given vector. See Figure (a) for an illustration. Consider the projection of points in Q onto $\vec\ell$. For any two points $q,r \in Q$, we write $q \prec_\ell r$, if the projection of r lies further from the starting end of $\vec\ell$ than the projection of q. See Figure (b) for an illustration, where $p_5$ is further than $p_4$ in the direction of $\vec\ell$.

A point $q \in Q$ is said to be maximal with respect to $\vec\ell$ if there exists no point $r \in Q$ such that $q \prec_\ell r$. Similarly, a point $q \in Q$ is minimal with respect to $\vec\ell$ if there exists no $r \in Q$ such that $r \prec_\ell q$. For example, in Figure (a), both $p_1$ and $p_6$ are maximal points of Q and $p_4$ is the minimal point of Q.

Let $\delta(Q)$ denote the boundary of the convex polygon Q and consider the properties of Q.