Papers › Polygonal Sequence-driven Triangulation Validator: An Incremental Approach to 2D...
Polygonal Sequence-driven Triangulation Validator: An Incremental Approach to 2D Triangulation Verification
Sora Sawai, Kazuaki Tanaka, Katsuhisa Ozaki, Shin'ichi Oishi
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections