(1) Let the coordinates of $Q_i$ be $(x_i, y_i)$. Without loss of generality, assume $x_1 < x_2 < x_3$. Since both the conditions and conclusion are symmetric under reflection about the $x$-axis and $y$-axis, we can further assume $y_1 < y_3 < y_2$. After appropriate translation, we may set $x_1 = y_1 = 0$, so $0 < x_2 < x_3$ and $0 < y_3 < y_2$. Since $\{Q_1, Q_2, Q_3\}$ is sparse,
$$A = (x_3 - x_2)(y_2 - y_3) \ge 1, \quad B = x_2y_2 \ge 1, \quad C = x_3y_3 \ge 1.$$
The area of triangle $Q_1Q_2Q_3$ is $S = \frac{1}{2}(x_3y_2 - x_2y_3)$, and we have
$$\begin{align*} (2S)^2 &= (x_3y_2 - x_2y_3)^2 = (x_3y_2 + x_2y_3)^2 - 4x_3y_2x_2y_3 \\ &= (A + B + C)^2 - 4BC = A^2 + 2A(B + C) + (B - C)^2 \\ &\ge 5, \end{align*}$$
which proves $S \ge \frac{\sqrt{5}}{2}$.

(2) Define the $L^1$ distance between two points $A(a_1, a_2), B(b_1, b_2)$ as $d_1(A, B) = |a_1 - b_1| + |a_2 - b_2|$. It's easy to verify that the $L^1$ distance satisfies the triangle inequality
$$d_1(A, B) + d_1(B, C) \ge d_1(A, C),$$
with equality when $A, B, C$ are colinear in order. It's known that if convex polygon $Q$ is contained in convex polygon $R$, then the perimeter of $Q$ doesn't exceed that of $R$. Using similar proof methods and the triangle inequality for $L^1$ distance, we can show that under these conditions, the $L^1$ perimeter of $Q$ (sum of $L^1$ lengths of its sides) doesn't exceed that of $R$.
Let $R$ be the given square with side length $a$, and $P = \{P_1, \dots, P_n\}$ be a sparse subset of $R$. By the definition of sparse sets, for any $i \neq j$,
$$|x_i - x_j| + |y_i - y_j| \ge 2\sqrt{|x_i - x_j| \cdot |y_i - y_j|} \ge 2,$$
i.e., $d_1(P_i, P_j) \ge 2$.
For a triangle $\triangle P_i P_j P_k$ with vertices in $P$, if $P_i$ lies inside the rectangle with $P_j P_k$ as diagonal and sides parallel to the coordinate axes, we call $\triangle P_i P_j P_k$ a bad triangle, $\angle P_j P_i P_k$ its bad angle, and $P_j P_k$ its bad edge. Each bad triangle has exactly one bad angle and one bad edge. Let $\ell(\triangle P_i P_j P_k) = d_1(P_j, P_k)$ be the length of the bad edge, which equals $d_1(P_j, P_i) + d_1(P_i, P_k)$. If no angle of $\triangle P_i P_j P_k$ is bad, we call it a good triangle. Part (1) shows that good triangles have area at least $\frac{\sqrt{5}}{2}$.

Let the convex hull of $P$ be an $m$-gon $Q = Q_1Q_2\cdots Q_m$. We first state a lemma:
Lemma: There exists a triangulation $\mathcal{T}$ of $Q$ consisting of $2n-m-2$ triangles with vertices in $P$, such that the number of bad triangles in $\mathcal{T}$ doesn't exceed $2a$.
We'll use this lemma to prove the main result. Take a triangulation $\mathcal{T}$ satisfying the lemma. Since the $L^1$ perimeter of $Q$ doesn't exceed that of $R$,
$$4a \ge \sum_{i=1}^{m} d_1(Q_i, Q_{i+1}) \ge 2m,$$
so $m \le 2a$. As $\mathcal{T}$ has at most $2a$ bad triangles, the number $N$ of good triangles satisfies
$$N \ge (2n - m - 2) - 2a \ge 2n - 4a - 2.$$
Since the total area of good triangles doesn't exceed the area of $R$ and each good triangle has area at least $\frac{\sqrt{5}}{2}$,
$$a^2 \ge \frac{\sqrt{5}}{2}N \ge \frac{\sqrt{5}}{2}(2n - 4a - 2),$$
which implies $n \le \frac{a^2}{\sqrt{5}} + 2a + 1$.

Next, we prove the lemma. Consider a triangulation $\mathcal{T}$ of $Q$ that minimizes both the number of bad triangles and, subject to that condition, minimizes the sum of all bad angles.

For any internal bad triangle $ABC$ in $\mathcal{T}$ with bad edge $BC$, there exists another triangle $BCD$ sharing the edge $BC$. Let $\mathcal{T}'$ be the triangulation obtained by replacing triangles $\triangle ABC$ and $\triangle BCD$ with $\triangle ABD$ and $\triangle ACD$.
As shown in the figure, point $D$ may lie in regions $Y_1$ through $Y_5$. For each possible position of $D$, we can carefully analyze how the number of bad triangles and the sum of bad angles change when transforming $\mathcal{T}$ to $\mathcal{T}'$, as described in the following table:

By the minimality of $\mathcal{T}$, we conclude that $D \in Y_5$. In this case, $\triangle BCD$ is also a bad triangle. If $D$ is in the bottom-left $Y_5$ region of the figure, then $CD$ is the bad edge of $\triangle BCD$, giving $\ell(\triangle BCD) = d_1(D, B) + d_1(B, C) \ge \ell(\triangle ABC) + 2$. If $D$ is in the top-right $Y_5$ region, then $BD$ is the bad edge of $\triangle BCD$, giving $\ell(\triangle BCD) = d_1(B, C) + d_1(C, D) \ge \ell(\triangle ABC) + 2$.
In summary, for any internal bad triangle $\Delta_0$, the triangle $\Delta_1$ on the other side of its bad edge is also bad, with $\ell(\Delta_1) > \ell(\Delta_0)$. If $\Delta_1$ is also internal, then the triangle $\Delta_2$ on the other side of its bad edge is bad, and so on, forming a unique chain of bad triangles:
$$\Delta_0 \rightsquigarrow \Delta_1 \rightsquigarrow \dots \rightsquigarrow \Delta_k,$$
ending with a boundary bad triangle $\Delta_k$. Denote this chain by $C(\Delta_0)$. For a boundary bad triangle $\Delta_0$, $C(\Delta_0)$ contains only $\Delta_0$ itself.