A Comment on Pseudo-Triangulation in Three Dimensions

Sariel Har-Peled.

Pseudo-triangulations in two dimensions had attracted
attention in computational geometry in recent years
[cegghss-rspug-94,pv-tsvcpt-96,s-capnc-00,abghz-dfstk-01].
We present one possible extension of this concept to
three dimensions. Our construction has several
desirable properties, among them having the same number
pseudo-triangles, independent of the point
configuration, overall linear complexity, and relatively
simple construction.