Polygonal Sequence-driven Triangulation Validator: An Incremental Approach to 2D Triangulation Verification
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916093281435648 |
|---|---|
| author | Sawai, Sora Tanaka, Kazuaki Ozaki, Katsuhisa Oishi, Shin'ichi |
| author_facet | Sawai, Sora Tanaka, Kazuaki Ozaki, Katsuhisa Oishi, Shin'ichi |
| contents | Two-dimensional Delaunay triangulation is a fundamental aspect of computational geometry. This paper presents a novel algorithm that is specifically designed to ensure the correctness of 2D Delaunay triangulation, namely the Polygonal Sequence-driven Triangulation Validator (PSTV). Our research highlights the paramount importance of proper triangulation and the often overlooked, yet profound, impact of rounding errors in numerical computations on the precision of triangulation. The primary objective of the PSTV algorithm is to identify these computational errors and ensure the accuracy of the triangulation output. In addition to validating the correctness of triangulation, this study underscores the significance of the Delaunay property for the quality of finite element methods. Effective strategies are proposed to verify this property for a triangulation and correct it when necessary. While acknowledging the difficulty of rectifying complex triangulation errors such as overlapping triangles, these strategies provide valuable insights on identifying the locations of these errors and remedying them. The unique feature of the PSTV algorithm lies in its adoption of floating-point filters in place of interval arithmetic, striking an effective balance between computational efficiency and precision. This research sets a vital precedent for error reduction and precision enhancement in computational geometry. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_08242 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Polygonal Sequence-driven Triangulation Validator: An Incremental Approach to 2D Triangulation Verification Sawai, Sora Tanaka, Kazuaki Ozaki, Katsuhisa Oishi, Shin'ichi Computational Geometry Numerical Analysis 65D18, 68U05, 65N30, 65G50 Two-dimensional Delaunay triangulation is a fundamental aspect of computational geometry. This paper presents a novel algorithm that is specifically designed to ensure the correctness of 2D Delaunay triangulation, namely the Polygonal Sequence-driven Triangulation Validator (PSTV). Our research highlights the paramount importance of proper triangulation and the often overlooked, yet profound, impact of rounding errors in numerical computations on the precision of triangulation. The primary objective of the PSTV algorithm is to identify these computational errors and ensure the accuracy of the triangulation output. In addition to validating the correctness of triangulation, this study underscores the significance of the Delaunay property for the quality of finite element methods. Effective strategies are proposed to verify this property for a triangulation and correct it when necessary. While acknowledging the difficulty of rectifying complex triangulation errors such as overlapping triangles, these strategies provide valuable insights on identifying the locations of these errors and remedying them. The unique feature of the PSTV algorithm lies in its adoption of floating-point filters in place of interval arithmetic, striking an effective balance between computational efficiency and precision. This research sets a vital precedent for error reduction and precision enhancement in computational geometry. |
| title | Polygonal Sequence-driven Triangulation Validator: An Incremental Approach to 2D Triangulation Verification |
| topic | Computational Geometry Numerical Analysis 65D18, 68U05, 65N30, 65G50 |
| url | https://arxiv.org/abs/2401.08242 |