CAT(0) Geometry, Robots,
and Society

Federico Ardila-Mantilla
1. Moving Objects Optimally
There are many situations in which an object can be moved
using certain prescribed rules, and many reasons—pure
and applied—to solve the following problem.

Problem 1. Move an object optimally from one given position
to another.

Without a good idea, this is usually very hard to do.
When we are in a city we do not know well, trying to

get from one location to another quickly, most of us will
consult a map of the city to plan our route. This simple,
powerful idea is the root of a very useful approach to Prob-
lem 1: We build and understand the “map of possibilities,”
which keeps track of all possible positions of the object; we
call it the configuration space. This idea is pervasive in many

Federico Ardila-Mantilla is a professor of mathematics at San Francisco State
University, and profesor adjunto at Universidad de Los Andes. His email ad-
dress is federico@sfsu.edu.
This work was supported by NSF CAREER grant DMS-0956178, grants DMS-
0801075, DMS-1600609, DMS-1855610, Simons Fellowship 613384, and
NIH grant 5UL1GM118985-03 awarded to SF BUILD.

For permission to reprint this article, please contact:
reprint-permission@ams.org.

DOI: https://doi.org/10.1090/noti2113

fields of mathematics, which call such maps moduli spaces,
parameter spaces, or state complexes.

This article seeks to explain that, for many objects that
move discretely, the resulting “map of possibilities” is a
CAT(0) cubical complex: a space of nonpositive curvature
made of unit cubes. When this is the case, we can use ideas
from geometric group theory and combinatorics to solve
Problem 1.

This approach is applicable to many different settings,
but to keep the discussion concrete, we focus on the follow-
ing specific example. For precise statements, see Section 3
and Theorems 5 and 9.

Figure 1. A pinned down robotic arm of length 6 in a tunnel of
height 2. The figure above shows its configuration space.

Theorem 2 ([3], [4]). The configuration space of a 2-D pinned
down robotic arm in a rectangular tunnel is a CAT(0) cubical
complex. Therefore there is an explicit algorithm to move this
robotic arm optimally from one given position to another.

AUGUST 2020 NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY 977



2. Black Lives Matter
On July 4, 2016, we finished the implementation of our
algorithm to move a discrete robotic arm. Three days later,
seemingly for the first time in history, US police used a
robot to kill an American citizen. Now, whenever I present
this research, I also discuss this action.

The day started with several peaceful Black Lives Matter
protests across the US, condemning the violence dispro-
portionately inflicted on Black communities by the Amer-
ican state. These particular protests were prompted by the
shootings of Alton Sterling and Philando Castile by police
officers in Minnesota and Louisiana.

In Dallas, TX, as the protest was coming to an end, a
sniper opened fire on the crowd, killing five police offi-
cers. Dallas Police initially misidentified a Black man—
the brother of one of the protest organizers—as a suspect.
They posted a photo of him on the internet and asked for
help finding him. Fearing for his life, he turned himself in,
and was quickly found innocent.

A few hours later, police identified US Army veteran
Micah Johnson as the main suspect. After a chase, a stand-
off, and failed negotiations, they used a robot to kill him,
without due process of law.

The organizers of the protest condemned the sniper’s
actions, and police officials believe he acted alone. The ro-
bot that killed Johnson cost about $150,000; police said
that the arm of the robot was damaged, but still functional
after the blast [18]. The innocent man who was misiden-
tified by the police continued to receive death threats for
months afterwards.

Different people will have different opinions about the
actions of the Dallas Police in this tragic event. What is
certainly unhealthy is that the large majority of people I
have spoken to have never heard of this incident.

Our mathematical model of a robotic arm is very simpli-
fied, and probably far from having direct applications, but
the techniques developed here have the potential to make
robotic operations cheaper and more efficient. We tell our-
selves that mathematics and robotics are neutral tools, but
our research is not independent from how it is applied. We
arrive at mathematics and science searching for beauty, un-
derstanding, or applicability. When we discover the power
that they carry, how do we proceed?

Axiom ([6]). Mathematics is a powerful, malleable tool that
can be shaped and used differently by various communities to
serve their needs.

Who currently holds that power? How do we use it?
Who funds it and for what ends? With whom do we share
that power? Which communities benefit from it? Which
are disproportionately harmed by it?

For me these are the hardest questions about this work,
and the most important. The second goal in writing this

article—a central one for me—is to invite myself, and its
readers, to continue to look for answers that make sense
to us.

3. Moving Robots
We consider a discrete 2-D robotic arm 𝑅𝑚,𝑛 of length 𝑛
moving in a rectangular tunnel of height 𝑚. The robot con-
sists of 𝑛 links of unit length, attached sequentially, facing
up, down, or right. Its base is affixed to the lower left cor-
ner of the tunnel, as shown in Figure 1 for 𝑅2,6.

The robotic arm may move freely, as long as it doesn’t
collide with itself, using two kinds of local moves:
• Flipping a corner: Two consecutive links facing different
directions interchange directions.
• Rotating the end: The last link of the robot rotates 90∘
without intersecting itself.
This is an example of a metamorphic robot [1].

Figure 2. The local moves of the robotic arm.

How can we get the robot to navigate this tunnel effi-
ciently?

Figure 3 shows two positions of the robot; suppose we
want to move it from one position to the other. By trial
and error, one will not have too much difficulty in doing
it. It is not at all clear, however, how one might do this in
the most efficient way possible.

Figure 3. Two positions of the robot 𝑅2,6.

