Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
If $n$ is much smaller than $N$ and you distribute your $N$ points more or less uniformly on the surface of a sphere, then your question is a variant of the Thomson problem (see en.wikipedia.org/wiki/Thomson_problem). This problem is very hard, and it is only a very special case of your problem. So I think it's probably hopeless to find a nice algorithm that works optimally in every situation. So I think the answers of Weis and O'Rourke (or others like those) are probably as good as you can hope for.
It is not always optimal. Consider the case of trying to choose 3 points from the vertices of a regular hexagon. This algorithm will first remove one point A (any one, by symmetry) and then the point opposite A. It will then remove a third point (again, by symmetry it doesn't matter which) to leave a right triangle. But it's easy to compute that a better solution is the equilateral triangle formed by three mutual non-neighbors.
@Burak: I do not. I will point out that in the non-metrizable setting, there you can find a universal minimal system that is itself a minimal system (any minimal subsystem of $\mathbb{N}^*$ will do). So again the situation is very nice for compact Hausdorff spaces, but I don't know the answer for metric spaces.
I don't know about useful bounds, but in general $p(T)$ will not be a function of $|L(T)|$ alone. To see this, you can find two non-isomorphic trees, each with ten nodes and $|L(T)| = 6$, that have different values for $p(T)$.
@MartinTancer: No worries! I started this whole discussion by missing something much more obvious, so I'll be the last to judge you. Your idea about modifying $K_5$ by throwing in some topologist's sine curves seems like a good one. Unless I'm mistaken, you should be able to use that idea to come up with an infinite collection of complete metric spaces, none of which embeds in another, none of which embeds in $\mathbb{R}^2$, and such that if $X$ is any space embedding in two of them, then $X$ embeds in $\mathbb{R}^2$. This would answer the question negatively. Please do write up an answer!
@MartinTancer: The "ultra" that you're referring to was a typo, and I'm sorry for the confusion. The spaces you're referring to are not ultrametrizable (e.g., because every ultrametrizable space has a basis of clopen sets). I don't read German, but (based on the pictures) the link you shared looks interesting, although I'm not sure it answers my question (because "embeds" and "is a subcomplex of" are very different). By the way, I'll point out that three of the four spaces on my list embed into three triangles that share an edge (all but the sphere).
@Joel: Correct. And using that idea, one can also find infinite decreasing chains. Just use $\Gamma_{A_n}$ where $A_0 \supsetneq A_1 \supsetneq A_2 . . . $.
@Tom: You're right! The sum of $n$ tori (for example) does not embed in the sum of $n+1$ tori (or vice versa). I feel like a bit of an idiot for missing such a natural example. Thanks for the fast response.
