# Dots-and-Polygons

Jessica Dickson<EMAIL_ADDRESS>and  Rachel Perrier<EMAIL_ADDRESS>
###### Abstract.

Dots-and-Boxes is a popular children’s game whose winning strategies have been
studied by Berlekamp, Conway, Guy, and others. In this article we consider two
variations, Dots-and-Triangles and Dots-and-Polygons, both of which utilize
the same lattice game board structure as Dots-and-Boxes. The nature of these
variations along with this lattice structure lends itself to applying Pick’s
theorem to calculate claimed area. Several strategies similar to those studied
in Dots-and-Boxes are used to analyze these new variations.

##  1\. Introduction

Dots-and-Boxes is a children’s game in which dots are set up in a rectangular
grid. Two players take turns drawing horizontal and vertical lines between
these dots. If a player completes a $1\times 1$ box they get to claim this
area by placing their initials inside it or shading it with their color. This
player also gets to draw an extra line after claiming a box. The game ends
once the entire game board is claimed, and the winner is the player who has
claimed the most boxes.

The game of Dots-and-Boxes has been studied extensively by Elwyn Berlekamp,
John Conway, and Richard Guy [3, 4]. In their books on the topic, they reveal
strategies players can employ to give them a better chance to win. One main
strategy is the double-dealing move. In this move, rather than claiming two
boxes, the first player makes a move that allows the second player to claim
both in a single move. While the first player may lose these two boxes, this
double-dealing move also forces the second player to move first in an
unclaimed region of the game board, often with the purpose to open up a longer
chain of boxes for the first player to claim. The move where the second player
claims the two boxes in a single move is called a doublecrossed move. Figure 1
demonstrates these types of moves.

Figure 1. The left picture shows the board on which the players are about to
move. The middle picture shows the first player’s double-dealing move (in red
dashes) while the right picture demonstrates the second player performing a
doublecrossed move and claiming area (using blue dotted lines).

Berlekamp, Conway, and Guy also give other strategies for controlling the form
and final outcome of a game. These strategies rely on the number of dots on
the game board, the number of long chains, and the number of doublecrossed
moves. They also mention a few variations of Dots-and-Boxes, such as playing
on other board shapes and playing a variation called Strings-and-Coins on the
dual of a Dots-and-Boxes game board.

In this paper we explore a new variation of Dots-and-Boxes, one where closing
any polygonal-shaped region allows a player to claim it. In this situation, a
winner could be considered the player who captured the most area on the grid,
similar to the player who claims the most boxes in Dots-and-Boxes. In the
latter game, the unit nature of the boxes allows area to be easily calculated.
The question then becomes, is there a simple way to calculate area in the
former game?

Pick’s Theorem allows easy calculation of the area of a polygon on an integer
lattice, provided that all corner points are integer [5]. Let $B$ be the
number of boundary points, that is, the lattice points that lie on the
boundary of the polygon, and $I$ be the number of interior lattice points of
the polygon. Then, Pick’s Theorem tells us that the area of the closed region
is given by

$I+\frac{B}{2}-1.$

For instance, consider Figure 2. The polygon has $12$ boundary points and $2$
interior points, which makes the area of this polygon $2+\frac{12}{2}-1=7$.
This result can be verified by cutting the polygon up into geometrical shapes
with known area formulas.

Figure 2. Example of a closed region on the integer lattice whose area can be
calculated using Pick’s Theorem.

We will consider two variations of Dots-and-Boxes, both with the goal to claim
the most area. In Dots-and-Triangles players claim area on the lattice game
board by completing triangles with three boundary points and no interior
points. Pick’s theorem tells us that these claimed triangles have area
$\frac{1}{2}$. Since all these triangles have the same area, the player who
claims the most will be the winner. Later, we consider the game Dots-and-
Polygons, where players gain area by closing polygonal regions with no
interior line segments.

##  2\. Dots-and-Triangles

The game of Dots-and-Triangles is played on an finite integer lattice
structure where players alternate turns. We will assume that these games are
always played on finite rectangular lattice structures. The rules are as
follows: (1) Each turn consists of connecting any two distinct points with a
straight line that does not intersect another lattice point nor another line
in the process; (2) if a player closes a triangular region with three boundary
points and without any interior points, that player claims the associated area
and immediately makes another move; (3) two players Robert and Betty play
alternately, with the assumption Robert moves first; (4) the game ends once
all the area on the game board is claimed. For the remainder of this paper, we
will assume that Robert (denoted by $\mathcal{R}$ with the use of red dashed
lines) is always the first to move while Betty (denoted by $\mathcal{B}$ with
blue dotted lines) is second.

Unlike the version in [4] where the triangular cells are predetermined, the
Dots-and-Triangles version we propose is more flexible. Our proposal resembles
a lattice structure version of the Monochromatic Complete Triangulation game
discussed in [1] and the sankaku-tori game discussed in [7]. Our version plays
out differently than these games, though, as neither allows collinear points.
Additionally, sankaku-tori lacks the free turn after the completion of a
triangle. However, like the Monochromatic Complete Triangulation game or
sankaku-tori, different plays on the same game board may result in different
structures, as is demonstrated in Figure 3. Consequently, this rules out a
helpful strategy used in analyzing Dots-and-Boxes—the dual graph, Strings-and-
Coins. Since the dual structure of a Dots-and-Triangles game board is not
evident until players have carved out the triangular cells, an analysis of
this dual nature will not provide much insight until the game is nearly over.

Figure 3. Example of two possible final game board formations for a $3\times
3$ game of Dots-and-Triangles.

###  2.1. Double-Dealings and Doublecrosses

As was mentioned in the introduction, one of the main winning strategies
employed in Dots-and-Boxes is forcing doublecrossed moves. These often occur
at the end of a long chain, a series of three or more boxes than can be
completed in a single turn. Such a strategy allows a player to maintain
control of the game. It is shown in [3, 4] that in the game of Dots-and-Boxes
the number of turns equals the number of starting dots on the game board plus
the number of doublecrosses. This result provides a clear strategy for the
players. The first player wants to make (turns) = (dots) + (doublecrossed
moves) odd; that is, (dots) + (long chains) even. Meanwhile the second player
tries to make (turns) = (dots) + (doublecrossed) moves even; that is, (dots) +
(long chains) odd. It is interesting to note that, despite Dots-and-Triangles
generating twice as many closed shapes as Dots-and-Boxes, the same strategies
still hold.

######  Theorem 2.1.

The number of turns equals the number of dots on the game board plus the
number of doublecrosses.

###### Proof.

This proof is a combination of those from [4, 9] using triangular cells rather
than square ones and relies on a result from graph theory.

First, suppose we are playing a game of Dots-and-Triangles without any
doublecrosses. Let $D$ be the number of dots, $T$ the number of turns to draw
$L$ line segments, and $P$ be the number of triangles we finish the game with.
Now, every line segment that is placed, except the last, either forms exactly
one triangle or ends the turn (but not both). However, the last line segment
placed forms a triangle and marks the end of a turn and thus is counted in
both $P$ and $T$. A $1$ is subtracted to rectify this double counting. This
gives us the formula:

$\displaystyle L$ $\displaystyle=P+T-1.$ (2.1)

But Euler’s formula, which applies to finite, connected, planar graphs without
edge intersections, can also be applied in a modified way to Dots-and-
Triangles. That is, since we have $P+1$ faces in Euler’s formula (rather than
$P$ as we must count the outer face), we have

$\displaystyle D-L+(P+1)$ $\displaystyle=2$

or

$\displaystyle P+D-1$ $\displaystyle=L.$ (2.2)

So in a game without doublecrosses, Equations $2.1$ and $2.2$ give us that the
number of turns equals the number of dots ($D=T$).

Now let’s consider a game with doublecrosses, and let $C$ be the number of
doublecrosses. Each doublecross will create two triangles rather than one so
we can adjust for this double counting by subtracting $C$ from $P$. Altering
Equation $2.1$ accordingly gives

$\displaystyle L$ $\displaystyle=P-C+T-1$ (2.3)

and, using Equation $2.2$, which still holds, combined with Equation $2.3$, we
get

$T=D+C.$

That is, the number of turns equals the number of dots plus the number of
doublecrosses. ∎

###  2.2. Nested Diamonds

For the purposes of this game, a diamond is a quadrilateral whose boundaries
have slopes of $1$ or $-1$. An $n$-nested diamond, is a set of $n$ diamonds
($n\geq 1$) that lie within one another and have no other interior points
between the layers of diamonds, with the exception of the innermost lattice
point. Note that a $1$-nested diamond is just a single diamond with one
interior point. Figure 4 presents an example of a 3-nested diamond.

Figure 4. Example of a 3-nested diamond.

Now let’s examine winning area on an $n$-nested diamond. If Robert is using
the strategy of an ordinary child, as described in [3, 4], he will move in the
innermost nested diamond in order to give up the least area. If Betty were
also playing as an ordinary child, she would then claim all of that area, and
move in the next smallest nested diamond. In this manner, Robert wins if there
is an even number of nested diamonds and Betty wins if there is an odd number.

