Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Why can't you just start from some triangle and add adjacent triangles until you have half of them? You'd just need to make sure that you don't add ones that contain vertices you've already included elsewhere, since that would separate the remaining ones, but it seems that you shouldn't run out of suitable triangles before reaching half? –  joriki Aug 27 '12 at 7:55
    
That algorithm isn't fast, since it requires a lot of back-tracking to correct for poor choices of triangles. Think of something like a near "space-filling" combinatorial disc in a triangulated 2-sphere. –  Ryan Budney Aug 27 '12 at 7:57
2  
I don't understand -- wouldn't such a disk still always allow adding to it some suitable triangles (near the "bends")? Or is the problem that there might be few of these and it might be inefficient to have to find them? But it seems one should be able to keep a list of suitable triangles and keep it up to date in constant time per triangle added, which would lead to linear time overall. (Also it seems it shouldn't be too difficult to avoid such a situation by a judicious choice of triangles to add, e.g. always adding the one closest to a fixed point on the sphere.) –  joriki Aug 27 '12 at 8:11
    
This is basically the problem of planar graph separation, applied to the dual graph. I don't know much about it, but en.wikipedia.org/wiki/Planar_separator_theorem look slike a good starting place. –  David Speyer Aug 27 '12 at 14:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.