4
$\begingroup$

Take a triangulation of the 2-sphere, $S^2$. Let the triangulation be denoted $T$. The Euler characteristic tells you that the number of triangles in $T$ is even. Since triangulations of the 2-sphere are shellable, this means you can write $T$ as the union of two triangulated discs along their common boundary, moreover you can ensure the number of triangles in each disc is half the number of triangles in $T$.

Do you know an efficient algorithm to find a partition of $T$ into two discs with equal number of triangles? I imagine there are some fairly efficient algorithms out there, but I'm not sure what to search for in the literature.

I'm particularly interested in partitions into two discs that are somehow optimal. For example, one where the triangulated discs have boundaries with the least number of edges.

edit: Joriki's comment shows the first part of my question has a relatively simple answer. In my words: take a triangulated 2-sphere. Remove a triangle to get a triangulated disc (if you're not using simplicial triangulations this will require a judicious choice). That triangulated disc is shellable, so you can remove one of the triangles that contains a boundary edge (or two) to get a combinatorial disc. etc. By shellability of triangulated discs, this process can be continued until you have a triangulated disc with half the number of triangles.

So the only part of my question remaining is finding ideal such partitions. I suppose the greedy way to attempt to do this would be to prefer to remove triangles with two boundary edges over one. Is that enough to ensure you get a combinatorial disc with the minimum number of boundary edges?

  • 0
    This is basically the problem of planar graph separation, applied to the dual graph. I don't know much about it, but http://en.wikipedia.org/wiki/Planar_separator_theorem look slike a good starting place.2012-08-27

0 Answers 0