The Strange World of the
Hausdorff Metric Geometry
XIII. Finite
Conversion Algorithm and Configuration Construction Theorem
The 2005 REU group 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
and B in a configuration X satisfy the PFAEL conditions, and let
there exist a natural number k ≥
2 such that there are k elements at
each location between A and B.
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 7 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
8, where #(XF) = 9.
Figure 7: An infinite configuration X with #(X) = 9.
Figure 8: 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 X consisting of sets A
and B in Rβ+2 with
·
|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).
·
A and B satisfy the PFAEL
conditions.
Finally, the purpose
for constructing XF from X is made clear in the following
theorem.
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.