Collinear convex hull

The problem is to find the outer boundary of the union of the squares. We state two claims that help design an $O(n)$ algorithm, where $n$ are the number of given squares.

Let $S_1,\dotsc,S_n$ be the set of given squares. Each square boundary is composed of four line segments. Let $L = \{\ell_1,\dotsc,\ell_m\}$ be the multiset of all the line segments of all squares. By the definition of the boundary, the following claim holds:

Claim 1: A line segment $\ell_i \in L$ forms the boundary of the union if and only if it appears exactly once in the multiset $L$.

The above claim is easy to see. That is, if a line segment $\ell_i$ appears more than once in $L$, then it is shared by some two squares thus it is not a part of the boundary of the union. Now, we state the second claim.

Let $L'$ be the set of line segments that appears exactly once in $L$. Since each square shares at least one side with another square, the following claim holds:

Claim 2: Each line segment $\ell_i \in L'$ shares each of its end point with one other line segment in $L'$.

Using claim $1$ and $2$, the following algorithm finds the outer boundary $B$ of the union of the squares:

1. Given $L$, find $L'$ using a hash map in $O(n)$ time.
2. Let $E$ be the set of all end points of the line segments in $L'$. Create a hash map $H$ such that each endpoint in $E$ maps to the two line segment in $L'$ which incident on it. It can be done in $O(n)$ time.
3. Let $e_l$ be an endpoint in $E$ that has the least $x$ coordinate value. This endpoint is definitely a part of the outer boundary. Add $e_{l}$ to set $B$.
4. Let $\ell_e$ be one of the line segment in $L'$ that is incident on $e_l$. The line segment $\ell_e$ can be found in $O(1)$ time using hash map $H$.
5. Let $e'$ be the other end point of $\ell_e$. Add $e'$ to $B$.
6. Repeat step $4$ with $e_l$ replaced with $e'$ till the complete boundary is traversed. The complete boundary is traversed when $e_l$ is encountered again.

The step $4$ and $5$ can be implemented in $O(1)$ time using hash map. Therefore, the overall running time is linear in $n$, i.e., $O(n)$.