However, if Betty utilizes a double-dealing strategy, she can always win the
majority of the area of an $n$-nested diamond. Consider the subgame of playing
in the 2-nested diamond shown in Figure 5. In this instance, Betty plays using
a double-dealing strategy. She will not claim the inner area; instead, Betty
will finish off the inner straight line begun by Robert. Then, Robert would
claim the inner region, and be the first to move in the next layer after which
Betty would claim all the area of the second layer. For a $3$-nested diamond,
Betty could double-deal again in the second layer, as illustrated in Figure 6,
and then claim the entirety of the third layer. In fact, if Betty uses this
strategy for any $n$-nested diamond where $n>1$, she will always claim more
area than Robert.

Figure 5. Example of $\mathcal{B}$’s double-dealing strategy.

Figure 6. Example of $\mathcal{B}$ continuing her double-dealing strategy from
Figure 5 in the second layer of a 3-nested diamond.

######  Theorem 2.2.

In an $n$-nested diamond, the second player to move can always win, optimally
claiming an area of $2n^{2}-2n+2$.

###### Proof.

Notice that the nested diamond structure can be broken into four congruent
right triangles, each with two legs of length $n$. So, the total area composed
in this shape is $4(\frac{1}{2}n^{2})=2n^{2}$.

In a $1$-nested diamond, Robert moves first, leaving Betty to win by claiming
all 4 triangles for a total area of $2=2(1^{2})-2(1)+2$. For $n>1$, until the
last layer of the $n$-nested diamond is played in, Betty, using the strategy
described previously, will perform a double-dealing move, forcing Robert to
always move first in any layer. This means Robert will only claim 4 triangles
(or an area of 2) in each layer, excluding the last one where Betty claims all
of the area. Thus Robert claims an area of $2(n-1)$ out of a total area of
$2n^{2}$, giving Betty a total area of $2n^{2}-2(n-1)=2n^{2}-2n+2$. Since
$2n^{2}-2n+2>\frac{1}{2}(2n^{2})=n^{2}$, Betty will win the majority of the
area. ∎

Note that this theorem only decides who wins the majority of the area in the
$n$-nested diamond. On a rectangular grid structure, if an $n$-nested diamond
takes up the entire center of a $(2n+1)\times(2n+1)$ game board (which has
total claimable area $4n^{2}$), then Betty has taken less than half the area
possible. This means that the play that happens in the four corners would
determine the winner of the game.

###  2.3. Reduced and Extremely Reduced Shapes

We use shape as a general term to describe a closed polygon that may have
interior line segments and has not been fully claimed. In a reduced shape, any
two boundary points that can be validly connected via the interior of the
shape would divide it into two subshapes, each with at least one interior
point. That is, in a reduced shape no player can immediately claim area in a
single move. An extremely reduced shape is a reduced shape that cannot be
subdivided in a single move into two reduced shapes. Note that this means the
boundary points of an extremely reduced shape cannot be validly connected in
one move.

######  Theorem 2.3.

Any closed shape with no interior points is not reduced. Moreover, such a
shape can be completely claimed by a player in a single turn.

###### Proof.

We propose an algorithm to show how all area in a closed shape with no
interior points can be claimed by a player in a single turn. Per [5], any
shape can be decomposed into triangles of area $\frac{1}{2}$. Consider any
such decomposition. Figure 7 illustrates a possible decomposition and
demonstrates the following two steps on an example shape.

Step 1: Since the boundary of the shape would need to be included in this
decomposition, begin by locating the triangles that are formed from two
boundary line segments and one interior line segment. Since the boundary line
segments have already been drawn, drawing these interior line segments will
grant a free turn as each will complete a triangle of area $\frac{1}{2}$. If
these moves claim all the area, we have our result. Otherwise, proceed to step
2.

Step 2: We are now left with a subshape with no interior points and a
decomposition originating from the starting decomposition. Perform step 1
again on this subshape.

Since we are considering shapes on a finite board, there are only a finite
number of moves possible. Because of this, the proposed algorithm will
terminate in a finite number of iterations and will result in all area claimed
in a single turn. This also implies that this closed shape was not reduced, as
area was able to be claimed. ∎

Figure 7. Example of the algorithmic approach for Theorem 2.3. The left
picture shows a possible decomposition of an example starting shape into
triangles of area $\frac{1}{2}$. The middle picture shows the area claimed by
a player in step 1. The right picture shows the resulting smaller subshape and
its decomposition to use for step 2.

It is important to note that although the above theorem shows that all area of
a closed shape with no interior points can be claimed in a single turn, it may
not be in a player’s best interest to do so. A doublecross situation may prove
to be more valuable, in a similar manner discussed in the nested diamond
formation.

We can use Theorem 2.3 and the following Lemma 2.4 to make a claim about a
property of extremely reduced shapes. In Theorem 2.5, we refer to linear
points, which are lattice points on the boundary of a polygon that are not
corner points.

######  Lemma 2.4.

If there are $k+1$ lattice points on a line segment, including the lattice
endpoints $(a,b)$ and $(c,d)$, then $k=\gcd(c-a,d-b).$

###### Proof.

Consider a line segment from point $(a,b)$ to $(c,d)$ with $k+1$ lattice
points, including endpoints, and with slope $\frac{r}{s}$ where $\gcd(r,s)=1$.
Using Theorem 3.8 from Apostol in [2], we know there are no integer lattice
points between $(a+(n-1)s,b+(n-1)r)$ and $(a+ns,b+nr)$ for $1\leq n\leq k$.
Thus we can label each point in this manner, specifically $(c,d)$ as
$(a+ks,b+kr)$, and get

$\displaystyle\gcd(c-a,d-b)$ $\displaystyle=\gcd(a+ks-a,b+kr-b)$
$\displaystyle=\gcd(ks,rk)$ $\displaystyle=k.$

Hence, we have our result. ∎

######  Theorem 2.5.

There are no convex extremely reduced shapes without interior line segments
that have five boundary points.

###### Proof.

We establish this proof by contradiction. A convex extremely reduced shape
with exactly five boundary points falls into three cases: three corner points
and two linear points, four corner points and one linear point, or five corner
points. By Theorem 2.3, we know that the shape in question has at least one
interior point.

We will first consider the case with four corner points and one linear point.
Assume that the shape is extremely reduced and thus that any line segment
between any two non-adjacent boundary points would have to cross an interior
lattice point. Since the shape is extremely reduced, we can apply Lemma 2.4 to
two boundary points $(a,b)$ and $(c,d)$. If these points are adjacent, then
$\gcd(c-a,d-b)=1$ and if these points are non-adjacent, then
$\gcd(c-a,d-b)>1$.

Assume without loss of generality that $(0,0),(n,m),\text{ and }(2n,2m)$ are
boundary points, where $\gcd(m,n)=1$, and that the other two boundary points
are $x=(x_{1},x_{2})$ and $y=(y_{1},y_{2})$. (We can always use the rigid
transformations of translation and rotation to move the shape to these
positions.) Note that $(n,m)$ is the linear point, and the rest are corner
points. Further, assume that there are line segments connecting $x$ to
$(0,0)$, $y$ to $(2n,2m)$, and $x$ to $y$. Then, using Lemma 2.4, we have the
requirements:

$\displaystyle\gcd(y_{1}-0,y_{2}-0)$ $\displaystyle=d_{1}>1,$
$\displaystyle\gcd(y_{1}-n,y_{2}-m)$ $\displaystyle=d_{2}>1,$
$\displaystyle\gcd(x_{1}-n,x_{2}-m)$ $\displaystyle=d_{3}>1,$
$\displaystyle\gcd(x_{1}-2n,x_{2}-2m)$ $\displaystyle=d_{4}>1,$
$\displaystyle\gcd(x_{1}-0,x_{2}-0)$ $\displaystyle=1,$
$\displaystyle\gcd(y_{1}-2n,y_{2}-2m)$ $\displaystyle=1,$
$\displaystyle\gcd(x_{1}-y_{1},x_{2}-y_{2})$ $\displaystyle=1.$

Note that $d_{i}$ for $i=1,2,3,4$ above are integers. By Bézout’s identity
(see §1.2 in [8] for details), we can find integers
$a_{i},b_{i},c_{i},e_{i},f_{i},g_{i},h_{i}$, for $i=1,2$, such that

$\displaystyle a_{1}y_{1}+a_{2}y_{2}$ $\displaystyle=d_{1},$ $\displaystyle
b_{1}(y_{1}-n)+b_{2}(y_{2}-m)$ $\displaystyle=d_{2},$ $\displaystyle
c_{1}(x_{1}-n)+c_{2}(x_{2}-m)$ $\displaystyle=d_{3},$ $\displaystyle
e_{1}(x_{1}-2n)+e_{2}(x_{2}-2m)$ $\displaystyle=d_{4},$ $\displaystyle
f_{1}x_{1}+f_{2}x_{2}$ $\displaystyle=1,$ $\displaystyle
g_{1}(y_{1}-2n)+g_{2}(y_{2}-2m)$ $\displaystyle=1,$ $\displaystyle
h_{1}(x_{1}-y_{1})+h_{2}(x_{2}-y_{2})$ $\displaystyle=1.$

Rearranging these equations and putting the coefficients into an augmented
matrix, we obtain