4. Maps
To answer this question, let us build the “map of possi-
bilities” of the robot. We begin with a configuration graph,
which has a node for each position of the arm, and an edge
for each local move between two positions. A small piece
of this graph is shown in Figure 4.

As we see in Figure 6, the resulting graph looks a bit
like the map of downtown San Francisco or Bogotá, with
many square blocks lined up neatly. Such a cycle of length
4 arises whenever the robot is in a given position, and there
are two moves A and B that do not interfere with each
other: if we perform move A and then move B, the result
is the same as if we perform move B and then move A; see
for example the 4-cycle of Figure 4. More generally, if the

978 NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY VOLUME 67, NUMBER 7



Figure 4. A part of the graph of possibilities of 𝑅2,6.

robot has 𝑘 moves that can be performed independently
of each other, these moves result in (the skeleton of) a 𝑘-
dimensional cube in the graph.

This brings up an important point: If we wish to move
the robot efficiently, we should let it perform various
moves simultaneously. In the map, this corresponds to
walking across the diagonal of the corresponding cube.
Thus we construct the configuration space of the robot, by
filling in the 𝑘-cube corresponding to any 𝑘 moves that
can be performed simultaneously, as illustrated in Figure
5; compare with Figure 4. The result is a cubical complex, a
space made of cubes that are glued face-to-face.

Figure 5. A part of the configuration space of 𝑅2,6.

Definition 3. The configuration space 𝒞(𝑅) of the robotic
arm 𝑅 is the cubical complex with:
• a vertex for each position of the robot,
• an edge for each local move between two positions,
• a 𝑘-dimensional cube for each 𝑘-tuple of local moves that

may be performed simultaneously.

Figure 6. The configuration space of the robotic arm 𝑅2,6.

This definition applies much more generally to discrete
situations that change according to local moves; see Sec-
tion 9 and [1], [11].

In our specific example, Figure 6 shows the configura-
tion space of the robot 𝑅2,6 of length 6 in a tunnel of height
2. It is now clear how to move between two positions effi-
ciently: follow the shortest path between them in the map!

5. What Are We Optimizing?
Is it so clear, just looking at a map, what the optimal path
will be? It depends on what we are trying to optimize. In
San Francisco, with its beautifully steep hills, the best route
between two points can be very different depending on
whether one is driving, biking, walking, or taking public
transportation. The same is true for the motion of a robot.

For the configuration spaces we are studying, there are
at least three reasonable metrics: ℓ1,ℓ2, and ℓ∞. In these
metrics, the distance between points 𝑥 and 𝑦 in the same
𝑑-cube, say [0,1]𝑑, is

√
∑

1≤𝑖≤𝑑
(𝑥𝑖 − 𝑦𝑖)2, ∑

1≤𝑖≤𝑑
|𝑥𝑖 − 𝑦𝑖|, max1≤𝑖≤𝑑 |𝑥𝑖 − 𝑦𝑖|,

respectively. Figure 7 shows the two positions of the robot
of Figure 3 in the configuration space, and shortest paths
or geodesics between them according to these metrics.

Figure 7. Some paths between two points in the configuration
space 𝒞(𝑅2,6). The black path is geodesic in the ℓ1 metric, the
magenta path is geodesic in ℓ1 and ℓ∞, and the cyan path is
geodesic in ℓ1,ℓ2, and ℓ∞.

If each individual move has a “cost” of 1, then perform-
ing 𝑑 simultaneous moves—which corresponds to cross-
ing a 𝑑-cube—costs √𝑑, 𝑑, and 1 in the metrics ℓ2, ℓ1, and
ℓ∞. Although the Euclidean metric is the most familiar, it
seems unrealistic in this application; why should two si-
multaneous moves cost √2? For the applications we have
in mind, the ℓ1 and ℓ∞ metrics are reasonable models for
the cost and the time of motion:
Cost (ℓ1): We perform one move at a time; there is no cost
benefit to making moves simultaneously.
Time (ℓ∞): We may perform several moves at a time, caus-
ing no extra delay.

These two metrics, studied in [3], [4], will be the ones
that concern us in this paper. The Euclidean metric, which
is useful in other contexts and significantly harder to ana-
lyze, is studied in [5], [13].

AUGUST 2020 NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY 979



6. Morning Routine
I write this while on sabbatical in a foreign city. Being the
coffee enthusiast that I am, I carefully study a map several
mornings in a row, struggling to find the best cafe on my
way from home to my office. One morning, amused, my
partner May-Li stops me on the way out: “Fede, you know
you don’t always have to take a geodesic, right?”

Perhaps, instead of the most efficient paths, we should
be looking for the most pleasant, or the greenest, or the
most surprising, or the most beautiful.

7. CAT(0) Cubical Complexes
Our two most relevant algorithmic results are the explicit
construction of cheapest (ℓ1) and fastest (ℓ∞) paths in the
configuration space of the robot arm 𝑅𝑚,𝑛. Still, the Eu-
clidean metric (ℓ2) turns out to play a very important role
as well. Most configuration spaces that interest us exhibit
nonpositive curvature with respect to the Euclidean metric,
and this fact is central in our construction of shortest paths
in the cost and time metrics.

Let us consider a geodesic metric space (𝑋,𝑑), where any
two points 𝑥 and 𝑦 can be joined by a unique shortest path
of length 𝑑(𝑥,𝑦); such a path is known as a geodesic. Let
𝑇 be a triangle in 𝑋 whose sides are geodesics of lengths
𝑎,𝑏,𝑐, and let 𝑇′ be the triangle with the same side lengths
in the plane. For any geodesic chord of length 𝑑 connect-
ing two points on the boundary of 𝑇, there is a compari-
son chord between the corresponding two points on the
boundary of 𝑇′, say of length 𝑑′. If 𝑑 ≤ 𝑑′ for any such
chord in 𝑇, we say that triangle 𝑇 is at least as thin as a
Euclidean triangle.

