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

Title:
On the Degree of Standard Geometric Predicates for Line Transversals in 3D
Authors:
Everett, Hazel, Lazard, Sylvain, Lenhart, Bill, Zhang, Linqiao
Contributors:
Effective Geometric Algorithms for Surfaces and Visibility (VEGAS), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Computer Science Department [Williamstown MA], Williams College [Williamstown]
Source:
Computational Geometry. 42(5):484-494
Publisher Information:
CCSD; Elsevier, 2009.
Publication Year:
2009
Collection:
collection:CNRS
collection:INRIA
collection:INPL
collection:INRIA-LORRAINE
collection:LORIA2
collection:INRIA-NANCY-GRAND-EST
collection:TESTALAIN1
collection:UNIV-LORRAINE
collection:INRIA2
collection:LORIA
collection:INRIA-300009
collection:INRIA-ETATSUNIS
collection:AM2I-UL
Subject Terms:
ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.2: Nonnumerical Algorithms and Problems, ACM: I.: Computing Methodologies, I.3: COMPUTER GRAPHICS, I.3.7: Three-Dimensional Graphics and Realism, [INFO.INFO-CG]Computer Science [cs], Computational Geometry [cs.CG]
Original Identifier:
HAL:
Document Type:
Zeitschrift article<br />Journal articles
Language:
English
ISSN:
0925-7721
Relation:
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.comgeo.2007.11.002
DOI:
10.1016/j.comgeo.2007.11.002
Access URL:
https://inria.hal.science/inria-00431441
https://inria.hal.science/inria-00431441v1/document
https://inria.hal.science/inria-00431441v1/file/CGTA_revised.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00431441v1
Database:
HAL

Weitere Informationen

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.