$\left[\begin{matrix}0&0&a_{1}&a_{2}&d_{1}\\\
0&0&b_{1}&b_{2}&b_{1}n+b_{2}m+d_{2}\\\ c_{1}&c_{2}&0&0&c_{1}n+c_{2}m+d_{3}\\\
e_{1}&e_{2}&0&0&2e_{1}n+2e_{2}m+d_{4}\\\ f_{1}&f_{2}&0&0&1\\\
0&0&g_{1}&g_{2}&2g_{1}n+2g_{2}m+1\\\
h_{1}&h_{2}&-h_{1}&-h_{2}&1\end{matrix}\right]$

which row reduces to

$\left[\begin{matrix}1&0&0&0&0\\\ 0&1&0&0&0\\\ 0&0&1&0&0\\\ 0&0&0&1&0\\\
0&0&0&0&1\\\ 0&0&0&0&0\\\ 0&0&0&0&0\end{matrix}\right].$

However, this tells us that the system has no solution, which contradicts our
assumption that our shape is extremely reduced. Thus, this case does not yield
an extremely reduced shape.

The case with five corner points has more variables, as the points can be
labeled as $(0,0),w=(w_{1},w_{2}),x=(x_{1},x_{2}),y=(y_{1},y_{2})$ and
$z=(z_{1},z_{2})$, where the adjacency is given by the ordering. However, by
using Lemma 2.4, it can be shown that the system of equations given by the
Euclidean algorithm is again inconsistent. The logistics are similar to the
first case and are omitted for brevity’s sake.

The final case of three corner points and two collinear points splits into two
subcases dependent on whether those collinear points are adjacent. If they are
adjacent, $(0,0),(n,m),(2n,2m),(3n,3m)$ and $x=(x_{1},x_{2})$ are these
boundary points, where the $\gcd(n,m)=1$ and $x$ is connected to both $(0,0)$
and $(3n,3m)$. A similar process to the previous two cases will show this
subcase is impossible. If the collinear points are not adjacent, label them
$(0,0),(n_{1},n_{2}),(2n_{1},2n_{2}),(m_{1},m_{2}),(2m_{1},2m_{2})$ where
$(n_{1},n_{2})$ and $(m_{1},m_{2})$ are the collinear points and
$\gcd(n_{1},n_{2})=\gcd(m_{1},m_{2})=1$. But then
${\gcd(2m_{1}-2n_{1},2m_{1}-2n_{2})=1}$ which is false, telling us this
subcase is impossible. ∎

This theorem says that a player can always find two boundary points to connect
in a convex shape with five boundary points and no interior line segments.
Generically speaking, a player is often able to claim triangles from the
boundary of a convex shape until it is reduced. Alternatively (or
additionally), if the player cannot gain area, they can split the shape into
two smaller shapes without ceding area to their opponent. Figure 8 gives an
example of claiming triangles to get a reduced shape and splitting the
resulting reduced shape into two extremely reduced subshapes. It is
interesting to note that Theorem 2.5 does not extend to the six boundary point
case, as can be observed in Figure 9 or in [6].

Figure 8. The starting convex shape with no interior line segments is shown on
the left. In the center, triangles have been claimed until the shape is
reduced. On the right, a final move is made to produce two extremely reduced
shapes.

Figure 9. An extremely reduced convex shape with six boundary points.

In the previous few theorems we exclusively considered shapes with no interior
line segments. Let us now switch our focus to what we shall define as an eye,
a closed polygon in which all interior points are path connected, but none of
the interior points are connected to boundary points. We use the term iris to
describe the path connected interior points and line segments. For instance,
in Figure 10 we see two examples of eyes.

Figure 10. Examples of eyes.

Eyes split the game board into subgames on potentially non-rectangular game
boards. Eyes cannot be claimed in a single move, so they are a structure that
could easily pop up during game play. However, sometimes small portions of
eyes can still be claimed by a player before the entire eye is claimed. This
can occur in two ways: using the vertices only from the iris or only from the
boundary. In the former case, once no additional line segments can be added to
connect the vertices of an iris, an iris is considered expanded. If the iris
is expanded and no additional line segments can be added to connect the
boundary vertices we are left with a reduced eye. Note that this definition of
a reduced eye, with an extra requirement of an expanded iris, preserves the
intuitive idea that there is no immediately claimable area in a reduced shape.
An extremely reduced eye has the characteristics of a reduced eye but also the
requirement that the eye cannot be subdivided in a single move. Figure 11
shows the reduced eyes from Figure 10. Close observation of these particular
eyes shows they are not only reduced eyes but extremely reduced eyes, a
property which turns out to be universal.

Figure 11. Claimed area that would result in reduced eyes.

######  Theorem 2.6.

All reduced eyes are extremely reduced eyes.

###### Proof.

Suppose there is a reduced eye that is not extremely reduced. Then there
exists a valid move connecting two boundary points that divides the polygon
into two shapes, both with interior points. But in a reduced eye, such a line
must have passed through the iris, an invalid move. Thus by contradiction
we’ve established the result. ∎

As a result of this theorem, we will often refer to extremely reduced eyes as
just reduced eyes for simplicity. The next theorem shows us why players try to
avoid being the first to move in a reduced eye.

######  Theorem 2.7.

The second player to move in a reduced eye gains its area.

###### Proof.

Since a reduced eye is a closed shape with an expanded iris that is
disconnected from the boundary points, the only valid move for a player to
make is from a point on the boundary of that expanded iris to the boundary of
the eye. The second player can then use that line segment, and the lattice
structure of the game board, to form a claimed triangle. The second player can
use at least one of the edges of this triangle to repeat the process until the
entire eye is claimed. ∎

While the eye structure is fairly straightforward in Dots-and-Triangles, it
provides a greater challenge in the next game we discuss.

##  3\. Dots-and-Polygons

Dots-and-Polygons is a generalized form of Dots-and-Triangles created by
changing the second rule: If a player closes a polygon with no interior lines,
they now claim that area and get an extra move. Note that closing two areas in
the same move still only grants a single extra move. By a polygon, we are
referring to a closed shape without holes whose boundary is formed by line
segments during game play which does not use a vertex or line segment multiple
times in the formation of its boundary. See Figure 12.

Figure 12. The green area in the leftmost region fills a polygon, as defined,
and thus is claimed area. The red areas in the other two figures are not
claimed as neither fill a polygon.

Using Pick’s theorem, area can be easily calculated to find the winner of each
game. Similar to Dots-and-Boxes and the previously discussed Dots-and-
Triangles, a player performs double-dealing moves in order to gain control of
the game. For example, consider the subgame in Figure 13. Robert can claim the
entire triangular region’s area of the left figure in his turn in several ways
but is forced to move first in the next subgame. However, he can perform the
double-dealing move in the right figure instead; Robert would gain no area but
would force Betty to claim the area and move first in the next subgame.

Figure 13. The figure on the left shows the original subgame. The figure on
the right shows $\mathcal{R}$’s double-dealing move.

The situation in Figure 13 can also occur in Dots-and-Triangles, but would not
be an optimal double dealing move in that game (giving up $\frac{3}{2}$ area
rather than 1 area). Thus some doublecross situations in Dots-and-Triangles
carry over to Dots-and-Polygons, but not all of them. For instance, consider
the previously discussed nested diamond double-dealing strategy from Figure 6.
In this figure, a player was able to double-deal in the middle nested diamond
by leaving several triangles unclaimed. In Dots-and-Polygons, the player would
have gained the area of these regions instead, since they are closed polygons
with no line segments lying interior. From these two examples, we can observe
that double-dealing moves are possible in Dots-and-Polygons, but it is a
trickier feat to perform such moves, especially optimally.

###  3.1. Claiming Area

Since Dots-and-Polygons allows larger swaths of area to be claimed,
occasionally lattice points will never have any line segments connected to
them. We adjust our definition of an eye slightly to account for this, with
the modification that the interior points of the eye are either path connected
or interior to a claimed region. See Figure 14.

Figure 14. From left to right, the pictures show examples of an eye, a hanging
eye, and a split hanging eye in Dots-and-Polygons.

In Figure 13, we can see that Robert performed a double-dealing move with the
help of a “hanging” line segment. This motivates several of the following
definitions. A hanging eye has the same criteria as an eye with the relaxation
that, instead of the interior vertices completely separated from the boundary
vertices, the interior (the iris) is connected by one or more line segments to
exactly one boundary vertex. Intuitively, a hanging eye resembles an eye whose
iris has been connected to the boundary at a single vertex, as illustrated in
Figure 14. We also say that an eye is lazy if the iris does not span the
interior vertices of a closed region or include them interior to claimed area.
If an eye has multiple irises spanning the interior vertices that are not
path-connected to one another, we say it is split. These terms can be used in
conjunction with one another to describe shapes such as split hanging eyes as
shown in Figure 14.

While many of the theorems from Dots-and-Triangles will still hold in Dots-
and-Polygons, the new nature of claiming area means each must be examined
carefully. For instance, Theorem 2.7 still holds for Dots-and-Polygons, but we
have to carefully check that the move the first player makes does not form a
valid polygon.

######  Theorem 3.1.

In Dots-and-Polygons, the second player to move in a reduced eye gains its
area.

###### Proof.

This proof follows similarly to Theorem 2.7; we need only check that the move
the first player makes does not form a closed polygon. Such a move forms a
line segment from a point on the boundary of that expanded iris to the
boundary of the eye. This forms a closed region which uses the new line
segment twice as a boundary. Thus this closed region is not a valid polygon,
and the first player does not claim any area, ending their turn. This is
illustrated in Figure 15. The second player can claim the remaining area by
simply making any move connecting a point on the boundary of the expanded iris
to the boundary of the eye to form two valid closed polygons. ∎