a
b

c

d

a b

c

d

X R2

Figure 8. A chord in a triangle in 𝑋, and the corresponding
chord in the comparison triangle in ℝ2. The triangle in 𝑋 is at
least as thin as a Euclidean triangle if 𝑑 ≤ 𝑑′ for all such
chords.

Definition 4. A metric space 𝑋 is CAT(0) if:
• between any two points there is a unique geodesic, and
• every triangle is at least as thin as a Euclidean triangle.

A (finite) cubical complex is a connected space obtained
by gluing finitely many cubes of various dimensions along
their faces. We regard it as a metric space with the Eu-
clidean metric on each cube; all cubes necessarily have the
same side length. Cubical complexes are flat inside each
cube, but they can have curvature where cubes are glued
together, for example, by attaching three or five squares
around a common vertex (obtaining positive and negative

curvature, respectively), as shown in Figure 9. We invite
the reader to check that the triangles in the left and right
panels of Figure 9 are thinner and not thinner than a Eu-
clidean triangle, respectively.

Figure 9. A CAT(0) and a non-CAT(0) cubical complex.

We have the following general theorem.

Theorem 5 ([1], [3], [5], [13], [14]). Given two points 𝑥 and
𝑦 in a CAT(0) cubical complex, there are algorithms to find a
geodesic from 𝑥 to 𝑦 in the Euclidean (ℓ2), cost (ℓ1), and time
(ℓ∞) metrics.

Thus a robot with a CAT(0) configuration space is easier
to control: we have a procedure that automatically moves
it optimally. We will see that this is the case for the robotic
arm 𝑅𝑚,𝑛.

8. How Do We Proceed?
Once I began to feel that this work, which started out in
“pure” mathematics, could actually have real-life applica-
tions, I started getting anxious and selective about who I
discussed it with. It is a strange feeling, to discover some-
thing you really like, and yet to hope that not too many
people find out about it. When I was invited to write this
article, I felt conflicted. I knew I did not want to only dis-
cuss the mathematics, but I am much less comfortable writ-
ing outside of the shared imaginary world of mathemati-
cians, where we believe we know right from wrong. Still,
I know it is important to listen, learn, discuss, and even
write from this place of discomfort.

How should I tell this story? Should I do it at all? I have
turned to many friends, colleagues, and students for their
wisdom and advice.

Mario Sanchez, who thinks deeply and critically about
the culture of mathematics and philosophy in our soci-
ety, is wary of mathematical fashions: What if it becomes
trendy for mathematicians to start working on optimizing
robots, but not to think about what is being optimized, or
whom that optimization benefits? He tells me, with his
quiet intensity: “If you’re worried that your paper might
have this effect, you should probably emphasize the hu-
man question pretty strongly.”

Laura Escobar just returned from a yoga retreat in
Champaign-Urbana where a scholar of Indian literature

980 NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY VOLUME 67, NUMBER 7



taught them the story of Arjuna, a young warrior about
to enter a rightful battle against members of his own fam-
ily. Deeply conflicted about the great violence that will
ensue, he turns to Krishna for advice. Oversimplifying
his reply, Krishna says: “One should not abandon duties
born of one’s nature, even if one sees defects in them. It
is your duty as a warrior to uphold the Dharma, take ac-
tion, and fight.” With her usual thoughtful laugh, Laura
tells me about the distressed reactions of her peace-loving
yoga classmates. Laura and I grew up in the middle of
Colombia’s sixty-year-old civil war, which has killed more
than 215,000 civilians and 45,000 combatants and has dis-
placed more than 15% of the country’s population [9],
[10]; it is hard for us to understand Krishna’s advice as
well.1 So we go to the bookstore and buy matching copies
of the Bhagavad Gita.

Many of my friends who do not work in science are sur-
prised by the lack of structural and institutional resources.
They ask me: If a mathematician or a scientist is trying
to understand or have some control over the societal im-
pact of their knowledge and their expertise, what organi-
zations can they turn to for support? I have been pos-
ing this question to many people. I have not found such
an organization, but I am collecting resources. Interdis-
ciplinary organizations such as the Union of Concerned
Scientists, Science for the People, Data for Black Lives, and
sections of the American Association for the Advancement
of Science seek to use science to improve people’s lives
and advance social justice. Our colleagues in departments
of science, technology, and society, public policy, history,
philosophy, and ethnic studies have been studying these
issues for decades, even centuries. This has often taken
place too far from science departments, and it must be said
that my generation of scientists largely looked down on
these disciplines as unrigorous, uninteresting, or unimpor-
tant. Governments, companies, and professional organi-
zations assemble ethics committees, usually separate from
their main operations, and give them little to no decision-
making power.

How do we make these considerations an integral part
of the practice and application of science? I am encour-
aged to see that the new generation of scientists under-
stands their urgent role in society much more clearly than
we do.

May-Li Khoe, whom I can always trust to be wise and
direct, asks me: “If you tell me that this model of mapping
possibilities could be applicable in many areas, and you
don’t trust the organizations that build the most powerful
robots, why don’t you find other applications?” She’s right.
I’m looking.

1We later learn that Robert Oppenheimer quoted Krishna when he and his team
detonated the first nuclear bomb.

