Non-crossing Hamiltonian Paths and Cycles
in Output-Polynomial Time

We describe a method for encoding a non-crossing path using this many bits of information, so that each path is uniquely described by this encoding. For an encoding with $b$ bits of information, the number of paths can be at most $2^{b}$ and the logarithm of this number is $O(b)$. Let $K$ be a subset of $S$, with $|K|=k$, such that $S\setminus K$ lies on a line $L$, and let $P$ be any given non-crossing path in $S$. Let $\ell=|L\cap S|$; because $k$ is the minimum number of points that can be removed to form a collinear set, no point of $K$ can lie on $L$, and $\ell=n-k$. To describe $P$, we combine the following pieces of information:

• •

  The set $Q$ of points of $L\cap S$ that belong to $P$, but for which zero or one of their neighbors in the path belong to $L$. Each such point is one of the two neighbors of a point in $K$, or one of the two ends of $P$, so $|Q|\leq 2k+2$. $Q$ can be encoded by specifying its size and the subset of $L\cap S$ of that size, out of $\tbinom{\ell}{|Q|}$ possibilities, so by Lemma 11 the number of bits needed to specify it is $O\bigl{(}\log n+k+k\log(n/k)\bigr{)}$. (Both the $\log n$ term and the $+1$ in the statement of the lemma are included to handle the case when $k=0$ but $|Q|>0$. Lemma 11 applies only when $k\leq n/2$ but for larger $k$ the bound to be proven is superlinear and the result is immediate.)

• •

  For each point in $Q$, a specification of whether it has a neighbor in $L$, and if so in which direction. This takes $O(k)$ bits of information.

• •

  The induced subgraph $P[K\cup Q]$, a linear forest using only the points in $K\cup Q$, and omitting the edges of $P$ that lie entirely within $L$. As with any type of planar straight-line graph, the number of linear forests on $O(k)$ points is singly exponential in $k$ [30], so $P[K]$ can be encoded with $O(k)$ bits of information.

Then $P$ may be recovered by combining the induced subgraph $P[K\cup Q]$ with segments of $L$ starting and ending at points of $Q$ and continuing in the specified direction from each of these points. All pieces of this encoding add up to the stated bound on the number of bits needed to encode the entire path. ∎

Maximal visible-vertex paths are Hamiltonian, by definition: they are defined to be paths that use all the points. Because each step in a visible-vertex path is defined locally, without respect to the earlier parts of the path, the ability to extend every non-maximal path follows immediately from 14.

It remains to prove that the resulting paths are non-crossing. For every segment $pq$ of the path, the next segment is incident to $q$ and therefore cannot cross $pq$. All segments after the next segment lie within the convex hull of the remaining points after $q$. Since $p$ and $q$ are vertices of their respective convex hulls, the convex hull of the points after them in the path does not contain them. Moreover, segment $pq$ does not cross this hull, because if it did then $q$ would not be visible from $p$. Thus, these later segments are disjoint (as closed line segments) from the closed line segment $pq$ and so cannot cross $pq$ nor even pass through $q$. Therefore, $pq$ cannot intersect any later segment. For each pair of segments in the path, a crossing is ruled out by applying this argument to the earlier of the two segments in the path, so no crossing can exist. ∎

Form a maximal visible-vertex path beginning at $p$, at each step choosing a visible vertex that is not $q$ when this is possible. By 14, the path will have two points to choose between (one of which is not $q$) until the remaining points become collinear. Once they do, all remaining points that are not $q$ will lie between $q$ and the current end of the path, so $q$ cannot be included in the path until it is the last point remaining. ∎

We form a tree $T$ of visible-vertex paths, in which the root is the empty sequence of vertices and the parent of any nonempty path is obtained by removing its last vertex (Fig. 2). By Lemma 15, the leaves of $T$ are non-crossing Hamiltonian paths. The root node of $T$ has at least three children (one for each convex hull vertex). In the nodes of $T$ at distance at most $\textsc{offline}(S)$ from the root, the last point in the path represented by each node is not collinear with the remaining points, by the definition of offline. It follows by 14 that these nodes have at least two choices of visible vertices and therefore that they have at least two children.