Figure 15. The figure on the left shows a reduced eye. The figure on the right
illustrates a move from the boundary of the eye to the boundary of the iris.
The shaded red area marks a region that is not polygonal (and thus not
claimable) as it uses one of its edges twice on the boundary.

While claiming area in an expanded eye is straightforward, it is useful to
note that the process of expanding an eye, and thus also an iris, is a “free
turn” process; that is, if a player notes such a structure exists, they can
quickly check and claim area in it until it is expanded. A player can expand
the boundary of an eye by connecting pairwise combinations of boundary
vertices with valid moves. However, not every pairwise combination of iris
vertices will form a valid polygon, and hence establishing that expanding an
iris is a free turn process needs special consideration. This free turn
process of expanding an eye will also imply that both hanging and split
hanging eyes can be immediately claimed in a single turn.

######  Lemma 3.2.

The process of expanding an iris can always be done is such a way as to not
consume a full turn.

###### Proof.

Start by connecting any vertices that result in claimed area. Such moves will
always result in another free move. Continue this until no such move is
possible. If the iris is expanded, we are done. If it is not expanded it means
there are still two vertices that can be connected to close a region, but that
region is not claimable. If the region is not claimable, then by the rules of
the game, either the closed region is not a polygon or there are interior
lines. We will show by contradiction that neither of these two cases can
occur.

Case 1: First consider the case where the closed region is not a polygon. That
is, suppose we connect two vertices to form a unclaimable closed region
without interior lines. Note that such a region must use a single vertex $i$
twice on its boundary. (A closed region that uses line segments twice on its
boundary can be classified as case 2). We will show there is a region that
should have already been claimed. In the scenario where we use $i$ twice,
consider the vertices near $i$ and on the opposite “side” of the the line
segment that was added to close the region (see Figure 16). Since we are on a
lattice structure and there are no interior vertices or lines in the region we
are guaranteed that there exist two such vertices that can be connected
validly. Connecting these two then forms a polygon with no interior points, a
claimable region that leads to a contradiction as any such area should have
already been claimed.

•••$i$••

Figure 16. A region that is not a polygon, closed by adding the pink line (not
necessarily adjacent to $i$) on the right side. We are considering the
vertices on the left. The shaded yellow region indicates area that should have
already been claimed by placing the yellow line segment.

Case 2: Now consider the case where the closed region has interior lines. Let
$e_{1}$ be the line segment that was added to close this region. By the
definition of an iris, all lines must be path connected (potentially using the
boundary of this new closed region), and it contains no degree 0 vertices.
This means this new closed portion of the iris is itself either a hanging eye
or split hanging eye that spans the interior vertices.

If we have a hanging eye, draw another line $e_{2}$ between the iris and the
border of the closed region. If we have a split hanging eye draw $e_{2}$
between two hanging irises. This splits the region into two parts, one with
both $e_{1}$ and $e_{2}$ on its boundary, and one with just $e_{2}$. This new
region formed with $e_{2}$ is not claimable, as otherwise it would have been
claimed by supposition. Thus, the new region is a (smaller) region to which we
can again apply either case 1 or case 2. Since case 1 has been disproved, we
can repeat the process from case 2. Since we are working on a finite lattice
structure, we know that there are only a finite number of possible moves
available to us in this region. Eventually, drawing a line segment $e_{k}$
would form a triangle or other claimable polygon that did not contain any
other $e_{j}$, for $1\leq j<k$. However, this contradicts the fact we started
by claiming all possible area. Hence, this case also does not hold. ∎

######  Theorem 3.3.

A hanging eye can have its entire area claimed in a single turn.

###### Proof.

We begin by applying Lemma 3.2 to the iris of the hanging eye. The process of
expanding the iris does not consume a full turn nor claim all the area of the
eye. Expanding the iris leaves us with an expanded hanging eye. Due to the
lattice structure and no degree 0 interior points, we can find a move
connecting the expanded iris to the boundary. This divides the hanging eye
into two valid polygons and thus claims the area.

∎

Similarly, we can argue a split hanging eye can also have its entire area
claimed in a single turn. Theorem 3.3 implies that a hanging eye cannot be
reduced by definition. Additionally, even though a player can claim the entire
area of a hanging or split hanging eye, they may want to only claim part of
the area in order to create a doublecrossed move. This theorem cannot,
however, be extended to a lazy hanging or lazy split hanging eye where the
iris(es) do not span all the interior nodes. While a player may still claim
the region in a single turn, this will not always hold, as pictured in Figure
17.

Figure 17. Here the figure is a lazy hanging eye where the iris does not span
all vertices. A player is unable to claim this region in a single turn.

###  3.2. Double-Dealings and Doublecrosses

Now, in Dots-and-Triangles Theorem 2.1 established that the number of turns
equals the number of dots on the game board plus the number of doublecrosses.
However, this is only an upper bound on the number of moves in Dots-and-
Polygons. That is, claiming any closed polygon in Dots-and-Polygons takes at
most the same number of moves as triangulating that same polygon in Dots-and-
Triangles. However, in the next theorem we establish an equality.

######  Theorem 3.4.

The number of turns equals the number of dots on the game board plus the
number of double crosses minus the number of unused interior dots

###### Proof.

First, suppose we are playing a game of Dots-and-Polygons without any
doublecrosses and every claimed polygon has no unused interior points. Let $D$
be the number of dots, $T$ the number of turns to draw $L$ line segments, and
$P$ be the number of polygons we finish the game with. Now, every line segment
that is placed, except the last, either forms exactly one polygon or ends the
turn (but not both). Then the similar result from the Dots-and-Triangles proof
holds, and we get that the number of turns equals the number of dots. If we
allow doublecrosses still without unused interior points, the result still
follows that we have the number of turns equals the number of dots plus the
number of doublecrosses.

Now, consider what happens if there are unused interior points. Let $I$ stand
for the number of these unused interior points, and $C$ be the number of
doublecrosses. So, it still follows that

$L=P-C+T-1.$

Using Euler’s formula where $D-I$ is the number of vertices, $L$ is the number
of edges, and $P+1$ is the number of faces, we get that

$(D-I)-L+(P+1)=2.$

Employing some algebra gives us the result

$T=D+C-I.\qed$

We can assume in Dots-and-Polygons that any doublecrossed move must occur
within a closed region. Imagine Robert performs a double-dealing move, but
leaves an open region after his turn. Betty will perform a doublecrossed move
on her turn, and as a result, will claim the entire region during her turn. If
Betty closes the region, then Robert’s move was not double-dealing as he could
not have claimed the entire area to begin with, although he may have been able
to claim part of it. Alternatively, if Betty does not close the region, then
she did not claim any area, and hence did not make a doublecrossed move.
Therefore, we can assume that all further doublecrossed moves occur inside a
closed region. Similarly, we can use this reasoning to establish the following
theorem.

######  Theorem 3.5.

A player is unable to perform a double-dealing move in a claimable region with
no interior points.

###### Proof.

Suppose that Robert can perform a double-dealing move against Betty in a
claimable region with no interior points. Then the polygon is missing exactly
one line segment on its boundary; otherwise it is not claimable in a single
turn. Robert must still perform a double-dealing move by supposition. However
in this region such a move would complete a valid polygon and claim area,
resulting in an additional turn, which is a contradiction to the double-
dealing strategy. ∎

######  Theorem 3.6.

A player can only be forced to perform a doublecrossed move in a closed region
with a hanging eye or split hanging eyes.

###### Proof.

We will assume that Robert performed the double-dealing move, and Betty is the
player forced into making the doublecrossed move. Proceeding via
contradiction, assume that Betty performs the doublecrossed move in a region
that does not meet the claimed criteria. This yields two cases.

Case 1: Suppose not all the interior vertices are spanned. Then Betty can
simply connect a degree 0 vertex to any other vertex without claiming area as
it is impossible to have a polygon with a degree 1 vertex.

Case 2: Suppose all the interior vertices are spanned but there is at least
one iris that is not hanging. Note that the line segments that form the non-
hanging portion of the irises are disjoint from all other line segments that
form the region. This means if Betty connects a vertex from the non-hanging
iris to any other vertex, she would not claim area as the region formed would
use the new line segment as a boundary twice (and thus would not be a
polygon).

Both these cases contradict Betty being forced to perform the doublecrossed
move. ∎

The previous theorem gives necessary conditions for a doublecrossed move. Note
that this theorem describes not the region in which we doublecross, but the
region we get as a result of the doublecross. However, this theorem does not
stipulate that every closed region with hanging eyes can be used to force a
player into a doublecrossed move, as is demonstrated in Figure 18.

Figure 18. The figure on the left shows the initial region $\mathcal{R}$ can
move in. Although the move shown in the figure on the right creates a hanging
eye, it does not qualify as a double-dealing move as $\mathcal{R}$ could not
have claimed area initially.

We have examined regions in which players can make double-dealing moves, but
what is the smallest area a player would have to give up when making such a
move? Since the goal of a double-dealing move is to give up area to gain more
area in the long run, players might try to strategize their double-dealing
moves to give up as little area as possible.

