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 ≤ i
≤ l), place a point yi in Y. Similarly, for each [bj]C in QB
(where 1 ≤ i ≤ m), place a point zj in Z.
·
Step
2: For each [ai]C
in QA (where 1 ≤ i ≤ l), 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 ≤ i ≤ m), 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.