9. Examples
Just like any other cultural practice, mathematics respects
none of the artificial boundaries that we sometimes draw,
in an attempt to understand it and control it. This is ev-
ident for CAT(0) cubical complexes, a family of objects
which appears in many seemingly disparate parts of (math-
ematical) nature. Let us discuss three sources of examples;
each one raises different kinds of questions and offers valu-
able tools that have directly shaped this investigation.
Geometric group theory. This project was born in geo-
metric group theory, which studies groups by analyzing
how they act on geometric spaces. Gromov’s pioneering
work in this field [12] led to the systematic study of CAT(0)
cubical complexes. A concrete source of examples is due
to Davis [8].

A right-angled Coxeter group 𝑋(𝐺) is given by generators
of order 2 and some commuting relations between them;
we encode the generators and commuting pairs in a graph
𝐺. For example, the graph of Figure 10(a) encodes the
group generated by 𝑎,𝑏,𝑐,𝑑 with relations 𝑎2 = 𝑏2 = 𝑐2 =
𝑑2 = 1, 𝑎𝑏 = 𝑏𝑎,𝑎𝑐 = 𝑐𝑎,𝑏𝑐 = 𝑐𝑏,𝑐𝑑 = 𝑑𝑐.

The Cayley graph has a vertex for each element of 𝑋(𝐺)
and an edge between 𝑔 and 𝑔𝑠 for each group element 𝑔 and
generator 𝑠. This graph is the skeleton of a CAT(0) cube
complex that 𝐺 acts on, called the Davis complex 𝒮(𝐺). It is
illustrated in Figure 10(b). One can then use the geometry
of 𝒮(𝐺) to derive algebraic properties of 𝑋(𝐺). For example,
one can easily solve the word problem for this group: given
a word in the generators, determine whether it equals the
identity. This problem is undecidable for general groups.

b 1 d

bc c cd

abc ac

ab a ad

dadda

cda

b

dc
a

Figure 10. (a) A graph 𝐺 determining a right-angled Coxeter
group 𝑋(𝐺), and (b) part of its Davis complex 𝒮(𝐺).

Phylogenetic trees. A central problem in phylogenetics is
the following: given 𝑛 species, determine the most likely
evolutionary tree that led to them. There are many ways
of measuring how different two species are,2 but if we are
given the (𝑛

2
) pairwise distances between the species, how

do we construct the tree that most closely fits that data?
Billera, Holmes, and Vogtmann [7] approached this

problem by constructing the space of all possibilities: the
space of trees 𝒯𝑛. Remarkably, they proved that the space
of trees 𝒯𝑛 is a CAT(0) cube complex. In particular, since
it has unique geodesics, we can measure the distance

2We should approach them thoughtfully and critically; see Section 10.

AUGUST 2020 NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY 981



Figure 11. Ernst Haeckel’s tree of life (1866).

between two trees, or find the average tree between them.
This can be very helpful in applications: if ten different al-
gorithms propose ten different phylogenetic trees, we can
detect which proposed trees are close to each other, detect
outlier proposals that seem unlikely, or find the average
between different proposals. Owen and Provan showed
how to do this in polynomial time [15].

A B C D

A B C D

A B C D

A B C DA B C D

Figure 12. Five of the fifteen squares in the space of trees 𝒯4.

These results made us wonder whether one can simi-
larly construct ℓ2-optimal paths in any CAT(0) cube com-
plex. New complications arise, but it is possible [5], [13].
Discrete systems: Reconfiguration. Abrams, Ghrist, and
Peterson introduced reconfigurable systems in [1], [11].
This very general framework models discrete objects that
change according to local moves, keeping track of which
pairs of moves can be carried out simultaneously. Exam-
ples include discrete metamorphic robots moving around
a space, particles moving around a graph without collid-
ing, domino tilings of a region changing by flips ,
and reduced words in the symmetric group changing by
commutation moves 𝑠𝑖𝑠𝑗 ↔ 𝑠𝑗𝑠𝑖 for |𝑖 − 𝑗| ≥ 2 and braid
moves 𝑠𝑖𝑠𝑖+1𝑠𝑖 ↔ 𝑠𝑖+1𝑠𝑖𝑠𝑖+1.

Definition 3 associates a configuration space to any re-
configurable system. Such a configuration space is always
locally CAT(0). It is often globally CAT(0), and when that
happens Theorem 5 applies, allowing us to move our ob-
jects optimally.

10. Why Do We Map?
Math historian Michael Barany points out to me that,
struck by the aesthetic beauty of the tree of life shown
in Figure 11, I failed to notice another map that Haeckel
drew: a hierarchical tree of nine human groups—which
he regarded as different species—showing their supposed
evolutionary distance from the ape-man. Modern biology
shows this has no scientific validity, and furthermore, that
there is no genetic basis for the concept of race. Haeckel’s
work is just one sample of the deep historical ties between
phylogenetics and scientific racism, and between mapmak-
ing and domination.

If we map from a different—an other—point of
view [...] then mapping becomes a process of get-
ting to know, connect, bring closer together in re-
lation, remember, and interpret.

—Sandra Alvarez [2]

11. Characterizations
How does one determine whether a given space is CAT(0)?
We surely do not want to follow Definition 4 and check
whether every triangle is at least as thin as a Euclidean tri-
angle; this is not easy to do, even for an example as small
as Figure 9. Fortunately, this becomes much easier when
the space in question is a cubical complex. In this case,
Gromov showed that the CAT(0) property—a subtle met-
ric condition—can be rephrased entirely in terms of topol-
ogy and combinatorics; no measuring is necessary!

