If, for instance, I have a central point in a circle and a series of pie slices around it, a list of points on the edge is enough to tell me all of my pie slices. I assume that they loop and that they are in clockwise or counterclockwise order, so I always know which slice is bordered by which other slices.
But if I have a sphere that’s been subdivided into tetrahedral pie slices, is there any similar way that I can list the points in a linear (e.g. an array) or otherwise non-redundant fashion? I can solve the problem by introducing redundant data–having each spoke contain a list of the spokes it shares a tetrahedron with, but ideally I wouldn’t have to deal with all that data.
(Note that I’m not actually dealing with circles and spheres, but rather 2D and 3D delaunay triangulations.)
You can certainly put the slices in a list as you’ve a finite number of them. I’m guessing that you’re asking is there a path which passes through each slice once and only once (with no cheating by traveling along boundaries)?
If so then …
Since each slice defines an area on the surface, there is such a path if there is always a path through any map you can draw on the surface of a sphere. The answer to that question is clearly no as per Euler’s Konigsberg Bridge problem.
Not really. The surface of every circular section is an arc, which makes the problem very simple in two dimensions. As soon as you move up to three you can get arbitrary polygons, and that makes that considerably more complicated.
There may be some simplifications if you require that the partitions of the surface be convex, but I’m not familiar with anything in that area.
I don’t think the Konigsberg problem applies here: There, the objective is to traverse every edge exactly once, while here, the objective is to pass through every vertex exactly once. I’m pretty sure that a path always exists, for the surface of a sphere.
Am I correct in understanding the question to be that of a method of taking in a polyhedron with triangular faces and homeomorphic to a sphere, and list its vertices in some order without repetition in such a way as that the full structure is recoverable from this list alone?
Yes. For instance, like if you knew each new point created a face with the previous two points, or if it alternated between the previous two and the previous two skipping one position each time. Neither of those works to fully fill out a sphere though.
Sounds similar to the Hamiltonian Path which is a path through a graph of vertices. The wikipedia page uses a dodecahedron as an example of a shape over which a ham-path can be made.
It sounds like you’d like to know if a Hamiltonian path can be made from an Icosahedron which is a polyhedron that could resemble a sphere I believe.
If you don’t plan on altering the number of tetrahedral slices that’d give you a constant possible path you could follow each time – if there exists a hamiltonian path for this shape.
If you want to change the number of vertices used from sphere to sphere then you are clearly going to have a new problem each time. But if you keep the same number of vertices then I would imagine that you’d have a way of building it like you say. I’ve actually just finished writing an algorithm that finds a hamilton-path in a given graph of vertices and edges. I don’t have a way to input a icosahedron in it right now though.
hope this helps.
ETA:
According to this (PDF) a hamilton path exists for every solid polyhedron
I don’t know if this fits within your vision of tetrahedron slices or not, but if it does, then your desirata is not always possible. Drive a tetrahedron into the sphere, then drive three more smaller ones into the sphere that lie entirely within the first and do not touch each other. On the surface you now have a “triangle” with three disjoint triangles inside it. Clearly you can get to each of these slices only from the first. So to visit each slice you must visit the first at least twice.