My problem! We claim the answer is $3n-6$, achieved by $S=\{(0,1),(0,-1),(1,0),(2,0),\ldots,(n-2,0)\}$. Then, the tasty pairs are of the form $\{(0,1),(i,0)\}$, $\{(0,-1),(i,0)\}$, $\{(i,0),(i+1,0)\}$, or $\{(0,1),(0,-1)\}$. Clearly, if $A$, $B$, and $C$ are collinear in that order, then $\{A,C\}$ cannot be a tasty pair. The main claim is the following. Claim: If $ABCD$ is a convex quadrilateral, then $\{A,C\}$ and $\{B,D\}$ cannot both be tasty pairs. Proof: Since $\angle A+\angle B+\angle C+\angle D=360^\circ$, we must have either $\angle A+\angle C \ge 180^\circ$ or $\angle B+\angle D \ge 180^\circ$. If $\angle A+\angle C \ge 180^\circ$, then $\{B,D\}$ is not a tasty pair, and if $\angle B+\angle D \ge 180^\circ$, then $\{A,C\}$ is not a tasty pair. Thus, if we draw segments connecting the two points of all tasty pairs, the resulting graph is planar. The following well known lemma finishes the problem. Lemma: A planar graph with $n$ vertices has at most $3n-6$ edges. Proof: Let $E$ and $F$ denote the number of edges and faces in this graph. We double count the number of pairs $(f,e)$ such that edge $e$ is an edge of face $f$. On one hand, each edge is part of exactly $2$ faces, so there are $2E$ pairs. On the other hand, each face has at least $3$ edges, so there are at least $3F$ pairs. Thus, we have $2E \ge 3F$, or $F \le \tfrac{2}{3}E$. By Euler's formula, $n-E+F=2$, so $n-E+\tfrac{2}{3}E \le 2 \Rightarrow E \le 3n-6$.

CyclicISLscelesTrapezoid wrote: My problem! We claim the answer is $3n-6$, achieved by $S=\{(0,1),(0,-1),(1,0),(2,0),\ldots,(n-2,0)\}$. Then, the tasty pairs are of the form $\{(0,1),(i,0)\}$, $\{(0,-1),(i,0)\}$, $\{(i,0),(i+1,0)\}$, or $\{(0,1),(0,-1)\}$. Clearly, if $A$, $B$, and $C$ are collinear in that order, then $\{A,C\}$ cannot be a tasty pair. The main claim is the following. Claim: If $ABCD$ is a convex quadrilateral, then $\{A,C\}$ and $\{B,D\}$ cannot both be tasty pairs. Proof: Since $\angle A+\angle B+\angle C+\angle D=360^\circ$, we must have either $\angle A+\angle C \ge 180^\circ$ or $\angle B+\angle D \ge 180^\circ$. If $\angle A+\angle C \ge 180^\circ$, then $\{B,D\}$ is not a tasty pair, and if $\angle B+\angle D \ge 180^\circ$, then $\{A,C\}$ is not a tasty pair. Thus, if we draw segments connecting the two points of all tasty pairs, the resulting graph is planar. The following well known lemma finishes the problem. Lemma: A planar graph with $n$ vertices has at most $3n-6$ edges. Proof: Let $E$ and $F$ denote the number of edges and faces in this graph. We double count the number of pairs $(f,e)$ such that edge $e$ is an edge of face $f$. On one hand, each edge is part of exactly $2$ faces, so there are $2E$ pairs. On the other hand, each face has at least $3$ edges, so there are at least $3F$ pairs. Thus, we have $2E \ge 3F$, or $F \le \tfrac{2}{3}E$. By Euler's formula, $n-E+F=2$, so $n-E+\tfrac{2}{3}E \le 2 \Rightarrow E \le 3n-6$. What about a regular n-gon ? Because the only tasty pairs are the adjacent vertex so $|S| = n$

$n \le 3n - 6 \iff n \ge 3 \iff n\text{-gon exists}$.

It's interesting to mention that any $n$ points in general position (no 3 collinear and no 4 on a same circle) can be triangulated such that each edge connects a tasty pair. In case the convex hull of the points is a triangle, we get a planar graph with $3n-6$ edges. The needed triangulation is called Delaunay triangulation. The circumcircle of any triangle does not contain any other points except the three vertices of the triangle. Slightly transforming this circle we can get that each segment of the triangle is tasty.