Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Shewchuk 97 gives me the orientation of 4 points, by finding the sign of a determinant, where the matrix is composed of the coordinates of the points. So, the signed volume of a tetrahedron, or which side of a plane a point is on, where the plane is defined by the other 3 points.

Bernstein, Fussell 09 (section 3.1) has a predicate which tells me which side of a plane a point is on, where that point is defined implicitly by the intersection of 3 planes. (A product of two determinants, where the matrix is composed of the coefficients of the plane equations of the 4 planes.)

My question: Is it possible to construct a predicate like the Shewchuk orient3d, but expressed in terms of points defined implicitly by planes? So, the orientation of a tet, where the 4 vertices are each defined by 3 arbitrary planes.

I can use an arbitrary precision arithmetic library, but I'm still hopeful it's possible without it, as I'd like to make use of the floating-point expansions and adaptive evaluation from the Shewchuk paper for performance reasons. (It's taken me a year since my last question to stumble upon the idea of representing the point as 3 planes.)

Thanks

share|improve this question
2  
It's not clear to me what criteria you are using to judge a solution (as phrased, there's a vacuous answer of "yes, one can construct such a predicate, if one doesn't worry about efficiency," but that wouldn't be a helpful answer). My impression of Shewchuk's paper is that his techniques are pretty general and can be applied to any of these determinant problems, but fine tuning them seems painful. Incidentally, I'm probably missing some basic idea, but why you are representing points as intersections of planes? And why not just solve for coordinates and apply Shewchuk? (Efficiency?) –  Henry Cohn Jun 18 '12 at 13:08
    
I was interested in the 3-plane representation so I wouldn't have to explicitly compute the points. They result from intersections of lines and planes, I can't compute them accurately enough with floating-point, given the input coordinates are also doubles. –  mr grumpy Jun 18 '12 at 18:28
add comment

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.