As a tree in which the root node has at least three children and the nodes in the next $\textsc{offline}(S)$ levels have at least two children, $T$ has at least $3\cdot 2^{\textsc{offline}(S)}$ leaves. Each leaf is a non-crossing Hamiltonian path, and each non-crossing Hamiltonian path can come from at most two leaves (one for each endpoint, if both endpoints are convex hull vertices). Therefore, there are at least $\tfrac{3}{2}\cdot 2^{\textsc{offline}(S)}$ non-crossing Hamiltonian paths. ∎

We may assume without loss of generality that $\ell\geq 2$, for otherwise the lemma states only that there exists a single non-crossing Hamiltonian path, known to be true. For convenience consider an orientation of the plane in which $L$ is horizontal and $S$ lies in the closed halfspace above $L$. We will prove the lemma by constructing many non-crossing Hamiltonian paths in which the points of $L\cap S$ appear in left-to-right order, and no point in $L$ has two neighbors in $S\setminus L$. For any such path, define its signature to be the binary sequence with a $1$-bit for points in $L$ and a $0$-bit for points in $S\setminus L$ (Fig. 3). It has length $n$, with $\ell$ $1$-bits, and does not have any three consecutive bits in the pattern $010$. The number of $010$-avoiding sequences with $n$ bits and $\ell$ $1$-bits is [25]

where for the simpler formula on the right hand side of the inequality the $1$-bits are grouped into $\lfloor\ell/2\rfloor$ pairs (with one group of three if $\ell$ is odd) and we count only the sequences in which each pair or triple appears consecutively. (By the assumption that $\ell\geq 2$, at least one such grouping is possible.) As we argue in the remainder of the proof, every $010$-avoiding sequence is the signature of at least one non-crossing Hamiltonian path, so this lower bound on the number of $010$-avoiding sequences also provides a lower bound on the number of non-crossing Hamiltonian paths.

For a given $010$-avoiding sequence $\sigma$, let $n_{i}$ denote the length of the $i$th non-empty block of consecutive $0$-bits in $\sigma$. We will partition the halfplane above $L$ into convex sets $C_{i}$, each containing $n_{i}$ points of $S\setminus L$, by a greedy process that maintains a convex subset of the halfplane containing the remaining points to be partitioned. Initially the convex subset is the entire halfplane and the remaining points are $S\setminus L$. On the $i$th step (for any $i$ other than the last one), let $p_{i}$ be the point of $S\cap L$ that corresponds to the $1$-bit of $\sigma$ following the $i$th block of $0$-bits. Sort the remaining points of $S\setminus L$ radially around $p_{i}$ (in left to right order with respect to $L$) breaking ties in favor of closer points to $p_{i}$, and let $q_{i}$ be the point in position $n_{i}$ of this sorted order. Draw line $p_{i}q_{i}$, separating $C_{i}$ on its left from a remaining convex subset on its right. Assign the $n_{i}$ points up to $q_{i}$ in the radial sorted order to set $C_{i}$, and leave the remaining points (possibly including farther points on line $p_{i}q_{i}$) unassigned. In the final step of this construction, assign all remaining points to the final remaining convex region. For instance, in Fig. 3, the leftmost set $C_{1}$ (yellow) is separated from the rest of the halfplane by line $p_{1}q_{1}$. Here $p_{1}$ is the leftmost point of $L$, and $q_{1}$ is the fifth point in the radial ordering around $p_{1}$. Point $q_{1}$ lies on the boundary of four convex regions but is assigned to the first, $C_{1}$. Line $p_{1}q_{1}$ also contains another point of $S$, farther from $p_{1}$, which is assigned to $C_{4}$ (green).

Once this partition into convex sets has been determined, use Lemma 16 to find a non-crossing Hamiltonian path within each convex set $C_{i}$ that starts and ends at its (one or two) points on $L$, and connect these paths in sequence by segments of $L$ to form a non-crossing Hamiltonian path for all of $S$, with the given $010$-avoiding sequence $\sigma$ as its signature. ∎

For any $k$, the logarithm of the number of non-crossing Hamiltonian paths is $\Omega(k)$ by Lemma 17. For $k\geq n/3$, $\log(n/k)=O(1)$, so for this range of $k$, this $\Omega(k)$ bound is equivalent to the bound stated in the theorem.

