Recognition of Pieces of Arithmetic Hyperplanes Using the Stern-Brocot Tree

The classical problem of discrete structure recognition is revisited in this paper. We focus on pieces of naive lines and, more generally, naive arithmetic hyperplanes, and present a new approach to recognising these discrete structures based on the Stern-Brocot tree. The algorithm for pieces of lines in dimension 2 proposes an alternative method to the state of the art, by proposing an efficient algorithm for any set, not necessarily connected. We also give an adaptation, in the connected case, which achieves linear complexity and keeps an incremental behaviour for the segments. While most of the concepts can be generalised to planes in dimension 3 and hyperplanes in higher dimensions, certain points in the management of the descent in the Stern-Brocot tree merit further study. The proposed algorithm calculates separating chords characterising the membership of planes to cones generated by the branch of the Stern-Brocot tree. This generalisation shows the close link between arithmetic hyperplanes and the generalised Stern-Brocot tree, opens up interesting prospects for recognising pieces of arithmetic hyperplanes but still suffers from certain limitations. However, beyond the recognition problem, which has already been well studied in the field, the main contribution of this article lies in the link it creates between generalisation of the Stern-Brocot tree and the combinatorial structure of arithmetic hyperplanes. Finally, we propose a geometric interpretation of separating chords and an interpretation of plane probing algorithms in the Stern-Brocot tree, showing both the links and the differences with our approach.

J. Math. Imaging Vis., 67(2): 15, 2025.