The Strange World of the Hausdorff Metric Geometry


XIV. Finite Conversion Algorithm and Configuration Construction Theorem

The 2005 REU group (Chantel Blackburn and Alex Zupan) created the Finite Conversion Algorithm and Configuration Construction Theorem [3]. The Finite Conversion Algorithm shows us how to identify to each infinite configuration X a finite configuration XF with #(XF) = #(X). The Configuration Construction Theorem tells us that we can always construct the finite configuration XF. When we put these together, we learn that we only need study finite configurations to understand the possible number of elements at each location between two sets.


Finite Conversion Algorithm

Let [A, B] be an infinite configuration with #([A, B]) = k for some integer k ≥ 2. Define Ω as before, and let QA = {[a]C : [a]C is in qA(U) for some U in Ω} and

QB = {[b]C : [b]C is in qB(U) for some U in Ω}. It is not difficult to show that |U| is finite for every U in Ω. Thus |QA| and |QB| must be finite. Let l = |QA| and m = |QB|. We can construct a finite configuration XF, consisting of sets Y and Z as follows:


         Step 1: For each [ai]C in QA (where 1 ≤ il), place a point yi in Y. Similarly, for each [bj]C in QB (where 1 ≤ im), place a point zj in Z.

         Step 2: For each [ai]C in QA (where 1 ≤ il), if there exists at least one point c in [ai]C such that c is not in U for any U in Ω, place an endpoint zy,i in Z and make yi in Y adjacent to zy,i.

         Step 3: For each [bj]C in QB (where 1 ≤ im), if there exists at least one point c in [bj]C such that c is not in U for any U in Ω, place an endpoint yz,j in Y and make zj in Z adjacent to yz,j.

         Step 4: For each c in [ai]C, if c is in U for some U in Ω, make yi adjacent to the zj in Z which corresponds to the bj in B such that c is in [bj]C.


As an example of the Finite Conversion Algorithm, consider the infinite configuration X in Figure 9 where A (red) and B (blue) consist of the indicated segments and points and the largest set C (green) between A and B is the collection of green segments and points. We note that #(X) = 9. The collection Ω in this example contains the empty set and the sets

{c1}, {c2}, {c4}, {c5},

{c1, c4}, {c1, c5}, {c2, c4}, {c2, c5}.

Now qA(c1) = [a0]C, qA(c2) = [a1]C, qA(c4) = [a2]C = qA(c5) and qB(c1) = [b1]C = qB(c2), qB(c4) = [b2]C, qB(c5) = [b3]C. Thus,

QA = {[a0]C, [a1]C, [a2]C} and QB = {[b1]C, [b2]C, [b3]C}.


Therefore, in step 1 of the Finite Conversion Algorithm we make y0, y1, and y2 in Y (corresponding to the elements in QA) and z1, z2, and z3 in Z (corresponding to the elements in QB).


Now notice that

[a0]C = {c0, c1}, [a1]C = {c2, c3}, and [a2]C = {c4, c5}.

So in step 2 we create points zy,0 and zy,1 in Z. Similarly, [b1]C = {c1, c2}, [b2]C = {c3, c4}, and [b3]C = {c5, c6} so we create points yz,2 and yz,3 in Y in step 3. Finally, using the adjacencies from steps 3 and 4, we arrive at the configuration XF as illustrated in Figure 10, where #(XF) = 9.



Figure 9: An infinite configuration X with #(X) = 9.



Figure 10: The configuration XF from the Finite Conversion Algorithm.


The Finite Conversion Algorithm gives us an algorithm for constructing finite configurations from infinite ones. However, the algorithm does not demonstrate that we can always construct a finite configuration with the necessary adjacencies. That problem is solved by the Configuration Construction Theorem.


Configuration Construction Theorem

Given natural numbers α and β, we can create a configuration [A, B] so that

         |A| = α

         |B| = β

         Every element in A is adjacent to a specified non-empty subset of elements in B (with every element in B adjacent to at least one element in A).


Finally, the purpose for constructing XF from X is made clear in the following theorem.


Finite Converstion Theorem: Suppose that we convert a configuration X with #(X) finite to a finite configuration XF as described in the Finite Construction Algorithm. Then #(XF) = #(X).


Therefore, when determining for which integers k we can find configurations X so that #(X) = k, it is enough to consider only finite configurations.