To state this, we recall two definitions. A space 𝑋 is sim-
ply connected if there is a path between any two points, and
every loop can be contracted to a point. If 𝑣 is a vertex of
a cubical complex 𝑋, then the link of 𝑣 in 𝑋 is the simpli-
cial complex one obtains by intersecting 𝑋 with a small

982 NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY VOLUME 67, NUMBER 7



sphere centered at 𝑣. A simplicial complex Δ is flag if it has
no empty simplices: if 𝐴 is a set of vertices and every pair
of vertices in 𝐴 is connected by an edge in Δ, then 𝐴 is a
simplex in Δ.

Theorem 6 ([12]). A cubical complex 𝑋 is CAT(0) if and only
if:
• 𝑋 is simply connected, and
• the link of every vertex in 𝑋 is flag.

In fact, one can also do without the topology: there is an
entirely combinatorial characterization of CAT(0) cubical
complexes. This is originally due to Sageev and Roller, and
we rediscovered it in [5] in a different formulation that is
more convenient for our purposes. Let a pointed cubical
complex be a cubical complex with a distinguished vertex.

Definition 7 ([5], [19]). A poset with inconsistent pairs
(PIP) (𝑃,≤,↮) is a poset (𝑃,≤) together with a collection of
inconsistent pairs, denoted 𝑝 ↮ 𝑞 for 𝑝 ≠ 𝑞 ∈ 𝑃, that is
closed under ≤; that is, if 𝑝 ↮ 𝑞 and 𝑝 ≤ 𝑝′, 𝑞 ≤ 𝑞′, then
𝑝′ ↮ 𝑞′.

PIPs are also known as prime event structures in the com-
puter science literature [19]. The Hasse diagram of a PIP
(𝑃,≤,↮) shows graphically the minimal relations that de-
fine it. It has a dot for each element of 𝑃, a solid line
from 𝑝 upward to 𝑞 whenever 𝑝 < 𝑞 and there is no 𝑟 with
𝑝 < 𝑞 < 𝑟, and a dotted line between 𝑝 and 𝑞 whenever
𝑝 ↮ 𝑞 and there are no 𝑟 ≤ 𝑝 and 𝑠 ≤ 𝑞 such that 𝑟 ↮ 𝑠.

A B 

D

FE

C

Figure 13. The Hasse diagram of a PIP: solid lines represent
the poset, and dotted lines represent the (minimal)
inconsistent pairs. Notice that 𝐶 ↮ 𝐹 implies 𝐸 ↮ 𝐹.

Theorem 8 ([5],[16], [17]). Pointed CAT(0) cube complexes
are in bijection with posets with inconsistent pairs (PIPs).

This rediscovery was motivated by the observation that
CAT(0) cubical complexes look very much like distribu-
tive lattices. In fact, Theorem 8 is an analog of Birkhoff’s
representation theorem, which gives a bijection between

distributive lattices and posets. The proof is subtle and re-
lies heavily on Sageev’s work [17], but the bijection is easy
and useful to describe.
Pointed CAT(0) cubical complex ↦ PIP. Let (𝑋,𝑣) be a
CAT(0) cubical complex 𝑋 rooted at vertex 𝑣. Every 𝑑-cube
in 𝑋 has 𝑑 hyperplanes that bisect its edges. Whenever two
cubes share an edge, let us glue the two hyperplanes bisect-
ing it. The result is a system of hyperplanes associated to 𝑋
[17]. Figure 14 shows an example.

The PIP corresponding to (𝑋,𝑣) keeps track of how one
can navigate 𝑋 starting from 𝑣. The elements of the cor-
responding PIP are the hyperplanes. We declare 𝐻 < 𝐼 if,
starting from 𝑣, one must cross 𝐻 before crossing 𝐼. We
declare 𝐻 ↮ 𝐼 if, starting from 𝑣, one cannot cross both 𝐻
and 𝐼 without backtracking. Remarkably, the simple com-
binatorial information stored in this PIP is enough to re-
cover the pointed space (𝑋,𝑣).

A

B D
F

E

C

v

Figure 14. A rooted CAT(0) cubical complex with six
hyperplanes. Its PIP is shown in Figure 13.

PIP ⟼ rooted CAT(0) cubical complex. Let 𝑃 be a PIP.
An order ideal of 𝑃 is a subset 𝐼 closed under <; that is, if
𝑥 < 𝑦 and 𝑦 ∈ 𝐼, then 𝑥 ∈ 𝐼. We say that 𝐼 is consistent if it
contains no inconsistent pair.

The vertices of the corresponding CAT(0) cubical com-
plex 𝑋(𝑃) correspond to the consistent order ideals of 𝑃.
Two vertices are connected if their ideals differ by a single
element. Then we fill in all cubes whose edges are in this
graph. The root is the vertex corresponding to the empty
order ideal.

We invite the reader to verify that the PIP of Figure 13
corresponds to the rooted complex of Figure 14.

Theorem 8 provides a completely combinatorial way
of proving that a cubical complex is CAT(0): one simply
needs to identify the corresponding PIP!

AUGUST 2020 NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY 983



12. Remote Controls and Geodesics
Intuitively, we think of the PIP 𝑃 as a “remote control”
to help an imaginary particle navigate the corresponding
CAT(0) cubical complex 𝑋. If the particle is at a vertex of 𝑋,
there is a corresponding consistent order ideal 𝐼 of 𝑃. The
hyperplanes that the particle can cross are the maximal el-
ements of 𝐼 and the minimal elements of 𝑃 − 𝐼 consistent
with 𝐼. We can then press the 𝑖th “button” of 𝑃 if we want
the point to cross hyperplane 𝑖.

