Preprint
English

A provably robust algorithm for triangle-triangle intersections in floating-point arithmetic

Publication date2021
Abstract

Motivated by the unexpected failure of the triangle intersection component of the Projection Algorithm for Nonmatching Grids (PANG), this article provides a robust version with proof of backward stability. The new triangle intersection algorithm ensures consistency and parsimony across three types of calculations. The set of intersections produced by the algorithm, called representations, is shown to match the set of geometric intersections, called models. The article concludes with a comparison between the old and new intersection algorithms for PANG using an example found to reliably generate failures in the former.

Keywords
  • Graph enumeration
  • Computation of transforms
  • Consistency
  • Parsimony
  • Robustness
  • Software reliability
  • Mesh models
Notesubmitted to Transactions on Mathematical Software (TOMS)
Citation (ISO format)
MCCOID, Conor Joseph, GANDER, Martin Jakob. A provably robust algorithm for triangle-triangle intersections in floating-point arithmetic. 2021.
Main files (1)
Preprint
Identifiers
  • PID : unige:152653
243views
333downloads

Technical informations

Creation25/06/2021 15:12:00
First validation25/06/2021 15:12:00
Update time16/03/2023 00:48:39
Status update16/03/2023 00:48:38
Last indexation31/10/2024 22:25:37
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack