On existence of a compatible triangulation with the double circle order type
Hong Duc Bui · 2025
Read On existence of a compatible triangulation with the double circle order type by Hong Duc Bui (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-04602.txt.
Introduction
Hong Duc Bui, writing alone, proves a result in discrete geometry in this 2025 arXiv paper. He studies the double circle order type, a pattern describing how a set of points is arranged. He shows it admits a triangulation that stays compatible with other order types. The match requires the same number of points and the same number of edges on the outer hull. Some wider versions of the pattern work too. The proof settles another special case of a conjecture posed by Aichholzer in 2003.
Catalog record
| CREATOR | Hong Duc Bui |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-04602
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On existence of a compatible triangulation with the double circle order type Hong Duc Bui Abstract We show that the “double circle” order type and some of its generalizations have a compatible triangulation with any other order types with the same number of points and number of edges on convex hull, thus proving another special case of the conjecture in [ 3 ] . 1 Introduction Let P be a set of points on the plane. Following definition in [ 3 ] , we say P is in general position if no three points in P are collinear. For the rest of this article, we implicitly assume point sets are in general position when convenient. We say P is in general + position if P is in general position and no three lines through six distinct points in P are concurrent. Define \operatorname{CH}(P) to be the convex hull of P . We define the concept of order types: Two point sets P and Q are said to have the same order type if there is a bijection f\colon P\to Q such that (p_{i},p_{j},p_{k}) are in counterclockwise order if and only if (f(p_{i}),f(p_{j}),f(p_{k})) are in counterclockwise order. Given a point set P , define an edge of P to be a line segment with two distinct endpoints in P . A triangulation of P is a maximal set of non-intersecting edges of P . Consider two point sets P=\{p_{1},\dots,p_{n}\} and Q=\{q_{1},\dots,q_{n}\} for some positive integer n . Let f\colon P\to Q be a bijection. We say (T_{P},T_{Q}) is a compatible triangulation (or joint triangulation) of (P,Q) with respect to the mapping f if T_{P} is a triangulation of P , T_{Q} is a triangulation of Q , and whenever the edge (p_{i},p_{j}) is in T_{P} , the edge (f(p_{i}),f(p_{j})) is in T_{Q} , and vice versa. In order for a compatible triangulation to exist with respect to some bijection f , it is necessary that |P|=|Q| and \lvert\operatorname{CH}(P)\rvert=\lvert\operatorname{CH}(Q)\rvert . In [ 3 ] , its sufficiency was conjectured. In fact, something stronger was conjectured—even when a bijection of the points on the convex hull are prescribed, it is conjectured that there is still a compatible triangulation as long as the prescribed bijection is a cyclic shift of the convex hulls: Conjecture 1.1 . Let P and Q be two arbitrary point sets such that |P|=|Q| . For any bijection f_{0}\colon\operatorname{CH}(P)\to\operatorname{CH}(Q) preserving the cyclic order of the points on the convex hull, there exists some bijection f\colon P\to Q extending f_{0} such that there exists a compatible triangulation of (P,Q) with respect to f . This conjecture was recently mentioned in [ 20 ] . Formally, “ f_{0} preserves the cyclic order of the points on the convex hull” means the following: for all p_{1},p_{2}\in\operatorname{CH}(P) , edge (p_{1},p_{2}) is in \operatorname{CH}(P) if and only if edge (f_{0}(p_{1}),f_{0}(p_{2})) is in \operatorname{CH}(Q) . (1) For short, we call such a mapping cyclic . For convenience, we say a point set P is universal if for all point sets Q and cyclic mapping f_{0}\colon\operatorname{CH}(P)\to\operatorname{CH}(Q) , the conclusion of 1.1 holds for (P,Q,f_{0}) . For example, it is obvious that: Theorem 1.1 . If P=\operatorname{CH}(P) , then P is universal. This is because any triangulation of P can be transported to a triangulation of Q . In other words, there is only one convex order type for each number of points n . In fact, [ 3 ] proved something stronger: Theorem 1.2 . If |P-\operatorname{CH}(P)|\leq 3 or |P|\leq 8 , then P is universal. The proof of the first statement involves tedious case analysis, and the proof of the second statement involves using computer brute force through all pairs of point sets. Other than the cases mentioned, no general families of point sets are known to be universal. In this article, we prove in Theorem 7.2 that a certain family of point sets is universal, which gives further evidence towards 1.1 . 2 Related Works In this section, we list some works on the topic of compatible triangulation. The problem of compatible triangulation was first considered in [ 3 ] , which states 1.1 and make some progress toward it. [ 8 ] studies this problem further. When the bijection of points is prescribed, [ 22 ] considers the case where the points are inside a rectangle and show that there always exist a compatible triangulation when some additional points, called Steiner points, are added. [ 9 ] gives an O(n^{3}) algorithm that conjecturally determines whether there exists a compatible triangulation with no Steiner points added, and find one if it exists. 3 Notation Term Note \operatorname{CH}(P) convex hull general position see Section 1 general + position see Section 1 order type see Section 1 compatible triangulation see Section 1 universal point set see Section 1 cyclic mapping see Section 1 \mathcal{T}(P,Q) , \mathcal{T}(P,Q,f_{0}) see Section 3 double circle see Definition 3.1 unavoidable spanning cycle see Section 3 generalized double circle see Definition 3.2 Table 1: Some terms defined in this article. If hyperref is enabled, clicking on the links in the table will go directly to the definition. Let P be any point set. We define the double circle as in [ 21 ] . Definition 3.1 (Double circle) . Let P=P_{1}P_{2}\dots P_{n} be a regular polygon with center O . For each 1\leq i\leq n , let point A_{i} be the point along the segment connecting O and the midpoint of segment P_{i}P_{i+1} , and has distance \varepsilon to the segment, where \varepsilon is a sufficiently small positive constant. It can be seen that as \varepsilon\to 0^{+} , the order type changes only finitely many times. Pick \varepsilon in such a way that for all 0<\varepsilon^{\prime}<\varepsilon , the order type would be the same if \varepsilon is replaced with \varepsilon^{\prime} . Then the double circle is the point set \{P_{1},\dots,P_{n},A_{1},\dots,A_{n}\} . Note that if i=n then i+1=n+1 , but the point P_{n+1} doesn’t exist. For convenience, we assume indices wraparound when convenient, so that for example, when i=n then P_{i+1}=P_{1} . Also following [ 21 ] , define an unavoidable spanning cycle as follows. For a point set P with |P|=n , we say P_{1}P_{2}\dots P_{n}P_{1} is an unavoidable spanning cycle of P if P=\{P_{1},\dots,P_{n}\} , and for every 1\leq i\leq n , P_{i}P_{i+1} belongs to every triangulation of P . Note that the natural cycle on the double circle, P_{1}A_{1}P_{2}A_{2}\dots P_{n}A_{n}P_{1} , is an unavoidable spanning cycle. See Figure 1 for an illustration. Figure 1: Illustration for a double circle. Its unavoidable spanning cycle is colored in blue. We generalize Definition 3.1 as follows. This method of generalization from the double circle to the generalized double circle is similar to the generalized double chain defined in [ 10 ] . Also note that the set of vertices of an almost-convex polygon, as defined in [ 17 ] , is a generalized double circle. Definition 3.2 (Generalized double circle) . For some integer n\geq 3 , for positive integers c_{1},c_{2},\dots,c_{n} , define a (c_{1},\dots,c_{n}) -double circle to be a point set P such that: • P has n+\sum_{i=1}^{n}c_{i} points, • \operatorname{CH}(P)=n , • for each 1\leq i\leq n , along each edge P_{i}P_{i+1}