######  Theorem 3.7.

The minimum amount of area that is needed to perform a double-dealing move is
$\frac{3}{2}$.

###### Proof.

Since we are working on an integer lattice, then the only regions with area
less than $\frac{3}{2}$ we need to consider are $\frac{1}{2}$ and $1$. By
Pick’s theorem both areas would not have any interior points. Suppose a player
makes a double-dealing move in such regions. Since there are no interior
points this means the region is either not closed by the double-dealing move
or it is a closed region that is immediately claimed. The former case is a
contradiction to Theorem 18 while the latter case precludes a double dealing
move, indicating the original move must not have been double-dealing. Hence we
rule out regions with area $\frac{1}{2}$ or $1$.

We will now show that a double-dealing move exists for a shape with an area of
$\frac{3}{2}$. We have two cases to consider by Pick’s Theorem: $I=0$ and
$B=5$, or $I=1$ and $B=3$. In the former case, Theorem 3.5 tell us that a
doublecross cannot occur. This means that we have a triangular region with one
interior point. Consider the region in Figure 13. In this, we can see that a
player can introduce the final boundary line to complete the double-dealing
move. ∎

The previous theorem gives players a goal to strive for when performing
double-dealing moves. Unfortunately, an explicit strategy to ensure optimal
double-dealing moves with minimum amount of ceded area has yet to be
established. Moreover, guaranteeing the existence of a double-dealing move is
also tricky. If we consider Figure 19 we have a split hanging eye, but upon
closer inspection, it is evident there is no way to do a double-dealing move.

Figure 19. A split hanging eye that does not contain a double-dealing move.

##  4\. Conclusion

We have analyzed game play strategies in two proposed variations of the
children’s game Dots-and-Boxes, Dots-and-Triangles and Dots-and-Polygons,
including several winning strategies similar to those in [3, 4]. However,
there are still many future directions to explore. What happens if we play
these games on various surfaces, such as a torus? What strategies guarantee a
player is giving up the minimum amount of area after performing a double-
dealing move? Additionally, Theorem 2.5 showed there are no convex extremely
reduced shapes without interior line segments that have five boundary points.
Can this be extended to the cases with larger odd numbers of boundary points?

## References

  * [1] Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, and Jorge Urrutia, _Games on triangulations_ , Theoretical Computer Science 343 (2005), 42–71.
  * [2] Tom M. Apostol, _Introduction to Analytic Number Theory_ , Springer Science-Busines Media, New York, 1976.
  * [3] Elwyn Berlekamp, _The Dots and Boxes Game: Sophisticated Child’s Play_ , A K Peters, Lrd., Natick, MA, 2000.
  * [4] Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, _Winning Ways for Your Mathematical Plays_ , vol. 2, Academic Press Inc., New York, New York, 1982\.
  * [5] RW Gaskell, MS Klamkin, and P Watson, _Triangulations and Pick’s theorem_ , Mathematics Magazine 49 (1976), no. 1, 35–37.
  * [6] Gerry Myerson (https://mathoverflow.net/users/158000/gerry-myerson), _Property of convex polygons on integer lattice structures_ , MathOverflow (https://mathoverflow.net/q/373673), Accessed Oct. 9, 2020.
  * [7] Takashi Horiyama, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, and Yukiko Yamauchi, _Sankaku-Tori: An Old Western-Japanese Game Played on a Point Set_ , Fun with Algorithms 8496 (2014), 230–239.
  * [8] Gareth A. Jones and Josephine M. Jones, _Elementary Number Theory_ , Springer, London, 1998.
  * [9] Ilan Vardi, _The Mathematical Theory of Dots_ , https://www.oocities.org/cf/ilanpi/math.html, October 2009, Accessed Jul. 1, 2020.


# Distributed boundary tracking using alpha and Delaunay-Čech shapes

Harish Chintakunta
North Carolina State University
<EMAIL_ADDRESS>Hamid Krim
North Carolina State University
<EMAIL_ADDRESS>
###### Abstract

For a given point set $S$ in a plane, we develop a distributed algorithm to
compute the $\alpha-$shape of $S$. $\alpha-$shapes are well known geometric
objects which generalize the idea of a convex hull, and provide a good
definition for the shape of $S$. We assume that the distances between pairs of
points which are closer than a certain distance $r>0$ are provided, and we
show constructively that this information is sufficient to compute the alpha
shapes for a range of parameters, where the range depends on $r$.

Such distributed algorithms are very useful in domains such as sensor
networks, where each point represents a sensing node, the location of which is
not necessarily known.

We also introduce a new geometric object called the Delaunay-Čech shape, which
is geometrically more appropriate than an $\alpha-$shape for some cases, and
show that it is topologically equivalent to $\alpha-$shapes.

##  1 Introduction

Many applications call for detecting and tracking the boundary of a
dynamically changing space of interest [4][3]. We would expect any algorithm
performing the task to include the following important properties: 1) the
boundary output is geometrically close to the actual boundary, and 2) the
interior of the boundary is topologically faithful to the original space. It
is often the case that we are only given random samples from the space. We may
then reconstruct the space by first placing balls of a certain radius around
these points, and then by taking the union of these balls. A good exposition
on relationship amongst the sampling density, the geometry of the underlying
space, and the radius of the balls may be found in [10].

In this paper, we start with the assumption that the union of the balls
described above is a good approximation to the space of interest. Note that in
some cases, this is by design. For example, in the case of systematic failures
in sensor networks [3], the failure in the nodes is caused by a spatially
propagating phenomenon, and our aim is to track its boundary. In this case, we
construct a space by taking the union of balls of radius $r_{c}/2$ around each
node, where $r_{c}$ is its radius of communication. The radius of
communication is the distance within which two nodes can communicate with each
other.

The problem may also be viewed as one of computing the boundary of a set of
points, provided with some geometric information. Given the binary
information, about nodes pair-wise location within a certain distance,
distributive algorithms exist to compute such a boundary [2]. These algorithms
are, unfortunately relatively slow, on account of the need for a global
structure to reach a decision on the membership of a node or of an edge to the
complex boundary. If on the other hand, we are provided with all pair-wise
distances of nodes within a neighborhood, the above decision may be locally
made by constructing an associated $\alpha-$shape.

Given a set of points $S$ in a plane, the $\alpha-$shape introduced in [5]
gives a generalization of the convex hull of $S$, and an intuitive definition
for the shape of points. More importantly, an $\alpha-$shape is the boundary
of an alpha complex, which has the same topology as that of the union of
balls. This relation amongst $\alpha-$shape, alpha complex and the union of
balls is contingent on certain relations between their parameters. We discuss
this in detail in Section 2.1. Such topological guarantees cannot be provided
by the boundary computed in [2].

The Delaunay triangulation gives sufficient information to compute the alpha
complex, and hence its boundary, the $\alpha-$shape. If we only require the
$\alpha-$shape, less information would be necessary. The work in [7] shows
that a global Delaunay triangulation is not necessary, and the alpha shape can
be computed using local Delaunay triangulations. Given the edge lengths of a
geometric graph, [7] constructs the local Delaunay triangulation by first
building local coordinates and then computing the Delaunay triangulation.
Computing the local coordinates, is however not robust and requires a high
density of nodes for accuracy. When given the edge length information, we show
that even local Delaunay triangulation is not necessary.

When there is a sufficient density of nodes, computing local coordinates is
accurate (probabilistically), and distributed algorithms exist for computing
modified versions of Delaunay triangulation [1, 9]. In this case, we define a
certain _Delaunay-Čech triangulation_ , which contains an alpha complex, and
which we show to be homotopy equivalent. For boundary tracking-based
applications, the boundary of Delaunay-Čech triangulation will serve as a
better geometric approximation to the boundary, while preserving the
topological features.

Our contributions in this article are:

  * •

Given the distances between pairs of nodes whenever they are closer than
$r_{c}>0$, we develop an algorithm to compute the $\alpha-$shape for a range
of parameters, where this range depends on $r_{c}$.

  * •

We introduce the Delaunay-Čech triangulation, defined in Section 2.2, and show
that it is homotopy equivalent to the alpha complex.

The remainder of the paper is organized as follows, in Section 2, we provide
some background information, along with a formulation of the problem. We
describe the distributed algorithm for computing an $\alpha-$shape in Section
3. The Delaunay-Čech triangulation and the Delaunay-Čech shape are defined in
Section 2.2, while the proof of its topological equivalence to the alpha
complex is given in Section 4. We conclude in Section 5 with some remarks.

##  2 Preliminaries

###  2.1 Alpha complex and $\alpha-$shape

Consider a set of nodes $V\subset\mathbb{R}^{2}$, and a parameter $r$. Let
$V_{i}$ be the voronoi cell associated with node $v_{i}\in V$ in the voronoi
decomposition of $V$. Define an alpha cell ($\alpha-$cell) of $v_{i}$ as
$\alpha(v_{i},r)=V_{i}\cap B(v_{i},r)$ where $B(v_{i},r/2)$ is the closed ball
of radius $r/2$ around $v_{i}$. The alpha complex, $A_{r}$ (we are assuming
$V$ is implied in this notation), is defined as the nerve complex of the alpha
cells, i.e., $(v_{0},v_{1},\ldots,v_{k})$ spans a $k-$simplex in $A_{r}$ if
$\bigcap_{i}\alpha(v_{i})\neq\varnothing$. Since the alpha cells are convex,
the nerve theorem [11, 8] implies that the alpha complex has the same homotopy
type as the union of the alpha cells, which in turn is equal to the union of
the balls $B(v_{i},r/2)$.