This point of view is powerful because in practical
applications, the configuration space 𝑋 is usually very
large, high dimensional, and combinatorially compli-
cated, whereas the remote control 𝑃 is much smaller and
can be constructed in some cases of interest.

Theorem 5 provides algorithms to move optimally be-
tween any two points in a CAT(0) cubical complex in the
ℓ1,ℓ2, and ℓ∞ metrics. We sketch the proof in the cases
that are relevant here: in the ℓ1 and ℓ∞ metrics, where the
two points 𝑣 and 𝑤 are vertices.

Sketch of Proof of Theorem 5. To move from 𝑣 to 𝑤, let us
root the cube complex 𝑋 at 𝑣, and let 𝑃 be the correspond-
ing PIP. Then 𝑤 corresponds to an order ideal 𝐼 of 𝑃; these
are the hyperplanes we need to cross.
Cost (ℓ1) Metric: We simply cross the hyperplanes from 𝑣 to
𝑤 in nondecreasing order, with respect to the poset 𝐼 ⊆ 𝑃:
we first cross a minimal element 𝑚1 ∈ 𝐼, then a minimal
element 𝑚2 ∈ 𝐼 − 𝑚1, and so on.
Time (ℓ∞) Metric: We first cross all minimal hyperplanes
𝑀1 in 𝐼 simultaneously, then we cross all the minimal hy-
perplanes 𝑀2 in 𝐼 − 𝑀1 simultaneously, and so on. This
corresponds to Niblo and Reeves’s normal cube path [14],
where we cross the best available cube at each stage. □

These algorithms show how to move a CAT(0) robot
optimally and automatically.

13. Automation
Driving in San Francisco, I get stuck behind a terrible driver.
They are going extremely slowly, hesitating at every corner,
stalling at every speed bump. When I finally lose patience
and decide to pass them, they swerve wildly towards me; I
react quickly to avoid being hit. I turn to give the driver a
nasty look, but I find there isn’t one.

What happens if you are injured by an automated, self-
driving vehicle or robot designed by well-meaning scien-
tists and technologists? When you live this close to Silicon
Valley, the question is not just philosophical.

14. Prototype: A Robotic Arm in a Tunnel
If we wish to apply Theorem 5 to move an object optimally,
our first hope is that the corresponding map of possibili-
ties is a CAT(0) cubical complex. If this is true, we can
prove it by choosing a convenient root and identifying the

corresponding PIP. Tia Baker and Rika Yatchak pioneered
this approach in their master’s theses [3].

For concreteness, let us consider our robotic arm of
length 𝑛 in a rectangular tunnel of height 1. Baker and
Yatchak found that the number of states of the configura-
tion space is the term 𝐹𝑛+1 of the Fibonacci sequence. This
seemed like good news, until we realized that these num-
bers grow exponentially! The dimension of the map is 𝑛/3,
and its combinatorial structure is enormous and intricate.
We cannot navigate this map by brute force.

Fortunately, by running the bijection of Theorem 8 on
enough examples, Baker and Yatchak discovered that this
robot has a very nice PIP: a triangular wedge 𝑇𝑛 of a square
grid with no inconsistent pairs, as shown in Figure 15. It is
much simpler than the configuration space and only has
about 𝑛2/4 vertices. Indeed they proved that the map of
possibilities of the robot 𝑅1,𝑛 is isomorphic to the cubical
complex 𝑋(𝑇𝑛) corresponding to 𝑇𝑛. This implies that the
map is CAT(0), and it allows us to use 𝑇𝑛 as a remote con-
trol to move the robot optimally.

Figure 15. The map of the robot 𝑅1,7 and its remote control,
the PIP 𝑇7.

More generally, we have the following.

Theorem 9 ([3], [4]). The configuration space of the robotic
arm 𝑅𝑚,𝑛 of length 𝑛 in a tunnel of height 𝑚 is a CAT(0)
cubical complex. Therefore, we have an algorithm to move the
arm optimally from any position to any other.

Naturally, as the height grows, the map becomes in-
creasingly complex. After staring at many examples, get-
ting stuck, and finally receiving a conclusive hint from
the Pacific Ocean—a piece of coral with a fractal-like
structure—we were able to describe the PIP of the robot
𝑅𝑚,𝑛 for any 𝑚 and 𝑛. It is made of triangular flaps like the
one in Figure 16 recursively branching out in numerous
directions.

This coral PIP serves as a witness that the map of possibil-
ities of the robotic arm 𝑅𝑚,𝑛 is a CAT(0) cubical complex.
It can also be programmed to serve as a remote control, to
help the arm explore the tunnel.

984 NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY VOLUME 67, NUMBER 7



Figure 16. The coral PIPs of the robot 𝑅2,9, which contains the
PIPs of 𝑅2,1,…,𝑅2,8, shown in different colors.

15. Implementation
The algorithms to navigate a CAT(0) space optimally, and
hence move a CAT(0) robot, are described in [3]. We
have implemented them in Python for the robotic arm
in a tunnel [4]. Given two states, the program outputs
the distance between the two states in terms of cost (ℓ1)
and time (ℓ∞), and an animation moving the robot opti-
mally between the two states. The downloadable code, in-
structions, and a sample animation are at math.sfsu.edu
/federico/robots.html.

With the goal to broaden access to these tools, I joined
my collaborator César Ceballos, who led a week-long
workshop for young robotics enthusiasts as part of the
Clubes de Ciencia de Colombia. This program invites
Colombian researchers to design scientific activities for
groups of students from public high schools and univer-
sities across the country.

