2
$\begingroup$

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.

<span class=P:n=30">

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.

Note: I did ask about this on StackOverflow before, but my question was not answered.

1 Answers 1

2

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.

This is pretty much independent of the particular scheme by which you arranged these points, which is known as the Thomson problem.

(By the way, your statement that the polyhedron is "formed by connecting the vertices to their sphere-distance nearest neighbor vertices" is incorrect: this procedure would only give you a tree, not a polyhedron.)

  • 0
    It turns out that a algorithm to compute the convex full was precisely what I needed. Thank you very much.2012-11-06