For smaller values of $k$, let $K$ be any set of $k$ points whose removal from $S$ leaves a collinear set of size $\ell=n-k=\Omega(n)$, belonging to a line $L$. Partition $K$ into the two subsets $K_{1}$ and $K_{2}$ on the two sides of $L$, with $|K_{1}|\geq|K_{2}|$; let $|K_{1}|=k^{\prime}\geq k/2$. Let $p$ be the first point of $S\cap L$, in the sorted sequence of the points along this line, let $\ell^{\prime}=\ell-1$ be the number of remaining points in $S\cap L$, and let $n^{\prime}=\ell^{\prime}+k^{\prime}$. By Lemma 18, the number of non-crossing Hamiltonian paths of $S\setminus K_{2}$ that start at $p$ is at least

Each such path can be extended to a non-crossing Hamiltonian path of all of $S$ by concatenating any non-crossing path through $p$ and the points of $K_{2}$. By the assumption that $k<n/3$, the bottom term of the right binomial coefficient is at most half the top term, allowing us to apply Lemma 11. By this lemma, and the facts that $k^{\prime}=\Theta(k)$ and $\ell^{\prime}=\Theta(n)$, the logarithm of this binomial coefficient is $\Omega\bigl{(}k\log(n/k)\bigr{)}$ as stated. ∎

Taking logs of both sides, it is equivalent to write that

