# Classification of, Information Regarding Particular Family of Polyhedra:

Let $n\ge4$. Let $n$ vertices be distributed on a spherical boundary. Let the vertices lie on this boundary as would electrons on a spherical boundary. That is, they are distributed "equally" by electron repulsion.

Let $P$ be the convex polyhedron formed by connecting the vertices to their sphere-distance nearest neighbor vertices. P is an $n$-vertex approximation to a sphere. At $n\to\infty$, P is a sphere.

Below is an example with n = 30. The faces are not drawn, but an edge between every vertex triplet is drawn. This should at least provide some visualization of the shape I am describing.

I am looking for a name and/or information for/regarding this family of polyhedra. Alternatively, any tips with regards to my problem, below, would be appreciated.

Motivation: I am working on a software project in which it has become necessary to quickly graph polyhedra of this type. I am able to generate the vertices, but the only algorithm which I am able to discover to graph these polyhedra takes $O(V^{3})$ time. But, this draws every single face possible between extra triplet of vertices. The majority of these faces are inside of the shape and so are invisible. I expect that if I could learn more about these types of polyhedra that I should be able to realize an algorithm which only draws the outer faces, resulting in a much faster software solution.

-

Given that all your points lie on a sphere, the polyhedron you want should be convex, so you can find it by computing the convex hull of the points. There are efficient $O(n\log n)$ algorithms for doing so, and lots of software available.
I see. I will look into this and report back. Thank you! In response to your by the way: I meant that for each of the n vertices, connect the vertex v to each of k surrounding "closest" vertices with polygons by choosing them at least two at a time. Perhaps there is a better way to say this, but this is not particularly my domain, so if you could point out a more correct way to say this, I would appreciate it.) –  Zéychin Nov 6 '12 at 3:52