The required maximum is $n - 2$. This follows from the fact that the image of $f_n$ consists of the first $n - 2$ positive integers.

Induct on $n$ to show that $f_n(P) \le n - 2$ for all $P$ in $\mathcal{P}_n$. The base case $n = 3$ is clear. If $P$ is convex, then $f_n(P) = 1$, since $P$ has three sides whose lines of support form a triangle that covers $P$ — simply extend two non-adjacent sides till they meet to obtain a polygon with fewer sides and proceed inductively.

If $P$ is not convex, consider a vertex $v$ interior to the convex hull of $P$. Extend one of the sides through $v$ beyond $v$ till it first meets again the boundary, to split $P$ into an $n_1$-gon $P_1$ and an $n_2$-gon $P_2$, where $n_1 + n_2 \le n + 2$. Hence $f_n(P) \le f_{n_1}(P_1) + f_{n_2}(P_2) \le n_1 - 2 + n_2 - 2 \le n - 2$.

Given a positive integer $m \le n-2$, we now describe a polygon $P = a_0a_1\dots a_{n-1}$ in $\mathcal{P}_n$ such that $f_n(P) = m$. Consider a parallelogram $aa_0a_1a_{m+1}$, let $a_2, \dots, a_m$ be interior points of the triangle $a_0a_1a_{m+1}$ forming, along with $a_1$ and $a_{m+1}$, an $(m+1)$-point configuration in strictly convex position, and let $a_{m+2}, \dots, a_{n-1}$ be interior points of the triangle $aa_0a_{m+1}$ forming, along with $a_0$ and $a_{m+1}$, an $(n-m)$-point configuration in strictly convex position; clearly, it is always possible to choose the latter so that $P$ has no parallel sides.

For convenience, a triangle formed by the lines of support of three sides of $P$ will be called a peritrigangle.

To show that $f_n(P) \ge m$, notice that, for each index $i$ in the range $1$ through $m$, covering the midpoint of the side $a_i a_{i+1}$ of $P$ requires a peritrigangle $\Delta_i$ lying in the same half-plane as $a_0$ relative to the line $a_i a_{i+1}$, one side of which contains the line-segment $a_i a_{i+1}$. Since, for distinct indices $i$ and $j$ in the range $1$ through $m$, the line $a_i a_{i+1}$ separates $a_0$ and the midpoint of the line-segment $a_j a_{j+1}$, the $\Delta_k$ are pairwise distinct, so $f_n(P) \ge m$.

To conclude that $f_n(P) = m$, notice that $P$ is covered by the $m$ peritriangles formed by the lines $a_0a_1, a_i a_{i+1}$ and $a_{i+1}a_{i+2}$, where $i$ runs from $1$ through $m$.