Finding points satisfying given constraints on their neighborhoods. Let $x_1,\cdots x_n$ and $y_1,\cdots y_m$ be arbitrary points in $\mathbb{R}^k$. For a given metric $d$ and a given $\epsilon>0$ define: $$A_i\equiv \{\, j \quad |\quad  d(x_i,y_j)<\epsilon\},$$ i.e. the set of labels of the points $y_j$ falling in the neighborhood of $x_i$, for $i=1,\cdots n$.
Clearly the $A_i$ can be determined for any sets of arbitrary points $x_i$ and $y_j$.
My question is about reversing the previous path: given an arbitrary family of subsets of $\{1,\cdots,m\}$, is it always possible to find a suitable metric $d$, a suitable $\epsilon$ and suitable points such that the $A_i$ satisfy the previous definition? 
For example, let $A_1\equiv\{1,2\}$ and $A_2\equiv\{3,4\}$. A solution in $\mathbb{R}$ is given by points $(y_1,y_2,y_3,y_4)\equiv(1,2,3,4)$ and $(x_1,x_2)=(1.5,3.5)$, the usual euclidean metric and any $\epsilon \in (0.5,1.5)$. However, if you add $A_3\equiv\{1,4\}$ and $A_4\equiv\{2,3\}$ there is no solution in $\mathbb{R}$ (but I could still find a solution in $\mathbb{R^2}$ by drawing). So maybe it is enough to raise dimensionality to find a solution?
 A: Let me make some quick observations about the Euclidean plane and the feasible sets of indices (subsets of $\{1,\ldots,m\}$).  The problem is essentially that of Venn diagrams, in which the centers of circles play the role of the $y_j, j=1,..,m$ and points $x_i$ are placed in regions of overlap/nonoverlap of circles according to the desired subset $A_i$.
It is well known (since Venn, 1880) that in the Euclidean plane the maximum number of circles of equal size ($\epsilon$-neighborhoods) that can be arranged to give all possible subsets is three.  Additional circles might be added to such a diagram, but not all possibilities of overlap/nonoverlap will be achieved.
The generalization to $d$-dimensional Euclidean spaces has been considered in the literature.  A result that at most $d+1$ "independent" (hyper)spheres are possible in $d$-dimensional space was reported by Rényi, Rényi, and Surányi (1951), with some corrections to that paper given by Branko Grünbaum (1975).  This latter paper won the MAA Writing Award in 1976 and may be read online, Venn Diagrams and Independent Families of Sets.
It follows that $d = m-1$ is a sufficiently high dimension to allow solutions $x_i, y_j$ for all $n = 2^m$ possible subsets $A_i$ of $\{1,\ldots,m\}$.
