Skip to Main content Skip to Navigation
New interface
Journal articles

On the Degree of Standard Geometric Predicates for Line Transversals in 3D

Hazel Everett 1 Sylvain Lazard 1 Bill Lenhart 2 Linqiao Zhang 1 
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper we study various geometric predicates for determining the existence of and categorizing the configurations of lines in 3D that are transversal to lines or segments. We compute the degrees of standard procedures of evaluating these predicates. The degrees of some of these procedures are surprisingly high (up to 168), which may explain why computing line transversals with finite-precision floating-point arithmetic is prone to error. Our results suggest the need to explore alternatives to the standard methods of computing these quantities.
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Sylvain Lazard Connect in order to contact the contributor
Submitted on : Thursday, November 12, 2009 - 11:56:33 AM
Last modification on : Saturday, November 19, 2022 - 3:58:59 AM
Long-term archiving on: : Thursday, June 17, 2010 - 8:09:31 PM


Files produced by the author(s)



Hazel Everett, Sylvain Lazard, Bill Lenhart, Linqiao Zhang. On the Degree of Standard Geometric Predicates for Line Transversals in 3D. Computational Geometry, 2009, 42 (5), pp.484-494. ⟨10.1016/j.comgeo.2007.11.002⟩. ⟨inria-00431441⟩



Record views


Files downloads