{'fraction_non_alphanumeric': 0.03555104113763331, 'fraction_numerical': 0.0045708481462671405, 'mean_word_length': 3.876237623762376, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Topologies of locally minimal planar binary trees

The aim of this article is to obtain an effective restriction on the possible topologies for locally minimal planar binary trees that cover an arbitrary fixed finite set of points Μ in the plane, starting from the geometry of M. This result could turn out to be very useful in improving existing algorithms for searching through these topologies in the construction of a minimal Steiner tree—that is, a network of shortest length that covers the given set. To give a precise statement of the result, we recall a well-known decomposition of finite subsets of the plane into convexity levels [1], [2], as well as an important geometric property of planar trees, namely the twist number as introduced by the authors in earner papers [2]-[S]. Let Μ be any finite non-empty set of points in the plane. By the first convexity level M l of Μ we mean the set of all points of Μ on the boundary of the convex hull of M. We note that M 1 is not empty, and remove M 1 from M. If the set so obtained is not empty, we apply the same procedure to it. The points of Μ on the boundary of the convex hull of Af\M' constitute the second convexity level M 2 of M. We continue in this way until all points of Μ lie on some convexity level. The decomposition Μ = \j^_ i M' is called the decomposition into convexity levels, and the set M' is the ith convexity level of M. If Μ —\J^ =1 M', we say that Μ is k-convex. We note that Μ lies on the boundary of its convex hull if and only if it has just one convexity level, which is of course Μ itself. Further, let Γ be a planar binary tree, that is, a planar tree whose vertices have degrees 1 or 3. Let a and b be any edges in Γ, and y[a,b] the unique path connecting them. On moving from a to b along y[a, b], at every inner vertex we turn to the left or to the right. The difference between the numbers of left and right turns is called the twist number tv/(a,b) of the ordered pair {a,b).