planar embedding (Katrin Dobrindt)

[Javid Huseynov]

This problem can be attempted by finding an embeddable (or realizable)
configuration that is topologically equivalent to the mesh in 3 space.
Namely, you can build a planar configuration that has the same triangle
orientations, or counterclockwise predicates as the one in question.
If you imagine this mesh as a point system and extract consecutive convex
hulls, you may attempt placing those hulls on a Euclidean plane while
checking that all counterclockwise predicates satisfy.

I did this for some systems on up to 30 points. 

Perhaps, "Axioms and Hulls" by Donald Knuth would help. Also, there
is a signficant research done by Goodman and Pollack, Ringel, etc. In
general, Peter Shor has proved that problem of deciding whether or not an
arbitrary point system is embeddable or not is NP-hard. But you may test
the embeddability in polynomial time.

Good luck.

----------------------------------------------------------
Javid Huseynov		* Information and Computer Science
PhD Student		* University of California Irvine
javid at baku.ics.uci.edu  * http://www.ics.uci.edu/~javid
----------------------------------------------------------


On Thu, 16 Dec 1999, autoform wrote:

> 
> Hi,
> 
> Perhaps somebody can help me with the following problem or give me a
> pointer to relevant literature.
> 
> Given:     an arbitrary triangulated mesh in 3-space (with boundaries and
> holes)
> Searched : its embedding in the plane.
> 
> with
> - an easy-to-implement algorithm; its theoretical complexity is not very
> important, since these meshes usually have less than 10,000 triangles.
> 
> by preference
> - ideally, the planar triangles would have a 'similar' shape as their
> corresponding triangles in space,
> - or at least, they should not be too 'bad' for the following
> FE-calculations, i.e. obtuse angles should be avoided etc. 
> 
> If you have any idea, please answer to my 'personal' mail account.
> 
> Thanks,
> 
> Katrin Dobrindt.
> 
> 
> -------------
> The compgeom mailing lists: see
> http://netlib.bell-labs.com/netlib/compgeom/readme.html
> or send mail to compgeom-request at research.bell-labs.com with the line:
> send readme
> Now archived at http://uiuc.edu/~sariel/CG/compgeom/threads.html.
> 



-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/threads.html.