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
Liste complète des métadonnées

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00431441
Contributor : Sylvain Lazard <>
Submitted on : Thursday, November 12, 2009 - 11:56:33 AM
Last modification on : Thursday, February 7, 2019 - 5:15:36 PM
Document(s) archivé(s) le : Thursday, June 17, 2010 - 8:09:31 PM

File

CGTA_revised.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Share

Metrics

Record views

320

Files downloads

234