Given a set of nodes $V\subset\mathbb{R}^{2}$ 222The alpha shape is generally
defined for points in $\mathbb{R}^{k}$ for any dimension $k$., and a parameter
$r>0$, the alpha shape, $\partial A_{r}$, is a 1-dimensional complex which
generalizes the convex hull of $V$. To simplify the notation, we use
$(v_{i},v_{j})$ to denote an edge in a graph, a 1-simplex in a complex or the
underlying line segment. A 1-simplex $(v_{i},v_{j})$ belongs to $\partial
A_{r}$ if and only if a circle of radius $r/2$ passing through $v_{i}$ and
$v_{j}$ does not contain any other node inside it. By “inside” a circle, we
mean the interior of the ball to which this circle is a boundary. We say that
such a circle satisfies the “ _$\alpha-$ condition_”. $\partial A_{r}$ also
contains all the nodes $\\{v_{j}\\}$ such that a circle of radius $r$ passing
through $v_{j}$ satisfies the $\alpha-$condition.

For a 2-dimensional simplicial complex $K$, we define the boundary of $K$ to
be the union of all the $1$-simplices (along with their faces), where each is
a face of at most one $2-$simplex, and all $0-$simplices which are not faces
of any simplex in $K$. The alpha shape $\partial A_{r}$ is the boundary of the
alpha complex $A_{r}$[6].

###  2.2 Delaunay-Čech Shape

For a set of nodes $V\subset\mathbb{R}^{2}$ and a parameter $r>0$, define the
geometric graph $G_{r}=(V,E)$ to be the set of vertices $(V)$ and edges $(E)$,
where $e=(v_{i},v_{j})$ is in $E$ if the distance between $v_{i}$ and $v_{j}$
is less than or equal to $r$. Let $\check{C}(V,r)$ denote the Čech complex
with parameter $r$ (the nerve complex of the set of balls
$\\{B(v_{i},r/2)\\}$) and let $DT(V)$ be the Delaunay triangulation of $V$. We
define the Delaunay-Čech complex $D\check{C}_{r}$ with parameter $r$ as
$D\check{C}_{r}=DT(V)\cap\check{C}(V,r)$. We will show in Section 4, that
$D\check{C}_{r}$ is homotopy equivalent to $A_{r}$. We call the boundary of
$D\check{C}_{r}$, denoted by $\partial D\check{C}_{r}$ the Delaunay-Čech
shape.

##  3 Computing the alpha shape of points in $\mathbb{R}^{2}$

In order to compute $\partial A_{r}$, we take each edge in $G_{r}$ and check
if it is in $\partial A_{r}$. If an edge $e=(v_{i},v_{j})$ belongs to
$\partial A_{r}$, then the length of the line segment $(v_{i},v_{j})$ is less
than or equal to $r$. Otherwise, the $\alpha-$condition cannot be satisfied.
Edge $e$ hence also belongs to $G_{r}$, and consequently, checking for all the
edges in $G_{r}$ is sufficient to compute $\partial A_{r}$.

Given an edge $e=(v_{i},v_{j})$, there are two circles of radius $r$ passing
through $v_{i}$ and $v_{j}$. Let us call these circles $\mathcal{C}$ and
$\mathcal{C}^{\prime}$ (see Figure 1). The $\alpha-$ condition is satisfied if
and only if at most one of $\mathcal{C}$ and $\mathcal{C}^{\prime}$ contains
node(s) inside.

We consider all the nodes in $\mathcal{N}_{i}\cap\mathcal{N}_{j}$ (neighbors
common to both $v_{i}$ and $v_{j}$) , and perform a series of tests to verify
their location inside $\mathcal{C}$ and $\mathcal{C}^{\prime}$. It is simple
to see that considering nodes only in $\mathcal{N}_{i}\cap\mathcal{N}_{j}$ is
sufficient. The diameter of both $\mathcal{C}$ and $\mathcal{C}^{\prime}$ is
$r$. If $v_{k}$ lies in one of the circles, the distance between $v_{k}$ and
either of $v_{i}$ and $v_{j}$ is less than $r$, and hence, $v_{k}$ is a
neighbor to both.

We now derive the following:

  1. 1.

A test to see if a node lies in both circles $\mathcal{C}$ and
$\mathcal{C}^{\prime}$. This immediately determines that $e$ does not belong
to $\partial A_{r}$.

  2. 2.

A test to see if a node lies in exactly one of the circles $\mathcal{C}$ and
$\mathcal{C}^{\prime}$.

  3. 3.

Given that there exists at least one node in one of the circles, a test to see
if a subsequent node lies in the other. This also, immediately determines that
$e$ does not belong to $\partial A$.

Let the angle subtended by the chord $v_{i}v_{j}$ on the bigger arc (of either
circle, see Figure 1) be $\theta$, hence making the angle subtended on the
smaller arc $\pi-\theta$. The angle which the chord subtends at the center,
$\omega$, may easily be computed using the law of cosines, and $\theta$ is
equal to $\omega/2$.

Let $v_{k}\in\mathcal{N}_{i}\cap\mathcal{N}_{j}$, and let
$\angle{v_{i}v_{k}v_{j}}=\phi_{k}$. Then, if $\phi_{k}>\pi-\theta$, $v_{k}$
lies inside both circles, and we immediately know that $e$ does not belong to
$\partial A_{r}$. If $\phi\leq\theta$, it lies inside neither circle. Let
$v_{k}$ be the first node satisfying $\theta<\phi\leq\pi-\theta$. Then $v_{k}$
lies in one of the circle. Without loss of generality, we assume $v_{k}$ lies
in $\mathcal{C}$.

Let $v_{l}$ be any subsequent node satisfying $\theta<\phi_{l}\leq\pi-\theta$.
If $v_{l}$ is not a neighbor of $v_{k}$, then $v_{l}$ lies in
$\mathcal{C}^{\prime}$, since any two nodes inside a circle of diameter $r$
will be neighbors. If $v_{k}$ and $v_{l}$ are neighbors, we know the length
$\|(v_{k}v_{l})\|$. Using the law of cosines, we compute the angle
$\angle{v_{k}v_{i}v_{l}}$ which we call $\beta$. If
$\beta=\angle{v_{k}v_{i}v_{j}}+\angle{v_{l}v_{i}v_{j}}$, $v_{l}$ lies in
$\mathcal{C}^{\prime}$, and if
$\beta=|\angle{v_{k}v_{i}v_{j}}-\angle{v_{l}v_{i}v_{j}}|$, $v_{l}$ lies in
$\mathcal{C}$. Figure 1 demonstrates this relationship between the angles.

computing the $\alpha-$shape
---
At each edge $e=(v_{i},v_{j})$ in $G$,
compute $\theta$
for each $v_{k}\in\mathcal{N}_{i}\cap\mathcal{N}_{j}$
compute $\phi_{k}$
if $\phi_{k}>\pi-\theta$
$e\not\in\partial A$, terminate
if $\phi_{k}\leq\theta$,
continue to next node
if $\theta<\phi\leq\pi-\theta$
is $v_{k}$ the first node satisfying this condition?
assign $v_{k}$ to $\mathcal{C}$
else
compute $\beta$
if $\beta=|\angle{v_{k}v_{i}v_{j}}-\angle{v_{l}v_{i}v_{j}}|$
continue to next node
else
$e\not\in\partial A$, terminate
$e\in\partial A$
Table 1: Algorithm for computing the $\alpha-$shape. Note that all the
computations require only local information.

The algorithm terminates when we determine that both circles $\mathcal{C}$ and
$\mathcal{C}^{\prime}$ contain at least one node, or there are no more nodes
in $\mathcal{N}_{i}\cap\mathcal{N}_{j}$ to consider. In the former case, the
edge $e$ does not belong to $\partial A_{r}$ and in the latter, $e$ belongs to
$\partial A_{r}$. Clearly, we can use the same algorithm to compute the
$\alpha-$shape for any parameter $0<q\leq r$. The algorithm is summarized in
Table 1. Figure 2 shows $\partial A_{r}$ for a set of points in
$\mathbb{R}^{2}$ computed using the algorithm in Table 1. The shaded region in
the Figure is the union of balls of radius $r/2$ centered at each point. Note
that the $\alpha-$shape is a boundary of an object which is homotopy
equivalent to the shaded region.

$v_{j}$$v_{i}$$v_{k}$$\theta$$\pi-\theta$$\phi_{k}$$\mathcal{C}^{\prime}$$\mathcal{C}$

$v_{i}$$v_{j}$$v_{k}$$v_{l}$$v_{l}$$\beta$$\beta$

