Downloads provided by UsageCounts
AbstractGeometric predicates are at the core of many algorithms, such as the construction of Delaunay triangulations, mesh processing and spatial relation tests. These algorithms have applications in scientific computing, geographic information systems and computer-aided design. With floating-point arithmetic, these geometric predicates can incur round-off errors that may lead to incorrect results and inconsistencies, causing computations to fail. This issue has been addressed using a combination of exact arithmetic for robustness and floating-point filters to mitigate the computational cost of exact computations. The implementation of exact computations and floating-point filters can be a difficult task, and code generation tools have been proposed to address this. We present a new C++ meta-programming framework for the generation of fast, robust predicates for arbitrary geometric predicates based on polynomial expressions. We combine and extend different approaches to filtering, branch reduction, and overflow avoidance that have previously been proposed. We show examples of how this approach produces correct results for data sets that could lead to incorrect predicate results with naive implementations. Our benchmark results demonstrate that our implementation surpasses state-of-the-art implementations.
Roundoff error, floating-point arithmetic, Numerical Analysis (math.NA), Numerical aspects of computer graphics, image analysis, and computational geometry, Computer graphics; computational geometry (digital and algorithmic aspects), computational geometry, FOS: Mathematics, 65G50 (Primary), 68U05 (Secondary), roundoff error, floating-point filter, Mathematics - Numerical Analysis, 000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik
Roundoff error, floating-point arithmetic, Numerical Analysis (math.NA), Numerical aspects of computer graphics, image analysis, and computational geometry, Computer graphics; computational geometry (digital and algorithmic aspects), computational geometry, FOS: Mathematics, 65G50 (Primary), 68U05 (Secondary), roundoff error, floating-point filter, Mathematics - Numerical Analysis, 000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
| views | 52 | |
| downloads | 19 |

Views provided by UsageCounts
Downloads provided by UsageCounts