This follows immediately from Lemma 19 and Lemma 12, according to which $\log\textsc{\#ham}(S)$ is lower-bounded and $\log\textsc{\#path}(S)$ upper-bounded (respectively) to within constant factors by formulas that differ from each other only in an additive $\log|S|$ term. ∎

The convex hull vertices cannot be interior to the hull or interior to an edge, by definition, so being a vertex of the cycle is the only way they can be surrounded. Any other segment between hull vertices would block all visibilities from one side of the segment to the other. A non-crossing cycle using such a segment could only have vertices on one side of the segment, and would be unable to have among its vertices the vertices of the convex hull of $S$ that lie on the other side. ∎

As in Lemma 12 we describe a method for encoding a surrounding cycle using this many bits of information, so that each cycle is uniquely described by this encoding. Let $H$ be the set of convex hull vertices of $S$, let $I=S\setminus H$ be the set of interior points, and let $C$ be the surrounding cycle that we are trying to describe. To describe $C$, we combine the following pieces of information:

• •

  The set $Q$ of points of $H$ that belong to $C$, but for which zero or one of their neighbors in the hull belong to $C$. There can be at most $2h$ such points (two neighbors of each point in $I$). $Q$ can be encoded by specifying its size and the subset of $H$ of that size, out of $\tbinom{n-h}{|Q|}$ possibilities, so by Lemma 11 the number of bits needed to specify it is $O\bigl{(}h+h\log(n/h)\bigr{)}$. (The case where $|Q|$ is too large for Lemma 11 to apply is trivial as this would make the bound we are proving superlinear.)

• •

  For each point in $Q$, a specification of whether it has a neighbor in $H$, and if so in which direction. This takes $O(h)$ bits of information. (This information is redundant when the point in $Q$ is adjacent in $H$ to a point of $H\setminus Q$, as all such pairs must be neighbors, but is needed when $Q$ contains multiple consecutive points of $H$.)

• •

  The induced subgraph $C[I\cup Q]$, a cycle or linear forest using only the points in $I\cup Q$. As with any type of planar straight-line graph, the number of linear forests on $O(h)$ points is singly exponential in $h$ [30], so $C[I\cup Q]$ can be encoded with $O(h)$ bits of information.

Then $C$ may be recovered by combining the induced subgraph $P[I\cup Q]$ with convex hull subsequences starting and ending at points of $Q$ and continuing in the specified direction from each of these points. All pieces of this encoding add up to the stated bound on the number of bits needed to encode the entire path. ∎

When $m=\textsc{inhull}(S)$ this is Lemma 23. When $m=\textsc{offline}(S)$ this follows immediately from Lemma 12, as each surrounding cycle can be made into a path by removing an edge, and no two such paths can come from the same cycle. ∎

We assume $n\geq 3$ else the lemma is trivial. Draw a line $L$ through $p$ that does not pass through any other point of $S$, splitting $S\setminus\{p\}$ into two subsets $A$ and $B$ in its two half-planes, with $|A|=\lfloor(n-1)/2\rfloor$ and $|B|=\lceil(n-1)/2\rceil$. For each of the possible $\tbinom{n-1}{\lfloor(n-1)/2\rfloor}$ binary sequences $\sigma$ having $|A|$ 0-bits and $|B|$ 1-bits, we will find a vertex-visible path $P_{\sigma}$ that has a point of $A$ for each 0 in $\sigma$ and a point of $B$ for each 1 in $\sigma$, ending in $p$.

To do so, we will construct this sequence one point at a time. As long as the remaining unchosen points include at least one point of $A$ and at least one point of $B$, the line $L$ will continue to separate points in $A$ from points in $B$. The convex hull of the remaining points must have a “bridge” edge $e$ with one point in each set; $e$ is crossed by $L$. Throughout the process we will maintain the following property as an invariant: the sequence constructed so far, both endpoints of this bridge edge $e$ are valid additions to a vertex-visible path (although only one of the two will match sequence $\sigma$). This invariant is automatically true at the start of the path construction process, when the path constructed so far is empty, because any convex hull vertex is a valid addition to an empty vertex-visible path.

At each subsequent step, let $e$ be the bridge edge. By the invariant, both endpoints of $e$ are valid additions to the path. We choose the endpoint that belongs to the set determined by the corresponding bit of $\sigma$, $A$ for a 0-bit or $B$ for a 1-bit. By the general position assumption, this chosen endpoint can see the other endpoint of $e$, in the other set. If it is not the last point in the set ($A$ or $B$) that contains it, it can also see at least one vertex of the convex hull of the remaining points that lies in its own set. Since the convex hull vertices that it sees must form a contiguous subsequence of the convex hull, it can see both endpoints of the new bridge edge crossed by $L$, separating $A$ from $B$, and the invariant is maintained.

Once all vertices in $A$ or in $B$ have been included in the vertex-visible path, we can complete the path in the same way as Lemma 16. Because all paths constructed in this way can be distinguished from each other by the order in which they use vertices from $A$ and from $B$, they are all distinct from each other. ∎

The process in Lemma 25 can be reinterpreted as non-deterministically choosing either a point from $A$ or a point from $B$ at each step, until running out of points in one of the two sets and then completing the path deterministically. This produces a binary tree of possible choices, and the the proof of Lemma 25 can be interpreted as counting the branches of this tree. A simpler analysis, less tight but still exponential, would observe that in this tree, each choice uses up one point of either $A$ or $B$, and the number of points in both steps starts at approximately $n/2$. Therefore, the height (minimum number of steps from the root of the decision tree in any branch until running out of choices) is approximately $|S|/2$, and the number of branches is at least $2^{|S|/2}$. We will generalize this process to allow non-binary choices, using a weighted definition of the height of the decision tree where the weight of each step is the binary logarithm of the number of available choices at that step. If we can show that each step that uses up some number $x$ of points gives us a number of choices that is exponential in $x$, then the weight of that step will be proportional to $x$ and the total height of the decision tree will be again linear in $|S|$, implying that again it has an exponential number of branches. With these generalities out of the way, it remains to show how to generalize the non-deterministic decision process of Lemma 25 so that, whenever we use up many points, we select from a number of choices that is exponential in the number of used-up points.

We define the line $L$ and the subsets of points $A$ and $B$, initially of size approximately $|S|/2$, in exactly the same way as in the proof of Lemma 25. We will build a non-crossing path to $p$, covering all points in $S$, in a sequence of steps. It will not necessarily be a visible-vertex path, but we will maintain after each step the same invariants as in Lemma 25. Namely, the path constructed so far will remain disjoint from the convex hull of the remaining points (so that any non-crossing path within those remaining points will be non-crossing globally), and as long as $A$ and $B$ are both non-empty, the unique $A$–$B$ edge $e$ of the convex hull of the remaining points will be entirely visible from the last point that has already been added to the path, so that any point on $e$ may be added as the next point on the path. We distinguish the following cases:

• •

  If there are fewer than $|S|/3$ points remaining in $A$ or $B$, stop making choices and complete the rest of the path deterministically.

• •

  If $A\cap e$ and $B\cap e$ are both small (at most three points), we extend the current path by a segment to one of the two endpoints of $e$, and then (if its visibility along $e$ is blocked by another point in the same set) by more segments to one or both blocking points. This case produces two choices (which endpoint of $e$ to extend to) and uses up at most three points of $A$ or $B$. It maintains the invariant by the same reasoning as in Lemma 25.

• •

  Otherwise, at least one of $A\cap e$ or $B\cap e$ is large (at least four points). We describe the case when $A\cap e$ is large; the case for $B\cap e$ large is symmetric. Let $x=|A\cap e|$, the number of points of $A$ on edge $e$ of the convex hull. Let $r$ be the point where $L$ crosses $e$. Draw a ray $R$ from $r$ that separates the remaining points not yet on the path into two subsets $X$ and $Y$ with $(A\cap e)\subset X$ and $|X|=2x$, breaking ties in such a way that the convex hulls of $X$ and $Y$ stay disjoint. Because $x\leq|S|/6$ points lie on a line and at least $|S|/3$ remaining points lie in $A$, $X\subset A$, and ray $R$ lies entirely on $A$’s side of line $L$. In Fig. 5, $e$, $r$, and $R$ are labeled; $x=7$, and $X$ is the subset of 14 points whose convex hull is shown as the red shaded area. The blue shaded area is the convex hull of $Y$.

  Among the vertices of the convex hull of $X$, at least one (the point in $A\cap e$ closest to $r$) can see a point in $B\cap Y$, the nearest one on edge $e$, along a segment exterior to the hull. Also, at least one of the vertices of the convex hull of $X$ on $R$ can see any remaining points in $A\cap Y$, along a segment exterior to the hull. Therefore, some vertex $q$ of the convex hull of $X$, on or between these two hull vertices, can see all of the unique $A$–$B$ edge of the convex hull of $Y$. For instance, $q$ may be chosen by triangulating the region between the convex hulls of $X$ and $Y$, and choosing the apex of the triangle on this edge. Fig. 5 depicts a case where $q$ can neither be on $e$ nor $R$.

  We will extend the current path, from its current endpoint, to one of the two endpoints of $X\cap e$ (in the figure, the endpoint farthest from $r$), through all points of $X$, ending at $q$. Because $e$ separates $Y$ from the first of these added segments, the remaining added segments lie within the convex hull of $X$, and $R$ separates the convex hulls of $X$ and $Y$, it follows that this extension maintains the invariant that the path so far is disjoint from the convex hull of the remaining point set $Y$. Because $q$ was chosen as a point that could see the $A$–$B$ edge of the convex hull of $Y$, it follows that this extension also maintains the invariant that any point along this edge could be added to the path next.

  By Lemma 18, the number of paths through $X$ that start and end at the two extreme points of $X\cap e$ is exponential in $x$. However, instead we need paths that start at one extreme point of $X\cap e$ and end at $q$. To obtain an exponential bound on the number of paths of this type, we use the same method as in the proof of Lemma 18: we consider $010$-avoiding sequences of length $2x$, in which each $0$ describes a point on the path that belongs to $X\cap e$ and each $1$ describes a point on the path that belongs to $X\setminus e$. Each such sequence can then be realized as a path by the method used in Lemma 18, which creates a convex subset of $X\setminus e$ corresponding to each block of consecutive 1-bits of the sequence. In order to obtain a path that starts at an extreme point of $X\cap e$ and that ends at $q$, it is necessary and sufficient that the corresponding $010$-avoiding sequence have a $0$ at one of its ends (representing the starting extreme point) and a large enough consecutive block of 1’s at the other end for $q$ to be included in that block. Here “large enough” depends on the arrangement of $X$, but each point of $X\setminus e$ contributes to this required block size only when it is more extreme than $q$ in the radial ordering of points around one extreme point of $X\cap e$, and when this happens it cannot also contribute to the required block size for the other extreme point. Therefore, for one of the extreme points of $X\cap e$, at least $x/2$ of the $1$-bits are free to be anywhere in the $010$-avoiding sequence, rather than forced to be in the contiguous block of $1$s at the end of the sequence. This is enough to produce an exponential number of $010$-avoiding sequences and an exponential number of path extensions ending at $q$.

Each step produces a number of choices exponential in the number of points that it uses up, until we have used up at least $|S|/6$ points and switch to the deterministic completion. Therefore, the total number of branches of the decision tree, and the total number of paths that it can produce is exponential in $|S|$. ∎

At least $6|S|/7$ points of $S$ are interior to the convex hull, within which the number of collinear points meets the conditions of Lemma 25. By Lemma 25, there are exponentially many distinct non-crossing Hamiltonian paths through the subset of interior points, starting and ending at a vertex of the convex hull of the interior points. It remains to argue that each such path $P$ has a polygonalization $C_{P}$ that uses the points of $P$ in path order. Because each two polygonalizations constructed in this way have a different ordering on the interior points of $S$, they will be distinct polygonalizations.

Therefore, let $P$ be any non-crossing Hamiltonian path through the subset of interior points, starting and ending at a vertex of the convex hull of the interior points. Triangulate the region between the convex hull of the interior points and the convex hull of $S$, and extend each end of $P$ by an edge from the triangulation; these edges must connect to convex hull vertices of $S$, and cannot cross each other. If they do not meet, complete the extended path to a polygon by following edges around the convex hull of $S$ from one endpoint of the extended path to the other. Let $Q$ be the resulting simple polygon. In most cases, $Q$ will not be a surrounding polygon of $S$, but the only points missing from $Q$ will be some of the convex hull vertices of $S$.

We now apply an argument of Steinhaus [32] to show that $Q$ can be completed to a polygonalization $C_{P}$, preserving the cyclic ordering of the points already in $Q$. Consider each point $q$ of the convex hull of $S$ that is not already in $Q$, in an arbitrary order. Because $q$ is on the convex hull, it cannot be surrounded by a cycle of edges, each partially obscuring the next in the cycle: the visibility ordering of edges of $Q$, as viewed from $q$, is acyclic. Therefore, at least one edge of $Q$ is completely visible to $q$. Replace this edge by a pair of edges through $q$ (gluing a triangle formed by this edge and $q$ onto the polygon; see Fig. 6). After gluing in all remaining convex hull vertices in this way, the result is a polygonalization of $S$. ∎

The points on the convex hull of $S$ partition it into $h$ segments. Consider any diagonal edge $e$ that partitions these segments into two subsequences of equal or nearly equal length; choose arbitrarily one of the two endpoints of $e$ to be first and the other to be second. At least one of the two sides of $e$ will contain at least $\lceil(n-h)/2\rceil$ points that are not on the hull (shown on the right side of $e$ in Fig. 7); let $I$ denote this set of points. On the other side of $e$, we can find $\lfloor h/4\rfloor$ disjoint segments of the hull; let $D=d_{1},d_{2},\dots$ denote this sequence of segments, in order from the first endpoint of $e$ to the second endpoint of $e$ (shown in red on the left side of Fig. 7).

We will partition the interior of the convex hull of $S$ into convex regions $C_{i}$, associated with and including each segment $d_{i}$ (the four colored regions in Fig. 7, with interior points colored by which region they belong to). Given such a partition, we can find a polygonalization that modifies the convex hull (a surrounding polygon) by replacing each segment $d_{i}$ by a Hamiltonian path through the non-hull points in $C_{i}$, according to Lemma 16. Let $n_{i}=|I\cap C_{i}|$; then the polygon constructed in this way has $n_{i}$ points of $I$ between the endpoints of $d_{i}$, allowing it to be distinguished from any polygon coming from a partition with different values of $n_{i}$. The numbers $n_{i}$ are non-negative and sum to $|I|$, and the number of ways of choosing non-negative numbers $n_{i}$ that sum to $|I|$ is at least equal to the binomial coefficient in the lemma (possibly larger if $D$ or $I$ are larger than their minimum sizes). It remains to prove that each such choice can be represented by a convex partition, and therefore also by a polygonalization.

As in Lemma 18 we construct these convex sets $C_{i}$ by a greedy process in sequence order. At each step, we maintain the invariant that the remaining points not assigned to a convex set lie within a convex set $K_{i-1}$ formed by the intersection of the convex hull of the input and a half-plane, and that $K_{i-1}$ includes at least one point of $e$. The convex sets $K_{i}$ are not shown in the figure, but can be reconstructed as the union of the sets $C_{j}$ for $j>i$. As a base case, let $K_{0}$ be the convex hull of all of the given points. To construct $C_{i}$, we consider the following cases.

• •

  If $d_{i}$ is the last segment in sequence $D$, let $C_{i}=K_{i-1}$. In the figure, $C_{4}$ is constructed by this case.

• •

  If $d_{i}$ is not the last segment, but all segments $d_{j}$ for $j>i$ have $n_{j}=0$, let $p_{i}$ be the second endpoint of $d_{i}$. Draw line $L_{i}$ through $p_{i}$ and the second endpoint of $e$, and cut $K_{i-1}$ along $L_{i}$ into two convex subsets. Let $C_{i}$ be the subset containing $d_{i}$ and let $K_{i}$ be the other subset. Assign to $C_{i}$ any points on line $L_{i}$.

• •

  If $n_{i}=0$, draw $L_{i}$ from the same point $p_{i}$ to the point on $e\cap K_{i-1}$ closest to the first endpoint of $e$. As in the previous case, and cut $K_{i-1}$ along $L_{i}$ into $C_{i}$ and $K_{i}$, assigning points on $L_{i}$ to $C_{i}$. In the figure, $C_{3}$ is constructed by this case.

• •

  In the remaining case, number the points in $I\cap K_{i-1}$ in radial order around $q$, breaking ties in favor of closer points to $q$, and draw line $L_{i}$ through $q$ and the point in position $n_{i}$ in this numbered sequence. Cut $C_{i-1}$ along $L_{i}$ into two convex subsets $C_{i}$ and $K_{i}$, where $C_{i}$ contains $d_{i}$ and $K_{i}$. For points that lie on $L_{i}$, assign the one numbered $n_{i}$ and any closer points to $C_{i}$, and assign any farther points to $K_{i}$. For instance, in the figure, line $L_{1}$ contains two interior points; the closer yellow point is the one labeled $n_{1}=3$, and is assigned to $C_{1}$, while the farther blue point is assigned to $K_{1}$ and later to $C_{2}$.

In this way, the construction assigns exactly $n_{i}$ points of $I$ to the convex region $C_{i}$. These regions partition the convex hull of $S$, in such a way that all interior points of the hull (regardless of whether they belong to $I$) belong to exactly one of these regions. Each assignment can be used to construct a distinct polygonalization, and the number of assignments is at least the value given in the lemma. ∎

We consider the following cases:

• •

  If $\textsc{inhull}(S)\leq 6n/7$, the result follows from Lemma 28. In particular this applies when the largest subset of collinear points in $S$ has size $\geq n/7$ and is part of the convex hull.

• •

  If the largest subset of collinear points in $S$ has size $\geq n/7$ but is not part of the convex hull, then let $L$ be the line through this subset. Because $L$ does not lie on the convex hull, $S\setminus L$ includes points on both sides of $L$, with at least $m/2$ points in one of these two halfplanes. By Lemma 18 the number of Hamiltonian paths through the points in $L$ and the points in this halfplane, starting and ending at the two extreme points of $L$, meets or exceeds the lower bound in the statement of this lemma. Each of these Hamiltonian paths can be completed to a polygonalization through the points in the other halfplane bounded by $L$, by Lemma 16.

• •

  In the remaining case, the largest subset of collinear points in $S$ has size $<n/7$ and $\textsc{inhull}(S)\geq 6n/7$. In this case, $m=\Omega(n)$ and the bound of the lemma reduces to $\Omega(n)$. The result follows from Lemma 27.

Since all cases have at least the number of polygonalizations stated, the bound holds.

For a bound of $\Omega(i)$, apply Lemma 27, and for $\Omega(i\log n/i)$ when $i\leq n/2$, apply Lemma 28, in both cases using Lemma 11 to estimate the logarithm of the binomial coefficient. ∎