Many questions have been raised about what the odd collection of if-then-elses means for PM1_Check and its counterpart SHARE_PM12_Vertex in Samet 229-230. I hope this manages to help those of you who are having difficulty with his algorithm interpret the psuedocode with greater ease. Read this at your own peril, though.

I have divided it into the 7 cases the code shows, and I try to give an English explanation of what is being done in each, followed by further comments in parentheses.

Remember you start the PM1_Check with a square representing a quadrant and a quadrant’s data dictionary (the q-edges present in the quadrant plus the q-edge you are adding into the quadrant if it intersects this quadrant). What occurs outside this quadrant is not important at this level.

The code uses true to signify that the PM1_check has determined that the quadrant is valid for a PM1. False is used to indicate invalid quadrants (quadrants that must be split).

1) When the quadrant is empty…

THEN: true

(If you have nothing in a quadrant, you don't need to split it.)

else…

2) When the quadrant's data dictionary's first q-edge is an isolated
vertex…

THEN: If it is the only q-edge in the data dictionary
--> true

Else --> false

(If you have an isolated vertex in your data dictionary [stored as
A <-> A for instance] then it must be the only vertex in your dictionary)

else…

3) When there is only one q-edge in the quadrant's data dictionary…

THEN: If both vertices of the q-edge are inside
the quadrant --> false

Else --> true

(If you have a single q-edge, the only problem you face is the case
where the vertices reside in the same quadrant. The other cases [either
no vertices in the quadrant or only one vertex in the quadrant] are fine.)

(Here we have the three basic cases represented. Case A. is when two
vertices of the only q-edge are in the quadrant. This is a failure case.
The other two are where one vertex is in the quadrant (B.) and neither
vertex of the q-edge is in the quadtree (C.).
**A.
B.
C.**

else…

4) When the quadrant's data dictionary's first q-edge has both endpoints
(vertices) inside this quadrant…

THEN: false

(As before, this case is a failure because you can only have vertex
per quadrant. The reason we include this case even though it seems handled
in the prior case is because that was for the situation when there is only
one q-edge in the data dictionary. This covers the cases when there are
more than one q-edges in the data dictionary.)

else…

5) When the quadrant's data dictionary's first q-edge has its vertex
designated P1 in this quadrant...

THEN: Check to see that every other q-edge in the
data dictionary shares vertex designated P1. (by calling Share_PM12...
on the next q-edge in the data dictionary)

else…

6) When the quadrant's data dictionary's first q-edge has its vertex
designated P2 in this quadrant…

THEN: Check to see that every other q-edge in the
data dictionary shares vertex designated P2. (by calling Share_PM12...
on the next q-edge in the data dictionary)

else…

7) When the quadrant's data dictionary's first q-edge has neither vertex
in this quadrant (this is the only possibility left since all the others
have been exhausted)…

THEN: false

(This is always false because if you have a q-edge in a quadrant that
does not have either vertex in the quadrant it must be the only q-edge
present. We would only reach this case if we have more than one q-edge
because of the if statement labelled 3))

The return command is divided as follows into if-then-else cases. When
you move down from 1 - 7, cases in previous lines are no longer possible
(that's why we passed by them). It might seem like a small vertex, but
it is critical to understanding what is happening.

So after case 1) is passed there must be something in the quadrant

After case 2) is passed there is not an isolated vertex in the quadrant

After case 3) is passed there is more than one q-edge in the quadrant’s
data dictionary

After case 4) is passed the first q-edge has less than two vertices
inside this quadrant

After case 5) is passed the "first" vertex of the first q-edge is not
in the quadrant

After case 6) is passed the "second" vertex of the first q-edge is
not in the quadrant

This leads to case 7), which is always invalid (as explained in that
case above)

**Share_PM12_Vertex:**

The purpose of this function is to tell whether or not a vertex in a quadrant is shared by all q-edges in the quadrant’s data dictionary. If it is, then true is returned. If it is not, then false is returned. True and false mean valid and invalid respectively as before.

It might seem odd that in the PM1_Check we only look at the first q-edge of the data dictionary, which seems to be an arbitrarily chosen q-edge. This is because there are only two cases that need to look at all the q-edges. These cases call the Share_PM12_Vertex. When we call Share_PM12_Vertex the situation is as follows:

We know that the first q-edge in this quadrant’s data dictionary has only one of its vertices in this quadrant. In order to be a valid PM1 quadrant, every other q-edge must share that same vertex.

Some specific examples might help in understanding this.

Below CASE I shows a valid quadrant. The q-edge labeled A was the first q-edge in the data dictionary, and its P2 is in the quadrant. As we run Share_PM12_Vertex on every other q-edge in the data dictionary, we see they all have an endpoint at P2 and none of them has another endpoint that is also in the quadrant.

CASE II shows an invalid quadrant. The q-edge labeled B was the first q-edge in the data dictionary, and its P1 is in the quadrant. As we run Share_PM12_Vertex on every other q-edge in the data dictionary, we see that one q-edge (labeled C) does not share this vertex as an endpoint. Therefore we return false and must split the quadrant.

CASE III shows an invalid quadrant. The q-edge labeled D was the first q-edge in the data dictionary, and its P1 is in the quadrant. As we run Share_PM12_Vertex on every other q-edge in the data dictionary, we see that one q-edge (labeled E) shares a vertex, but also has its other endpoint in this quadrant which is a violation of the PM1 quadtree rules. Therefore we return false and must split the quadrant.

**CASE I
CASE II
CASE III**

This function has four cases and takes in not only a quadrant/square and a data dictionary, but the vertex that is supposed to be shared.

1) If there are no more q-edges in the data dictionary…

THEN: true

(if you get this far and there have been no problems, there ain't going
to be any problems)

else...

2) The shared vertex equals the first vertex of the current q-edge
of interest in the data dictionary…

THEN: make sure the second vertex of the current
q-edge is not in the quadrant too, and call Share_PM12... on the same shared
vertex, same square, but the next q-edge of the data dictionary

else...

3) The shared vertex equals the second vertex of the current q-edge
of interest in the data dictionary…

THEN: make sure the first vertex of the current
q-edge is not in the quadrant too, and call Share_PM12... on the same shared
vertex, same square, but the next q-edge of the data dictionary

else...

4) Otherwise…

THEN: false

(This happens when the current q-edge doesn't share one of its vertices
with the passed in vertex. This violates the PM1 quadtree rules).