Figure 1: (a)shows the cycles $\mathcal{C}$ and $\mathcal{C}^{\prime}$ which
pass through $v_{i}$ and $v_{j}$. $\phi_{k}$ satisfies
$\theta\leq\phi\leq\pi-\theta$ and $v_{k}$ lies in $\mathcal{C}$. (b)shows the
angle relationships. When $v_{l}$ also lies in $\mathcal{C}$, then
$\beta=|\angle{v_{k}v_{i}v_{j}}-\angle{v_{l}v_{i}v_{j}}|$, and if $v_{l}$ lies
in $\mathcal{C}^{\prime}$,
$\beta=\angle{v_{k}v_{i}v_{j}}+\angle{v_{l}v_{i}v_{j}}$ Figure 2:
$\alpha-$shape with parameter $r_{c}/2$ for a set of points in
$\mathbb{R}^{2}$ computed using algorithm in Table 1. The shaded region is the
union of balls of radius $r_{c}/2$ centered at each point.

##  4 Relation between $D\check{C}_{r}$ and $A_{r}$

Consider the Delaunay-Čech complex $D\check{C}_{r}$ as defined in Section 2.2,
and the $\alpha-$complex $A_{r}$, as defined in Section 2.1. We will show that
$D\check{C}_{r}$ has the same homotopy type as $A_{r}$, by showing that there
exists a bijective pairing between the 1-simplices and 2-simplices in
$D\check{C}_{r}\setminus A_{r}$, such that the pairing describes a homotopy
collapse. Note that both $A_{r}$ and $D\check{C}_{r}$ do not contain any
simplices of dimension greater than 2. Figure 3 shows such a homotopy
collapse.

$e$ Figure 3: Homotopy collapse of an edge into an adjacent 2-simplex

Let $F(G_{r})$ be the flag complex of $G_{r}$. Define the complex $U_{r}$ as
$U_{r}=DT(V)\cap F(G_{r})$. Since the Čech complex $\check{C}(V,r)$ is a
subcomplex of $F(G_{r})$, $D\check{C}_{r}$ is a subcomplex of $U_{r}$.

Let $\mathcal{T}_{e}$ denote the set of all 2-simplices to which $e$ is a face
in $U_{r}$, $\mathcal{T}_{e}^{r_{c}/2}\subseteq\mathcal{T}_{e}$ denote the
2-simplices in $\mathcal{T}_{e}$ with circum-radius less than or equal to
$r/2$, and $\mathcal{T}_{e}^{\pi/2}\subseteq\mathcal{T}_{e}$ denote the
2-simplices in $\mathcal{T}_{e}$ such that the angle opposite $e$ is greater
than $\pi/2$. Figure 4 shows examples of triangles with these properties.

$e$$\tau$$r_{c}/2$ (a) $\tau\in\mathcal{T}_{e}^{r_{c}/2}$

$e$$\tau$$>\pi/2$ (b) $\tau\in\mathcal{T}_{e}^{\pi/2}$

Figure 4: Examples of the triangle sets $\mathcal{T}_{e}^{r_{c}/2}$ and
$\mathcal{T}_{e}^{\pi/2}$. The circles in (a) have are centered at the nodes
with radius $r/2$. Since the circum-radius is less than $r/2$, the circles
have a common intersection with positive area.

In order to show the existence of a paring, we first analyze the triangles
surrounding an edge $e\in A_{r})$. The following lemma characterizes the
2-simplices in $A_{r}$ in terms of their circum-radius.

###### Lemma 4.1

A simplex $(v_{1},v_{2},v_{3})$ in $U_{r}$ is in $A_{r}$ iff the circum-radius
of the triangle $(v_{1},v_{2},v_{3})$ 222we use the notation
$(v_{1},v_{2},v_{3})$ to denote both the simplex and the underlying triangle
is less than or equal to $r/2$.

  * Proof

Since $U_{r}\subseteq DT(V)$, $(v_{1},v_{2},v_{3})\in
U_{r}\Rightarrow(v_{1},v_{2},v_{3})\in DT(V)$. The circumradius is less than
or equal to $r/2$, _iff_ circumcenter belongs to all $\alpha-$cells
$\alpha(v_{1})$, $\alpha(v_{2})$ and $\alpha(v_{3})$. This results in the
three $\alpha-$ cells having a non-empty intersection, hence
$(v_{1},v_{2},v_{3})\in A_{r}$. $\blacksquare$

Lemmas 4.2 and 4.3 together impose conditions on cardinality of the sets
$\mathcal{T}_{e}^{r_{c}/2}$ and $\mathcal{T}_{e}^{\pi/2}$. We utilize these
conditions in Lemma 4.1 to show the existence of the pairing.

###### Lemma 4.2

Denote by $m_{e}$ the midpoint of the 1-simplex $e\in U_{r}$. $m_{e}$ is a
witness for $e$ iff $\mathcal{T}_{e}^{\pi/2}=\varnothing$

  * Proof

$m_{e}$ is a witness for $e$ iff there does not exist any other node inside
the circle with $e$ as the diameter (illustrated in Figure 5(a)). This occurs
if and only if the angle opposite $e$ in any incident triangle is acute.
$\blacksquare$

$>\pi/2$$<\pi/2$$m_{e}$ (a) Construction for Lemma 4.2.

$\phi$$<\pi-\phi$$e$$v$$\tau_{1}$$\tau$ (b) Construction for Lemma 4.4

Figure 5:

###### Lemma 4.3

Consider the following statements

  * •

$S_{1}:$ $\mathcal{T}_{e}^{\pi/2}=\varnothing$

  * •

$S_{2}:$ $\mathcal{T}_{e}^{r/2}\neq\varnothing$

  * •

$S_{3}:$ $e\in A_{r}$

$S_{1}\vee S_{2}$ is a necessary and sufficient condition for $S_{3}$.

  * Proof

Let $e=(v_{1},v_{2})$. For sufficiency: from Lemma 4.2, $S_{1}$ implies
$m_{e}$ is a witness for $v_{1}$ and $v_{2}$, and $S_{2}$ implies $\exists$ a
witness (the circumcenter of one of the triangles in $\mathcal{T}_{e}^{r/2}$).
For necessity: if $S_{3}$ is true, then there exists a witness for $e$. If
$m_{e}$ is a witness, then $S_{1}$ is true. If $m_{e}$ is not a witness, then
$e$ shares a witness with a 2-simplex which is in $A_{r}$. From Lemma 4.1,
this implies $\mathcal{T}_{e}^{r/2}\neq\varnothing$. Therefore, $S_{2}$ is
true. $\blacksquare$

The above Lemma suggests the existence or non-existence of types of triangles
surrounding an edge in $A_{r}$. Lemma 4.4 and Theorem 4.1 further refine this
relationship, and precisely identify the triangle to be removed when an edge
is removed from $D\check{C}_{r}$.

###### Lemma 4.4

If $\mathcal{T}_{e}^{\pi/2}\neq\varnothing$, then
$|\mathcal{T}_{e}^{\pi/2}|=1$.

  * Proof

Suppose $\mathcal{T}_{e}^{\pi/2}\neq\varnothing$. Let
$\tau\in\mathcal{T}_{e}^{\pi/2}$, and let the angle opposite $e$ in $\tau$ be
$\phi$ with $\phi>\pi/2$ (see Figure 5(b)). Let $\tau_{1}\neq\tau$ be incident
on $e$, with $v$ being the opposite vertex. Since $\tau\in U_{r}$, $v$ does
not lie inside the circum-center of $\tau$. This implies that the angle
opposite $e$ in $\tau_{1}$ is less than $\pi-\phi$ which is less than $\pi/2$.
$\blacksquare$

Let $C_{k}(K)$ denote the $k-$simplices in the complex $K$.

###### Theorem 4.1

Let $\mathcal{T}_{R}=C_{2}\left(D\check{C}_{r}\right)\setminus
C_{2}\left(A_{r}\right)$ and
$\mathcal{E}_{R}=C_{1}\left(D\check{C}_{r}\right)\setminus
C_{1}\left(A_{r}\right)$. There exists a bijective pairing
$P:\mathcal{E}_{R}\rightarrow\mathcal{T}_{R}$ such that $e$ is a face of
$P(e)$.

  * Proof

Let $e\in D\check{C}_{r}$ but $e\not\in A_{r}$, from Lemma 4.3,
$\mathcal{T}_{e}^{r_{c}/2}=\varnothing$ and
$\mathcal{T}_{e}^{\pi/2}\neq\varnothing$. Since we assume $e\not\in A_{r}$,
$e$ cannot be a face of any 2-simplex in $A_{r}$. Owing to the condition
$\mathcal{T}_{e}^{r_{c}/2}=\varnothing$, Lemma 4.1 ensures that this is indeed
the case. Also, from Lemma 4.4, $|\mathcal{T}_{e}^{\pi/2}|=1$. Let
$\tau\in\mathcal{T}_{e}^{\pi/2}$. Note that $\tau$ is unique, and $\tau\not\in
A_{r}$. Further, since $\tau$ is an obtuse triangle, $\tau\in\check{C}(V,r)$,
and this implies $\tau\in D\check{C}_{r}$. The pairing $P$ is then defined as
$P(e)=\tau$. $\blacksquare$

For any simplicial complex $K$, let $\sigma_{1}$ and $\sigma_{2}$ be simplices
of dimension $1$ and $2$ such that $\sigma_{1}$ is a face of $\sigma_{2}$.
Then, there exists a deformation retraction $F_{\sigma_{1}}:K\rightarrow
K\setminus(\sigma_{1}\cup Int(\sigma_{2}))$, which “collapses” $\sigma_{1}$
into $\sigma_{2}$. Therefore, $K$ is homotopy equivalent to
$K\setminus(\sigma_{1}\cup Int(\sigma_{2}))$.

