Question : Given any $n$ distinct points $S$, consider the $\binom n2$ discs $D_{pq}$ formed by picking a pair of points $p,q$ from $S$ and using them as a diameter. For each disc $D_{pq}$, let $N_{pq}$ be the number of points of $S$ on or inside $D_{pq}$. Let $N_S(n)$ be the largest $N_{pq}$, i.e. $$N_S(n)=\max\{N_{pq} :p,q\in S,p\not=q\}.$$ Let $f(n)$ be the minimum value of $N_S(n)$ when $S$ varies over the set of $n$ points. Then, how can we represent $f(n)$ by $n$ ?
Remark : A user achille hui got the following bounds for $n\gt 3$ :
$$\left\lceil \frac{n}{3}\right\rceil + 1 \le f(n) \le \left\lceil\frac{2n}{3}\right\rceil$$ This fixes $f(4)$ to $3$. (We have $f(3)=2$ trivially.)
The question comes from that I changed 'rectangle' to 'circle' in the following question I met a few weeks ago.
"When we place $n$ distinct points on the $xy$-plane, prove that there exists a rectangle, whose diagonal is closed by two of the $n$ points and whose edges are parallel to either $x$-axis or $y$-axis, has at least $\lfloor(n+1)/5\rfloor+1$ points inside or on the edges."
As a result, the question seems very difficult to me. Can anyone help?
Update : I crossposted to MO.
This is a partial answer, I get following bounds for $n > 3$.
$$\left\lceil \frac{n}{3}\right\rceil + 1 \le f(n) \le \left\lceil\frac{2n}{3}\right\rceil\tag{*1}$$ In particular, this fixes $f(4)$ to $3$.
For any points $p,q,r \in \mathbb{R}^2$, let $\ell_{pq}$ be the line segment joining $p$ and $q$. Let $C_{pq}$ be the circle/disk having $\ell_{pq}$ as a diameter and $\triangle_{pqr}$ be the triangle formed by $p, q, r$.
For any set of $n$ points $S = \big\{\;p_1, p_2, \ldots, p_n \;\big\}$ where $n > 3$. Let $C_{min}$ be the smallest circle/disk covering $S$. It is known that $C_{min}$ is unique and one can determine it by at most 3 points from $S \cap \partial C_{min}$.
If determined by $2$ points $p, q \in S \cap \partial C_{min}$, $\ell_{pq}$ is a diameter of $C_{min}$.
If determined by $3$ points $p, q, r \in S \cap \partial C_{min}$, $\triangle_{pqr}$ is not obtuse.
If there exists $p,q \in S$ such that $\ell_{pq}$ is a diameter of $C_{min}$, then $C_{pq} = C_{min}$ covers $S$.
In this case, $$| C_{pq} \cap S | = |S| = n\tag{*2a}$$
Otherwise, $C_{min}$ is determined by 3 points $p, q, r \in S$ and we can further assume $\triangle_{pqr}$ is an acute triangle. When $\triangle_{pqr}$ is an acute triangle, one can show that${}^{\color{blue}{[1]}}$ $$C_{pq} \cup C_{qr} \cup C_{rp} \supset C_{min} \supset S$$ This means one of $C_{pq}$, $C_{qr}$ and $C_{rp}$ contains at least one third of elements from $S \setminus \big\{\;p,q,r\;\big\}$. As a result, we get
$$\max\big\{\; |C_{pq} \cap S|, |C_{qr}\cap S|, |C_{rp} \cap S| \;\big\} \ge \left\lceil \frac{n-3}{3} \right\rceil + 2 = \left\lceil \frac{n}{3} \right\rceil + 1\tag{*2b}$$
Combine $(*2a)$ and $(*2b)$, we get LHS of $(*1)$.
For the other direction of $(*1)$, one split $S$ into 3 groups $S_1, S_2, S_3$ with sizes $$|S_1| = \left\lfloor \frac{n}{3} \right\rfloor, |S_2| = \left\lfloor \frac{n+1}{3} \right\rfloor\quad\text{ and }\quad |S_3| = \left\lfloor \frac{n+2}{3} \right\rfloor$$ One then place each group "near" the vertices of an equilateral triangle. If one pick $p$ from $S_i$ and $q$ from $S_j$ and form the circle $C_{pq}$, it is clear $C_{qp} \cap S \subset S_i \cup S_j$. This gives us
$$|C_{pq} \cap S| \le n - \min\big\{\; |S_1|, |S_2|, |S_3| \;\big\} = \left\lceil\frac{2n}{3}\right\rceil$$
Since this is true for all $p,q \in S$, this leads to RHS of $(*1)$.
Notes and Details
$\color{blue}{[1]}$ - To illustrate why $C_{pq} \cup C_{qr} \cup C_{rp} \supset C_{min}$, consider the picture at end.
If one drop a perpendicular from $r$ to $pq$ and let $u$ be the corresponding foot, it is easy to see $$\triangle_{pqr} = \triangle_{pur} \cup \triangle_{ruq} \quad\text{ and }\quad \triangle_{pur} \subset C_{rp} \quad( \text{ and similarly } \triangle_{ruq} \subset C_{qr} ) $$ The rest of $C_{min}$ splits into 3 lunes. Let consider the lune formed by the arc and chord joining $p$ to $r$. Let $v$ be any point on the arc $pr$. When $\triangle_{pqr}$ is an acute triangle, we have $$\phi = \measuredangle_{pqr} < \frac{\pi}{2} \quad\implies\quad \measuredangle_{rvp} = \pi - \phi > \frac{\pi}{2}$$ This implies $v$ belongs to that part of semi-circle of $C_{pr}$ outside $\triangle_{pqr}$. As a consequence, arc $pr$ lies inside $C_{pr}$. Since the corresponding lune is a convex hull of arc $pr$, $C_{pr}$ cover that lune. Same thing happens to other lunes. From this, we can conclude $C_{pq}, C_{qr}$ and $C_{rp}$ indeed cover $C_{min}$.