We proposed some discrete models of robotic arms, and
our students successfully built their maps of possibilities.
Extremely politely, they also pointed out that César and I
really didn’t know much about the mechanics of robots,
and cleverly proposed several possible mechanisms. After
the workshop, Arlys Asprilla implemented the design on
CAD and built an initial prototype.

16. Escuela de Robótica del Chocó
Arlys, his classmate Wolsey Rubio (on the right in Figure
17(a), my partner May-Li Khoe, our friend Akil King, and
I designed a similar workshop in Arlys and Wolsey’s na-
tive Chocó. This region of the Colombian Pacific Coast

Figure 17. (a) César Ceballos and students discuss
configuration spaces during the Clubes de Ciencia de
Colombia. (b) Arlys Asprilla and one of his robotic arms.

is one of the most biodiverse in the world, and also one
of the most neglected historically by our government. We
partnered with the Escuela de Robótica del Chocó, led by
Jimmy Garcı́a, which seeks to empower local youth to de-
velop their scientific and technological skills in order to
address the problems faced by their communities.

At the end of the workshop, we asked the students:
What robot do you really want to design? Deison Rivas
wants to build a firefighter robot; it will quickly and safely
go in and out of houses—traditionally made of wood—
and put out the fires that have razed entire city blocks in
Quibdó in the past. Juan David Cuenta wants to design an
agile rescue robot; it will help people stuck under the fre-
quent landslides caused by illegal mining operations and
by heavy rainfalls on the roads.

This theoretical exercise in robotic optimization imme-
diately took on new meaning, thanks to the wisdom of
these young people.

AUGUST 2020 NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY 985

http://math.sfsu.edu/federico/robots.html
http://math.sfsu.edu/federico/robots.html


Figure 18. (a) At the Escuela de Robótica del Chocó. (b)
Deison Rivas and Juan David Cuenta.

17. What Does It Mean to Do Math Ethically?
Six years ago, my student Brian Cruz asked me whether
mathematicians have an ethical code, similar to the Hippo-
cratic Oath adopted by physicians. More than two decades
into my mathematical career, I had never thought or heard
of this specific suggestion.

Thanks to Brian, I did some research, gathered some
resources with the help of my students,3 and I now de-
vote one day of each semester to discuss this question with
them. Posing the question to them is surely more impor-
tant than proposing an answer:
Writing assignment. What does “doing mathematics ethically”
mean to you? This question is an invitation to recognize the
power you carry as a mathematician, and the privilege and re-
sponsibility that comes with it. When you enter a scientific ca-
reer, you do not leave yourself at the door. You can choose how
to use that power. My hope is that you will always continue to
think about this in your work.

3These resources are available at math.sfsu.edu/federico
/ethicsinmath.html.

Arlys Asprilla César Ceballos Hanner Bastidas

John Guo Matthew Bland Maxime Pouokam

Megan Owen Rika Yatchak

Seth Sullivant Tia Baker

ACKNOWLEDGMENTS. I would like to extend my sin-
cere gratitude to the students and colleagues who have
collaborated with me on this research: Arlys Asprilla,
César Ceballos, Hanner Bastidas, John Guo, Matthew
Bland, Maxime Pouokam, Megan Owen, Rika Yatchak,
Seth Sullivant, and Tia Baker.

I am also very grateful to the many people who en-
couraged me and helped me figure out how to tell this
story.

References
[1] Aaron Abrams and Robert Ghrist, State complexes for meta-

morphic robots, The International Journal of Robotics Re-
search 23 (2004), no. 7-8, 811–826.

[2] Sandra C. Alvarez, Tracing a cartography of struggle: reflec-
tions on twenty years of transnational solidarity with the U’wa
people of Colombia, International Feminist Journal of Poli-
tics 20 (2018), no. 1, 86–90.

986 NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY VOLUME 67, NUMBER 7

http://math.sfsu.edu/federico/ethicsinmath.html
http://math.sfsu.edu/federico/ethicsinmath.html


[3] Federico Ardila, Tia Baker, and Rika Yatchak, Moving robots
efficiently using the combinatorics of CAT(0) cubical complexes,
SIAM J. Discrete Math. 28 (2014), no. 2, 986–1007, DOI
10.1137/120898115. MR3224575

[4] Federico Ardila, Hanner Bastidas, Cesar Ceballos, and
John Guo, The configuration space of a robotic arm in a tunnel,
SIAM J. Discrete Math. 31 (2017), no. 4, 2675–2702, DOI
10.1137/16M1089411. MR3732943

[5] Federico Ardila, Megan Owen, and Seth Sulli-
vant, Geodesics in CAT(0) cubical complexes, Adv.
in Appl. Math. 48 (2012), no. 1, 142–163, DOI
10.1016/j.aam.2011.06.004. MR2845512

[6] Federico Ardila-Mantilla, Todos cuentan: Cultivating diver-
sity in combinatorics, Notices Amer. Math. Soc. 63 (2016),
no. 10, 1164–1170.

[7] Louis J. Billera, Susan P. Holmes, and Karen Vogtmann,
Geometry of the space of phylogenetic trees, Adv. in Appl. Math.
27 (2001), no. 4, 733–767, DOI 10.1006/aama.2001.0759.
MR1867931

[8] Michael W. Davis, Groups generated by reflections and
aspherical manifolds not covered by Euclidean space,
Ann. of Math. (2) 117 (1983), no. 2, 293–324, DOI
10.2307/2007079. MR690848

[9] Centro Nacional de Memoria Histórica, Observatorio de
memoria y conflicto, centrodememoriahistorica.gov
.co/observatorio (August 2018).

[10] United Nations High Commissioner for Refugees, Global
trends, forced displacement in 2018, https://www.unhcr
.org/5d08d7ee7.pdf (June 2019).

[11] R. Ghrist and V. Peterson, The geometry and topology of
reconfiguration, Adv. in Appl. Math. 38 (2007), no. 3, 302–
323, DOI 10.1016/j.aam.2005.08.009. MR2301699

[12] M. Gromov, Hyperbolic groups, Essays in group theory,
Math. Sci. Res. Inst. Publ., vol. 8, Springer, New York,
1987, pp. 75–263, DOI 10.1007/978-1-4613-9586-7_3.
MR919829

[13] Koyo Hayashi, A polynomial time algorithm to com-
pute geodesics in CAT(0) cubical complexes, 45th Interna-
tional Colloquium on Automata, Languages, and Program-
ming, LIPIcs. Leibniz Int. Proc. Inform., vol. 107, Schloss
Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, Art. No.
78, 14 pp. MR3830009

[14] G. A. Niblo and L. D. Reeves, The geometry of cube
complexes and the complexity of their fundamental groups,
Topology 37 (1998), no. 3, 621–633, DOI 10.1016/S0040-
9383(97)00018-9. MR1604899

[15] Megan Owen and J. Scott Provan, A fast algorithm for
computing geodesic distances in tree space, IEEE/ACM Trans-
actions on Computational Biology and Bioinformatics
(TCBB) 8 (2011), no. 1, 2–13.

[16] Martin Roller, Poc sets, median algebras and group
actions, Habilitationschrift, Regensberg; available at
arXiv:1607.07747 (1998).

[17] Michah Sageev, Ends of group pairs and non-positively
curved cube complexes, Proc. London Math. Soc. (3) 71
(1995), no. 3, 585–617, DOI 10.1112/plms/s3-71.3.585.
MR1347406

[18] Sara Sidner and Mallory Simon, How robot, explo-
sives took out Dallas sniper in unprecedented way, CNN
News, https://edition.cnn.com/2016/07/12/us
/dallas-police-robot-c4-explosives/index
.html (July 2016).

[19] Glynn Winskel, An introduction to event structures, Lin-
ear time, branching time and partial order in logics and
models for concurrency (Noordwijkerhout, 1988), Lecture
Notes in Comput. Sci., vol. 354, Springer, Berlin, 1989,
pp. 364–397, DOI 10.1007/BFb0013026. MR1035280

Federico
Ardila-Mantilla

Credits

Opening graphic and Figures 1–17(a) are courtesy of Federico
Ardila-Mantilla.

Figure 17(b) is courtesy of Arlys Asprilla.
Figure 18 is courtesy of May-Li Khoe.
Photo of Arlys Asprilla is courtesy of Arlys Asprilla.
Photo of César Ceballos is courtesy of César Ceballos.
Photo of Hanner Bastidas is courtesy of Hanner Bastidas.
Photo of John Guo is courtesy of John Guo.
Photo of Matthew Bland is courtesy of Matthew Bland.
Photo of Maxime Pouokam is courtesy of Maxime Pouokam.
Photo of Megan Owen is courtesy of Megan Owen.
Photo of Rika Yatchak is courtesy of Rika Yatchak.
Photo of Seth Sullivant is courtesy of Seth Sullivant.
Photo of Tia Baker is courtesy of Tia Baker.
Photo of Federico Ardila-Mantilla is courtesy of May-Li Khoe.

AUGUST 2020 NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY 987

http://dx.doi.org/10.1137/120898115
http://dx.doi.org/10.1137/16M1089411
http://dx.doi.org/10.1006/aama.2001.0759
http://dx.doi.org/10.2307/2007079
http://dx.doi.org/10.1016/j.aam.2005.08.009
http://dx.doi.org/10.1007/978-1-4613-9586-7_3
http://dx.doi.org/10.1016/S0040-9383(97)00018-9
http://dx.doi.org/10.1016/S0040-9383(97)00018-9
http://dx.doi.org/10.1112/plms/s3-71.3.585
http://dx.doi.org/10.1007/BFb0013026
http://dx.doi.org/10.1137/16M1089411
https://edition.cnn.com/2016/07/12/us/dallas-police-robot-c4-explosives/index.html
https://edition.cnn.com/2016/07/12/us/dallas-police-robot-c4-explosives/index.html
https://edition.cnn.com/2016/07/12/us/dallas-police-robot-c4-explosives/index.html
http://centrodememoriahistorica.gov.co/observatorio
http://centrodememoriahistorica.gov.co/observatorio
https://www.unhcr.org/5d08d7ee7.pdf
https://www.unhcr.org/5d08d7ee7.pdf
http://www.arxiv.org/abs/1607.07747
http://www.ams.org/mathscinet-getitem?mr=919829
http://www.ams.org/mathscinet-getitem?mr=1035280
http://www.ams.org/mathscinet-getitem?mr=3224575
http://www.ams.org/mathscinet-getitem?mr=3732943
http://www.ams.org/mathscinet-getitem?mr=2845512
http://www.ams.org/mathscinet-getitem?mr=1867931
http://www.ams.org/mathscinet-getitem?mr=3830009
http://www.ams.org/mathscinet-getitem?mr=1604899
http://www.ams.org/mathscinet-getitem?mr=1347406
http://www.ams.org/mathscinet-getitem?mr=690848
http://www.ams.org/mathscinet-getitem?mr=2301699