The removal of edges $\mathcal{E}_{R}$ and triangles $\mathcal{T}_{R}$
describes a finite sequence of deformation retractions via the pairing $P$.
When we collapse all the edges into their paired triangles, the resulting
complex is $A_{r}$. Each collapse is a homotopy equivalence, and a composition
of homotopy equivalences is a homotopy equivalence. This leads us to our main
theorem:

###### Theorem 4.2

The complexes $D\check{C}_{r}$ and $A_{r}$ are homotopy equivalent.

Figure 6 illustrates the above theorem using an example. Note that $A_{r}$ and
$D\check{C}_{r}$ are homotopy equivalent to each other and both are homotopy
equivalent to $R_{c}$ (the shaded region). Further, as seen, $D\check{C}_{r}$
is a better geometric approximation to $R_{c}$ than $A_{r}$. This is simply
because $A_{r}$ is a sub-complex of $D\check{C}_{r}$.

(a) $A_{r_{c}/2}(V)$ (b) $D\check{C}_{r_{c}/2}(V)$ (c) $A_{r_{c}/2}(V)$ super-
imposed over $D\check{C}_{r_{c}/2}(V)$

Figure 6: Figure shows the homotopy equivalence between $A_{r_{c}/2}(V)$ and
$D\check{C}_{r_{c}/2}(V)$. The shaded region is $R_{c}$. Note that
$D\check{C}_{r_{c}/2}(V)$ is a better geometric approximation to $R_{c}$ than
$A_{r_{c}/2}(V)$.

##  5 Conclusion

The algorithm described in Section 3 takes the edge lengths as inputs and
outputs the alpha shapes. We make no further assumptions on the node density,
and we need not compute any coordinates. The decision about an edge belonging
to an $\alpha-$shape is carried out by only looking at the local information,
i.e., considering only the points within a certain distance, and may therefore
be implemented distributively. In Section 2.2, we define the Delaunay-Čech
complex which contains the alpha complex. Its boundary, defined as a Delaunay-
Čech shape, is therefore a better geometric approximation for the union of
balls with an appropriate radius. We also show in Section 4 that, like the
$\alpha-$shape, the Delaunay-Čech shape remains topologically faithful to the
underlying space.

## References

  * [1] Chen Avin.  Random Geometric Graphs: An Algorithmic Perspective.  PhD thesis, 2006.
  * [2] H. Chintakunta and H. Krim.  Divide and conquer: Localizing coverage holes in sensor networks.  In Sensor Mesh and Ad Hoc Communications and Networks (SECON), 2010 7th Annual IEEE Communications Society Conference on, pages 1 –8, june 2010\.
  * [3] H. Chintakunta and H. Krim.  Detection and tracking of systematic time-evolving failures in sensor networks.  In Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), 2011 4th IEEE International Workshop on, pages 373 –376, dec. 2011\.
  * [4] S. Duttagupta, K. Ramamritham, and P. Kulkarni.  Tracking dynamic boundaries using sensor network.  Parallel and Distributed Systems, IEEE Transactions on, PP(99):1, 2011.
  * [5] H. Edelsbrunner, D. Kirkpatrick, and R. Seidel.  On the shape of a set of points in the plane.  Information Theory, IEEE Transactions on, 29(4):551–559, 1983.
  * [6] H. Edelsbrunner and E.P. Mücke.  Three-dimensional alpha shapes.  ACM Transactions on Graphics (TOG), 13(1):43–72, 1994.
  * [7] M. Fayed and H.T. Mouftah.  Localised alpha-shape computations for boundary recognition in sensor networks.  Ad Hoc Networks, 7(6):1259–1269, 2009.
  * [8] J. Leray.  Sur la forme des espaces topologiques et sur les points fixes des représentations.(french).  J. Math. Pures Appl.(9), 24:95–167, 1945.
  * [9] X.Y. Li, G. Calinescu, P.J. Wan, and Y. Wang.  Localized delaunay triangulation with application in ad hoc wireless networks.  Parallel and Distributed Systems, IEEE Transactions on, 14(10):1035–1047, 2003.
  * [10] Partha Niyogi, Stephen Smale, and Shmuel Weinberger.  Finding the homology of submanifolds with high confidence from random samples.  In Richard Pollack, J nos Pach, and Jacob E. Goodman, editors, Twentieth Anniversary Volume:, pages 1–23. Springer New York, 2009.
  * [11] W.L. Tu and R. Bott.  Differential forms in algebraic topology.  Graduate Texts in Math, Springer Verlag, 1982.


# Counting edges according to edge-type in $t$-ary trees

Helmut Prodinger  Helmut Prodinger
Department of Mathematical Sciences
Stellenbosch University
7602 Stellenbosch, South Africa
and
NITheCS (National Institute for Theoretical and Computational Sciences)
South Africa<EMAIL_ADDRESS>
###### Abstract.

Using the Lagrange inversion formula, $t$-ary trees are enumerated with
respect to edge type (left, middle, right for ternary trees).

###### 2020 Mathematics Subject Classification:

05A15

##  1\. Introduction

The preprint [1] triggered my interest in the sequence A120986 in [5]. It led
to a consideration of $T(n,k)$, the number of ternary trees with $n$ nodes and
$k$ middle edges, see [6].

But we can do better and enumerate such trees with $a_{1}$ left edges, $a_{2}$
middle edges, and $a_{3}$ right edges. Naturally, we must have
$a_{1}+a_{2}+a_{3}=n-1$. And each permutation of
$\\{\textit{left},\textit{middle},\textit{right}\\}$ must lead to the same
count, even if different permutations are applied on various nodes. We explain
everything for ternary trees, but later we will point out how things
generalize to $t$-ary trees. We use, apart from the variable $x$ for the
nodes, $y_{1},y_{2},y_{3}$ for the edge counts; altogether we must look at the
coefficient of $x^{n}y_{1}^{a_{1}}y_{2}^{a_{2}}y_{3}^{a_{3}}$ in a suitable
generating function.

We have

$G=x(1+y_{1}G)(1+y_{2}G)(1+y_{3}G),$

and, more generally

$G=x(1+y_{1}G)\dots(1+y_{t}G).$

This is already suitable for Lagrange inversion:

$[x^{n}]G=\frac{1}{n}[G^{n-1}](1+y_{1}G)^{n}\dots(1+y_{t}G)^{n}.$

Furthermore

$\displaystyle[x^{n}y_{1}^{a_{1}}\dots y_{t}^{a_{t}}]G$
$\displaystyle=\frac{1}{n}[G^{n-1}y_{1}^{a_{1}}\dots
y_{t}^{a_{t}}](1+y_{1}G)^{n}\dots(1+y_{t}G)^{n}$
$\displaystyle=\frac{1}{n}\binom{n}{a_{1}}\dots\binom{n}{a_{t}}.$

##  2\. Wave or particle _aka_ lattice path or tree

Sometimes lattice paths work better than trees, sometimes it is the other way
around. Strehl’s paths [3] seem to work better than Kemp’s trees [2], but the
trees in [4] work better that the paths in [4]. There are many examples, and
the pendulum can go both ways.

One can see from the picture that the trees do sit on different levels, so
counting the middle edges cannot be directly justified by counting the residue
classes $\bmod t$ of the down-steps. However, with our previous argument about
the permutations and the large symmetries, even such an approach is feasible.

left subtreemiddle subtreeright subtree

$\bullet$$\mathscr{T}_{L}$ $\mathscr{T}_{M}$ $\mathscr{T}_{R}$

Figure 1. Ternary tree represented as a lattice path

##  3\. Ordered sequences of $t$-ary trees

We think about $m$ $t$-ary trees, and a giant root (not counted) holding them
together. We assume that $1\leq m<t$ since then we can count the edges from
the giant root to the regular root of each of the $m$ trees. These edges are
labelled by $y_{1},\dots,y_{m}$. Then the Lagrange inversion formula leads to

$\frac{m}{n}\binom{n}{a_{1}-1}\dots\binom{n}{a_{m}-1}\cdot\binom{n}{a_{m+1}}\dots\binom{n}{a_{t}}.$

##  4\. Conclusion

We hope to report on applications soon.

## References

  * [1] A. Burstein.  The Distribution of peak heights modulo $k$ and double descents on $k$-Dyck paths-project.  arXiv:2009.00760  2020\.
  * [2] R. Kemp.  On the number of deepest nodes in ordered trees.  Discrete Math., 81 (1990) 247–258.
  * [3] V. Strehl.  Two short proofs of Kemp’s identity for rooted plane trees.  European J. Combin., 5 (1984) 373–376.
  * [4] N. T. Cameron and J. E. McLeod. Returns and hills on generalized Dyck paths. Journal of Integer Sequences, 19:Article 16.6.1 (28 pages), 2016.
  * [5] The online encyclopedia of integer sequences. http://oeis.org.
  * [6] H. Prodinger. Counting ternary trees according to the number of middle edges and factorizing into $(3/2)$-ary trees. Asian-European Journal of Mathematics, to appear, 2023.
  * [7] H. Prodinger.  Returns, hills, and $t$-ary trees, Journal of Integer sequences 19, Article 16.2.2.  2016\.