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.

$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.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$
    – Zéychin
    Nov 6, 2012 at 3:52
  • $\begingroup$ It turns out that a algorithm to compute the convex full was precisely what I needed. Thank you very much. $\endgroup$
    – Zéychin
    Nov 6, 2012 at 13:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .