I am looking for a data structure to represent non-orientable manifolds (i.e. meshes like Moebius Strip, but without self-intersection). I will then implement other algorithms using this DS such as, but not limited to, Catmull-Clark Subdivision, Offsetting, Minkowski Addition and Minimal Surface. I know that I cannot use Half-Edge Data Structure because it can only be used for orientable manifolds.

I am currently using Winged-Edge Data Structure. This is a very obvious choice, easy to program and reason. I am asking whether there are better, newly invented data structures; or are there any data structures that are better for certain niche use cases (that I might be interested)? I would be more than happy if you could point me some research papers.

Additional Information:

I only need to represent 3-dimentional manifolds.


  • $\begingroup$ Could some please comment whether this question should be migrated to CS Theory Stack Exchange? I personally feel like there must be a data structure better suited for this; but in all resources I found only Half-Edge, Winged-Edge and Quad-Edge Data Structures are listed. All of these are researched in late 20th century. So, should I conclude that Winged-Edge is the state of art data structure for non-orientable manifolds? $\endgroup$
    – user63364
    Commented Dec 19, 2016 at 14:20


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.