# Congestion and Scalability in Robot Swarms: a Study on Collective Decision
Making

Karthik Soma1, Vivek Shankar Vardharajan1, Heiko Hamann2 and Giovanni
Beltrame1 *This work was supported by the Natural Science and Engineering
Council of Canada (NSERC).1Karthik Soma, Vivek Shankar Vardharajan and
Giovanni Beltrame are with École Polytechnique de Montréal, 2900 Boul Édouard-
Montpetit, Québec, CA<EMAIL_ADDRESS>Heiko Hamann is with the
Department of Computer and Information Science, University of Konstanz, 78457,
Konstanz, Germany.

###### Abstract

One of the most important promises of decentralized systems is scalability,
which is often assumed to be present in robot swarm systems without being
contested. Simple limitations, such as movement congestion and communication
conflicts, can drastically affect scalability. In this work, we study the
effects of congestion in a binary collective decision-making task. We evaluate
the impact of two types of congestion (communication and movement) when using
three different techniques for the task: Honey Bee inspired, Stigmergy based,
and Division of Labor. We deploy up to 150 robots in a physics-based simulator
performing a sampling mission in an arena with variable levels of robot
density, applying the three techniques. Our results suggest that applying
Division of Labor coupled with versioned local communication helps to scale
the system by minimizing congestion.

##  I INTRODUCTION

Swarm robotics takes inspiration from natural swarms to design coordinated
behaviors. Since natural swarms exhibit properties like scalability, fault
tolerance, robustness, and parallelism, it is often assumed that these would
also be present in artificial systems like robot swarms [1]. Designing robot
swarms with local control rules to attain a global swarm behavior through
emergence alone might not be sufficient to ensure scalability. Practical
constraints such as crowding and communication issues hinder the scalability
of these systems and affect the deployment of robot swarms in real-world
scenarios [2]. In general, when robots in a swarm share access to a resource
(whether a communication medium or physical space), it often gives rise to
congestion.

Consequently, designing and deploying robot swarms involves choosing local
communication and coordination strategies and adapting to a swarm size that
will limit congestion. Making the swarm size too large could conversely affect
the task performance, giving rise to an optimal swarm size to maximize
performance [3]. In some application scenarios, the swarm size could not be
chosen, and the system must perform reasonably even when congested. We believe
it is fundamental to understand the role of congestion to address and design
strategies to achieve optimal performance for robot swarms.

Virtual StigmergyNESTZONE BZONE
APhototaxisAntiphototaxisAntiphototaxisPhototaxis Figure 1: Diagram of a
typical binary collective decision-making scenario.

We investigate the effect of congestion on a binary decision-making problem
where the robots assess the quality of two sites via sampling and collectively
determine the superior location (see fig. 1). The robots share an arena of a
given size (the “space medium”), a limited communication medium, have a
collision prevention behavior, and a belief propagation mechanism through
local communication. We identify two types of congestion: movement congestion,
which happens when robots hinder each other’s movements and is proportional to
the arena occupancy and the robot behavior; and communication congestion,
which is caused by belief propagation conflicts that depend on the recency of
the belief, communication range and the accuracy of the belief.

We answer three research questions:

  1. 1.

What are the effects of movement and communication congestion w.r.t media
occupancy?

  2. 2.

What could be the essential factors that contribute to congestion?

  3. 3.

Does introducing additional coordination mechanisms reduce congestion?

The remainder of the paper is organized into the following sections: we
discuss some related works in II, explain the problem setting in III, explain
the strategies mentioned above in IV, report the results V and draw some
conclusions in VI.

##  II Related work

_Collective decision-making:_ There is a vast literature of self-organizing
discrete collective decision-making (DCDM) strategies inspired by the house-
hunting behavior [4, 5] and positive feedback modulation [6] from the waggle
dance of honey bees, where the task of the swarm is to find the best of two
discrete options spatially segregated into zones (see Figure 1). Each agent
assesses the qualities of sites, advertises their opinions proportionally to
the quality of zone and applies a voter based [7] or majority [8] based
decision rule. This problem is extended to dynamic site qualities in [9].

In a slightly different setting, the swarm is tasked to find the frequency of
features spread all over the environment for a single feature [10], with noise
[11], and multiple features [12]. Further Bayesian approaches were formulated
and studied for static [13, 14] and dynamic environments [15].

Continuous collective decision-making (CCDM), on the other hand, deals with
finding consensus on some environmental feature (e.g., intensity [16],
environmental edge [17] and tile density [18]).

None of the above decision-making strategies address the movement and
communication congestion arising from increasing system size. In this work, we
adapt the existing static, discrete collective decision-making setting and
strategy from [7, 8] coupled with feature-like distribution limited to the
zones [10], combining the Nest site selection and collective perception from
swarm robotics literature.

_Congestion prediction or mitigation:_ Ants [19] and humans [20] form self-
organizing lanes that help avoid congestion. In artificial systems, some
measures used to quantify movement congestion are throughput and collisions.
Throughput encodes the ability of multiple robots to reach a given target, and
Dos Passos et al. [21] use throughput to compare congestion of various
strategies. Yu and Wold [22] deploy ConvLSTMs to predict delays caused by
congestion in a centralized warehouse management system and increase
throughput. Proximity encounters and collisions are often used as a measure
for congestion: A strategy to avoid head-on collisions between two groups of
swarms was proposed in [23], and Wu et al. [24] propose collision-aware task
assignment to minimize congestion. Communication congestion is often
correlated to a degraded medium offering lower bandwidths [25, 26]. In robot
swarms, propagating beliefs with an increasing number of robots can generate
conflicts on top of these bandwidth concerns. We use communication conflicts
as a metric to quantify communication congestion.

_Divison of labor:_ A taxonomy of heterogenous robot swarms includes two high-
level classes: behaviorally (software) and physically (hardware) different
swarm members [27]. Behaviourally distinct swarm members often have uniform
hardware with role-specific behavior as in [28], where agents specialize to
become collectors or droppers in a food transporting task. Behavioral
variations can be dynamically triggered based on environmental features [29]
or could be static to divide tasks, as in shepherding [30]. Swarms of
physically distinct robots can benefit from traversing parts of the
environment with aerial and ground robots [31] or collaboratively mapping the
environment with various sensors [32]. Having physically and behaviorally
different swarm members can offer efficient task completion during a
collaborative mapping task [33]. A variety of missions have demonstrated the
benefits of using physically and behaviorally heterogeneous swarms in missions
like search and retrieval task [34] and formation control [35]. In this work,
we use a physically uniform and behaviorally distinct swarm to study decision-
making in the Division of Labor technique.

Init
---
$Id\%2=0$
---
$Z_{i}=A$
$Id\%2=1$
---
$Z_{i}=B$
$PT+CA$
---
$PT+CA$
---
$DF+CA$
---
Zone A msg
---
No zone A msg
---
No zone A and B msg
---
Zone A or B msg
---
No zone A and B
---
msg
Virtual
---
stigmergy
$Samples>S_{T}$
---
$Opinion=B$
---
$Z_{i}=B$
$Opinion=A$
---
$Z_{i}=A$
$Samples>S_{T}$
---
Update stig.
---
Broadcast bel.
---
Collect $\&$ avg
---
nei bel.
Read stig.
---
$Time>W_{T}$.
---
$Time>W_{T}$.
---
Update
---
Opinion.
SM1
---
SM2
---
Update
---
Opinion.
Zone A msg
---
Zone A msg
---
Zone A msg
---
Local Communication
---
Versioned local
---
Communication
Zone A followers
---
White zone explorers
---
Nest zone followers
---
$!PT+CA$
---
$!PT+CA$
---
$DF+CA$
---
$DF+CA$
---
Decision makers
---
No zone B msg
---
No zone B msg
---
Zone B msg
---
Zone B msg
---
Zone B msg
---
Zone B followers
---
Zone B explorers
---
$SM1:$ Honey Bee inspired decision-making and
---
$SM2:$ Stigmergy based decision-making.
---

Init
---
$Id\%3==0$
---
$Z_{i}=A$
---
$Z_{i}=B$
---
$Z_{i}=Nest$
---
$Id\%3==1$
---
$Id\%3==2$
---
$PT+CA$
---
$PT+CA$
---
$DF+CA$
---
No zone A msg
---
No zone A beacon
---
No zone A $\&$ B msg
---
No zone A $\&$ B msg
---
$Samples>S_{T}$
---
$Samples>S_{T}$
---
Zone A msg
---
Zone A msg
---
Zone A msg
---
Zone A followers
---
Zone A explorers
---
Nest zone explorers
---
$!PT+CA$
---
$!PT+CA$
---
$DF+CA$
---
No zone B msg
---
No zone B msg
---
Zone B msg
---
Zone B msg
---
Zone A msg
---
Zone B followers
---
Zone B explorers
---
.
---
Update stig.
---
Update stig.
---
Virtual
---
stigmergy
Update
---
Opinion.
Update
---
Opinion.
Update
---
Opinion.
Read stig.
---
Read stig.
---
Read stig.
---
$SM3:$ Divsion of labor based decision-making
---

Figure 2: The state machines illustrate the behavioral states of robots during
the three strategies Honey bee, Stigmergy, and Division of Labor SM(1-3).
Every robot in the swarm deployed a corresponding state machine during the
evaluation runs.

##  III Problem Setting

We consider an arena of size $U\times V$ subdivided into three zones: A, B,
and Nest. Each sampling zone (A,B) is composed of a uniform distribution of a
fill ratio comprising of white and black tiles representing the quality of the
site $\rho\in[0,1]$, where $0$ represents complete black and $1$ represents
complete white. A swarm composed of $N$ Khepera IV robots (modeled as
$\dot{x}_{i}=u_{i}$, where $x_{i}\in\mathbb{R}^{2}$ is the position of the
robot, with a circular communication model of range $R$, and with a ground
footprint of 0.045 $m^{2}$), equipped with 4 ground
($G_{i}=\\{G_{i}^{0},..,G_{i}^{3}\\}$), 8 proximity
($P_{i}=\\{P_{i}^{0},..,P_{i}^{7}\\}$), and 8 light sensors
($L_{i}=\\{L_{i}^{0},..,L_{i}^{7}\\}$). Each robot has to individually collect
$S_{T}$ samples using the ground sensors, calculate and communicate its belief
state ($0\leq bel_{i}\leq 1$), and avoid collisions. The swarm collectively
decides the highest quality zone (A or B). There are five beacon robots placed
at the boundary of both the sampling zones that constantly broadcast zone
option messages (i.e, A or B) to help robots situate themselves inside the
sampling zones. If a robot receives no broadcast message it is considered to
be in the Nest zone. To help robots move between the zones there is a light
placed above zone A, following the light gradient using the light sensors
($PT$ \- Phototaxis) leads the robots to zone A while doing the opposite
($!PT$ \- Antiphototaxis) leads the robots away from zone A to the zone B.

##  IV Approach

We consider three state-machines outlined in fig. 2: Honey Bee, Stigmergy, and
Division of Labor decision-making strategies. These state machines are made of
robot behaviors such as Diffusion ($DF$), Collision Avoidance ($CA$),
Phototaxis ($PT$), and AntiPhototaxis ($!PT$).
_Collision Avoidance ( $CA$):_ To avoid obstacles and other robots, every
robot uses the proximity sensors $P_{i}$. An obstacle vector is constructed as
$V_{i}^{o}=\frac{\sum_{i=0}^{7}P_{i}^{i}}{||P_{i}||}$ and applied as a control
input to the robot as shown below, where $S_{o}$ is a scaling factor and
$O_{lt}$ and $O_{at}$ are threshold parameters for obstacle avoidance.

$\displaystyle\dot{x}_{i}$
$\displaystyle=\frac{-S_{o}V_{i}^{o}}{||V_{i}^{o}||},$
$\displaystyle||V_{i}^{o}||\geq O_{lt}\ \&\ $ $\displaystyle-O_{at}\geq\angle
V_{i}^{o}\geq O_{at}$ (1)

This behavior moves the robot in the opposite direction of the aggregated
obstacle vector ($V_{i}^{o}$), hence locally avoiding collisions.
_Phototaxis and AntiPhototaxis ( $PT$ and $!PT$):_ To move between zones
robots use the light sensors $L_{i}$ whose readings are defined by the
equation $||L_{i}^{i}||=(I/x)^{2}$, where $I$ is the reference intensity and
$x$ the distance between the light and the sensor. A Light vector is
constructed as $V_{i}^{l}=\frac{\sum_{i=0}^{7}L_{i}^{i}}{||L_{i}||}$ and
applied as a control input to the robot as shown below unless a collision is
detected, where $S_{l}$ is a scaling factor.

$\displaystyle\dot{x}_{i}$
$\displaystyle=\begin{cases}\frac{S_{l}V_{i}^{l}}{||V_{i}^{l}||}\ ,&PT\\\
\frac{-S_{l}V_{i}^{l}}{||V_{i}^{l}||}\ ,&!PT\end{cases}$ (2)

_Diffusion ( $DF$)_: When the robot needs to explore the sampling zones to
collect samples or mix with other agents for efficient information propagation
while advertising the beliefs in the Nest zone, it uses diffusion, where the
robot just moves forward in the local frame with the maximum speed
($u_{i}^{x}=M_{s}$, $u_{i}^{y}=0$), unless a collision is detected. Collisions
with other robots and obstacles helps the robot diffuse.

###  IV-A Honey Bee

In this decision-making strategy, the robots are first initialized in a random
distribution in the Nest zone. Robots with even/odd IDs are assigned ($Z_{i}$)
to sample the zone (A/B) respectively. To reach the zone (A/B) the robots
perform $PT/!PT+CA$. When they reach the zone, they will receive a broadcast
from the A/B zone beacons. Upon reaching the zone, the robots diffuse
($DF+CA$) and start collecting $S_{T}$ no of samples from their ground
sensors, where each sample is
$bel_{i}(t)=\frac{\sum_{i=0}^{3}G_{i}^{i}}{||G_{i}||}$. After this, they come
back to the Nest zone to disseminate their averaged beliefs by executing the
opposite behavior $!PT/PT+CA$ used to reach the zones A/B. Upon reaching the
Nest zone, robots broadcast their averaged individual beliefs calculated as
$avg_{i}^{bel}=\frac{\sum_{t=1}^{S_{T}}bel_{i}(t)}{S_{T}}$ while diffusing
($DF+CA$) for a period of time ($W_{T}\propto avg_{i}^{bel}$). This positive
modulation of belief disemination is done to influence more robots to choose
the best site. Before the end of this period of time ($W_{T}$), robots start
collecting their local neighbors ($n_{i}$) beliefs. Robots further divide
$n_{i}$ into two sets $nA/B:=\\{j|j\in n_{i}\ \textit{and}\ Z_{j}=A/B\\}$.
Along with their own beliefs, robots calculate two aggregated averages one
each for zone $Z_{i}$ and $!Z_{i}$

$\displaystyle
agg_{i}^{Z_{i}}=\frac{\sum_{j=1}^{|nZ_{i}|}avg_{j}^{bel}+avg_{i}^{bel}}{|nZ_{i}|+1}$
(3) $\displaystyle agg_{i}^{!Z_{i}}$
$\displaystyle=\begin{cases}\frac{\sum_{j=1}^{|!Z_{i}|}avg_{j}^{bel}}{|n!Z_{i}|}\\\
0.0&|n!Z_{i}|=0\end{cases}$ (4)

if $agg_{i}^{!Z_{i}}$ $>$ $agg_{i}^{Z_{i}}$, $Z_{i}$ is updated to $!Z_{i}$
(positive modulation recruiting more robots towards the higher quality site,
represented by blue lines in the left of fig. 2), otherwise it remains the
same and the cycle is continued. The experiment is continued until all the
robots form the same opinion.

This differs from the approaches used in the [7, 8] in two ways. The qualities
of the zone aren’t directly broadcasted when the robots enter the zone, the
robots calculate them by using their ground sensors. This change was done to
make robots explore the zone, which is more realistic than the scenarios
considered in [7, 8] and this approach further emphasizes the effect of
movement flexibility in collective decision-making, as robots now have to move
within zones. The second change is that the individual averaged beliefs (not
opinions) are broadcasted, to have easier decision-making during tie-breaks
and have a belief consensus with virtual stigmergy. This change requires very
little communication overhead.

###  IV-B Stigmergy

In this decision-making strategy, we adopt the same state machine from the
Honey Bee approach but instead of using a local communication broadcasts, we
use a versioned local communication approach (virtual stigmergy [36]) to store
the aggregated beliefs of both zones in separate entries ($agg^{A/B}$).
Virtual stigmergy creates a shared tuple memory among the robots, where each
entry contains a key identifier, Lamport clock (version number), robot id
modifying the value and the value to be stored. Robots in the swarm are
allowed to read and write to the local memory of the tuple value. Each access
to the local memory creates a message to be broadcast in the local
neighborhood. Whenever a robot receives a more recent update to the tuple, it
updates the local memory and broadcasts the entry, allowing for more recent
entries to be propagated.

The entries in the virtual stigmergy are synchronized as long the robots are
connected [36], i.e., a communication path exists between any two connected
robots. With virtual stigmergy, robots can communicate with other robots even
with movement congestion. With this property, it doesn’t make sense for the
robots to spend time advertising their averaged beliefs proportional to the
average belief ($avg_{i}^{bel}$). Therefore $W_{T}$ is constant irrespective
of the quality of the site. $W_{T}$ has to be still non-zero as mixing robots
is still essential for synchronizing entries. At the beginning of this period
($W_{T}$) the robots read the entry of the zone they are assigned ($Z_{i}$)
and update it using the equation 5.

$\displaystyle agg^{Z_{i}}$
$\displaystyle=agg^{Z_{i}}+w(avg_{i}^{bel}-agg^{Z_{i}})$ (5)

where $w$ is the weight parameter. Instead of calculating the $agg^{A/B}$ like
equations 3, 4, the robots use the values from the stigmergy (Note that the
subscript $i$ is dropped for $agg^{Z_{i}}$ in equation 5). As multiple robots
might try to update the stigmergy at the same time (communication conflicts),
a conflict resolution manager is used that keeps track of the maximum value
for the aggregate belief for all robots. We count the number of conflicts
occurring in this manager as the number of communication conflicts.

###  IV-C Division of Labor

It can be seen that every robot in Honey Bee approach pursues two roles:
sampling and advertising, this mandates movement of robots between zones. In
this approach instead, we assign fixed permanent roles for robots: samplers
and networkers hence spatially segregating them into zones (A,B) and Nest
respectively. Robots are randomly initialized in the Nest zone. One-third of
robots are assigned ($Z_{i}$) to sample zone A, they follow the same state
machine from the Honey Bee approach until they enter zone A. Similarly one-
third of robots are assigned to be zone B samplers. This approach differs from
the previous approaches after this point as the robots stay and diffuse in
their zones (essentially disabling the positive modulation leading to the
recruitment of more and more robots towards the higher quality zone in
previous approaches) and after every $S_{T}$ number of samples collected, they
read both the entries to keep track of the best zone opinion and update the
aggregated belief in the stigmergy (similar to equation 5). The remaining one-
third of robots stay and diffuse in the Nest zone acting as networkers by
providing connectivity between the samplers for efficient belief propagation
between both the sampling zones. Additionally, they also constantly keep track
of the best zone opinion. This is continued until all the robots form one
opinion.

##  V Results

Figure 3: Congestion trends for scalability metrics for all three approaches.
It would appear that the total time trends for all three approaches have a
similar pattern for any decentralized system [3] and the optimal number of
robots for our setting would be around $(N\in\ \\{20-60\\})$ roughly. All
experiments of Stigmergy and Division of Labor converged to the superior
quality opinion before 6000 s timeout period, whereas some experiments of
$(N=120,\ R=0.8),(N=2,\ R=\\{0.4,0.8\\})$ and all experiments in $(N=120,\
R=0.4),(N=150,\ R=\\{0.4,0.8\\})$ for Honey Bee approach failed to converge to
any opinion.

Figure 4: Stagnation heatmaps for the positive modulation approaches are shown
in this figure for the combination $Z=A$, $R=0.4\ m$, $St_{T}$=1s (10
simulation timesteps). For the Honey bee approach $[T_{s},T_{f}]$ = $[95\%,\
100\%]$ and Stigmergy approach $[T_{s},T_{f}]$ = $[85\%,\ 100\%]$. The barrier
is of higher magnitude near the (zone A-Nest) boundary and has a decreasing
radial gradient (in bands) away from zone A (the gradient follows a similar
pattern to light intensity from the light centered at the end of zone A).
Honey Bee approach is significantly more congested for a fixed combination
compared to the Stigmergy approach (Honey Bee row is normalized by 5000 and
Stigmergy row is normalized by 1000.)

Figure 5: Stagnation heatmaps for Division of Labor approach is shown in this
figure for $N=150$ $R=0.4\ m$, $St_{T}$=1s (10 simulation timesteps). T =
start, represents $[T_{s},T_{f}]$ = $[0\%,\ 15\%]$, T = middle, represents
$[T_{s},T_{f}]$ = $[15\%,\ 85\%]$, and T = end, represents $[T_{s},T_{f}]$ =
$[85\%,\ 100\%]$. It can be seen that the magnitudes of stagnations are lesser
compared to fig 4 and stagnations outside the assigned zones occur only in the
starting phases of experiments. (All the rows are normalized by 1000.)

We investigate the scalability of the three approaches using the following
metrics: 1. average time spent by every robot avoiding collisions with other
robots and obstacles (arena walls), 2. average communication conflicts per
robot while updating the virtual stigmergy, and 3. total time taken for all
the robots to converge to highest quality opinion.

During all the experimental evaluations, we deploy the robots in a fixed arena
dimension of $U=4\ m,\ V=4\ m$ and a Nest of size $2m\times 4m$ with site A
quality $\rho_{A}=0.9$ and site B quality $\rho_{B}=0.1$. We varied the number
of robots $N\in\\{2,\ 4,\ 6,\ 10,\ 20,\ 40,\ 60,\ 80,\ 100,\ 120,\ 150\\}$
corresponding to a Nest robot density of $\\{1.3,\ 2.6,\ 3.9,\ 6.5,\ 13.1,\
26.2,\ 39.4,\ 52.5,\ 65.7,\ 78.8,\ 98.5\\}$ $\times$ $10^{-2}$ for Honey Bee
and Stigmergy based decision-making strategies. Similarly, for Division of
Labor technique, varied the robot numbers $N\in\\{3,\ 6,\ 9,\ 12,\ 24,\ 36,\
60,\ 81,\ 99,\ 120,\ 150\\}$ corresponding to a Nest robot density of
$\\{1.9,\ 3.9,\ 5.9,\ 7.8,\ 15.7,\ 23.6,\ 39.4,\ 53.2,\ 65,\ 78.8,\ 98.5\\}$
$\times$ $10^{-2}$. We set the communication range for all three techniques to
$R\in\\{0.4\ m,\ 0.8\ m,\ 1.2\ m\\}$ and repeated each configuration 30 times
with randomized robot placement following a normal distribution in the Nest
zone.

To further understand the effects of the movement congestion, we plot the
accumulated stagnation heatmap (defined as a robot spending over $St_{T}$
seconds in grids of size ($0.2\times 0.2$)) for an interval $[T_{s},T_{f}]$ in
fig. 4 and fig. 5. The averaged movement change gridmap divides the arena into
grids of size ($0.2\times 0.2$) for an interval $[T_{s},T_{f}]$ in fig. 6.
Averaged movement change for each grid cell is calculated by averaging the
movement vectors of robots in the grid over consecutive time steps
($x_{i}(t+1)-x_{i}(t)$). The stagnation heatmap and movement change gridmap
are averaged over all 30 repetitions of a given configuration. The stagnation
heatmap shows the congestion in space, while the averaged movement change
gridmap shows the movement of robots.

Leveraging the metrics introduced above, we make the following inferences:

(1) _Versioned local communication helps to overcome movement congestion, but
doesn’t decongest the system._ In fig. 3, the convergence time plot from the
first two rows show that the Stigmergy and Division of Labor strategy converge
significantly faster than the Honey Bee inspired, despite a comparable
stagnation pattern in Stigmergy based (see fig. 4). The presence of stagnation
with the Stigmergy approach indicates that congestion still exists. Faster
convergence correlates with the lower time spent avoiding obstacles.

(2) _Positive modulation in robot swarms increases the impact of stagnation
and convergence time._ A stagnation barrier (ref fig. 4) of increasing
thickness with an increased number of robots occurs near the superior quality
zone for Stigmergy and Honey Bee approaches. The barrier could result from
positive modulation recruiting more and more robots to visit the higher
quality zone as indicated in [7]. The barrier formation can also be inferred
in fig. 6, where the averaged movement vectors of robots point towards each
other, implying the robots’ intention to move towards each other. The
formation of a barrier significantly hinders the information propagation in
the Honey Bee approach, where belief propagation occurs through local
broadcasts and the ability of robots to move to exchange beliefs effectively.
The effect of the stagnation barrier is more pertinent for larger robot
density and smaller communication range for Honey Bee inspired.

(3) _Introducing structure through division of labor helps to minimize
movement congestion._ Fig. 5 shows the stagnation heatmap for the Division of
Labor approach. The zone samplers and nest zone networker robots experience
minimal stagnation within their respective zones as they are contained within
their zones (except T=start, as robots are deployed in the Nest zone). The
minimal stagnation in the grids directly reflects on the convergence time in
fig. 3, where convergence time and time spent on collisions are minimal
compared to the other two approaches. However, communication conflicts are
larger than in the Stigmergy approach as more updates to the robot beliefs
propagate through the swarm. The Stigmergy approach still suffers from
movement congestion, thereby influencing the ability of the robots to move,
sample, and update the stigmergy, which results in fewer conflicts.

(4) _Longer communication ranges make a positive difference only with the
local broadcast approach and make a negative impact with the versioned local
communication strategy for a larger number of robots._ Longer communication
range combinations used in Honey Bee approach improve the total time and time
spent avoiding collisions (ref fig. 3) compared to shorter communciation
ranges ($R=0.4\ m<0.8\ m<1.2\ m$) for any number of robots in the system
except ($N=150,\ R=\ 0.8\ m$, which has a slight increase in the time spent
avoiding collisions per robots compared to $N=150,\ R=\ 0.4\ m$). Whereas the
number of conflicts arising with the versioned local communication approach
increases with a longer communication range and a higher number of robots
($N>60$). As the movement congestion doesn’t impact the propagation of beliefs
with the versioned local communication approach, there is no significant
improvement in the total time taken and time spent avoiding collisions for
both these approaches compared to shorter communication ranges for a fixed
number of robot combination (for $N>20$, ref fig 3).

Figure 6: Movement changes for the combination $N\in\\{20,\ 100,\ 150\\}$,
$R=0.4\ m$, $Z=A$, $[T_{s},T_{f}]$ = $[85\%,\ 100\%]$. The top row shows the
averaged movement change of robots entering Zone A from Nest to sample (Zone A
followers in Stigmergy approach fig. 2) and the bottom row shows the averaged
movement change of robots entering Nest from Zone A (Nest followers in
Stigmergy approach fig. 2.)

##  VI Conclusions

Current collective decision-making strategies rarely address congestion-
related issues. This will have huge implications when it comes to deploying
robot swarm systems in real-world scenarios, as these systems will scale
poorly. In this paper, we discuss the impact of movement congestion and belief
propagation conflicts on swarm behaviors, specifically collective decision-
making. We find that using versioned local communication and Division of Labor
mechanisms helps to reduce the impact of movement congestion, despite the
increasing trends for communication conflicts. Further research could look
into congestion-aware initialization strategies, congestion-aware collision
avoidance, and dynamic approaches to switch between different state machines
for collective decision-making systems. We believe our results transfer to
other areas of swarm robotics such as foraging, task allocation, collective
construction etc. and would welcome additional studies in these domains.

## References

  * [1] M. Brambilla, E. Ferrante, M. Birattari, and M. Dorigo, “Swarm robotics: a review from the swarm engineering perspective,” _Swarm Intell_ , vol. 7, pp. 1–41, 2013.
  * [2] M. Dorigo, G. Théraulaz, V. Trianni, and G. Theraulaz, “Reflections on the future of swarm robotics,” _Science Robotics_ , vol. 2020, p. 4385. [Online]. Available: https://hal.science/hal-03362864
  * [3] H. Hamann, “Superlinear scalability in parallel computing and multi-robot systems: Shared resources, collaboration, and network topology,” in _Architecture of Computing Systems – ARCS 2018_ , M. Berekovic, R. Buchty, H. Hamann, D. Koch, and T. Pionteck, Eds. Cham: Springer International Publishing, 2018, pp. 31–42.
  * [4] T. Seeley, “Honeybee democracy,” 12 2009.
  * [5] N. Franks, S. Pratt, E. Mallon, N. Britton, and D. Sumpter, “Information flow, opinion polling and collective intelligence in house-hunting social insects,” _Philosophical transactions of the Royal Society of London. Series B, Biological sciences_ , vol. 357, pp. 1567–83, 12 2002.
  * [6] S. Garnier, J. Gautrais, and G. Theraulaz, “The biological principles of swarm intelligence,” _Swarm Intell_ , vol. 1, pp. 3–31, 2007.
  * [7] G. Valentini, H. Hamann, and M. Dorigo, “Self-organized collective decision making: The weighted voter model.” [Online]. Available: www.ifaamas.org
  * [8] G. Valentini, E. Ferrante, H. Hamann, and M. Dorigo, “Collective decision with 100 kilobots: speed versus accuracy in binary discrimination problems collective decision with 100 kilo-bots: speed versus accuracy in binary discrimination problems. autonomous agents and multi-agent systems,” vol. 30, pp. 553–580, 2016. [Online]. Available: https://hal.archives-ouvertes.fr/hal-01403730
  * [9] J. Prasetyo, G. De Masi, and E. Ferrante, “Collective decision making in dynamic environments,” _Swarm Intelligence_ , vol. 13, 12 2019.
  * [10] G. Valentini, D. Brambilla, H. Hamann, and M. Dorigo, “Collective perception of environmental features in a robot swarm,” in _Swarm Intelligence_ , M. Dorigo, M. Birattari, X. Li, M. López-Ibáñez, K. Ohkura, C. Pinciroli, and T. Stützle, Eds. Cham: Springer International Publishing, 2016, pp. 65–76.
  * [11] K. Chin, Y. Khaluf, and C. Pinciroli, “Minimalistic collective perception with imperfect sensors,” 09 2022.
  * [12] J. T. Ebert, M. Gauci, and R. Nagpal, “Multi-feature collective decision making in robot swarms,” in _Adaptive Agents and Multi-Agent Systems_ , 2018\.
  * [13] J. T. Ebert, M. Gauci, F. Mallmann-Trenn, and R. Nagpal, “Bayes bots: Collective bayesian decision-making in decentralized robot swarms.”
  * [14] Q. Shan and S. Mostaghim, “Discrete collective estimation in swarm robotics with distributed bayesian belief sharing,” _Swarm Intelligence_ , vol. 15, 12 2021.
  * [15] K. Pfister and H. Hamann, “Collective decision-making with bayesian robots in dynamic environments,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2022, pp. 7245–7250.
  * [16] M. Raoufi, H. Hamann, and P. Romanczuk, “Speed-vs-accuracy tradeoff in collective estimation: An adaptive exploration-exploitation case,” in _2021 International Symposium on Multi-Robot and Multi-Agent Systems (MRS)_ , 2021, pp. 47–55.
  * [17] Y. Khaluf, “Edge detection in static and dynamic environments using robot swarms,” 09 2017, pp. 81–90.
  * [18] Y. Khaluf, M. Allwright, I. Rausch, P. Simoens, and M. Dorigo, “Construction task allocation through the collective perception of a dynamic environment,” 11 2020.
  * [19] I. D. Couzin and N. R. Franks, “Self-organized lane formation and optimized traffic flow in army ants.”
  * [20] D. Helbing, P. Molnár, I. J. Farkas, and K. Bolay, “Self-organizing pedestrian movement,” _https://doi.org/10.1068/b2697_ , vol. 28, pp. 361–383, 6 2001. [Online]. Available: https://journals.sagepub.com/doi/10.1068/b2697
  * [21] A. Editors, J. Hu, Z. Peng, Y. T. dos Passos, X. Duquesne, and L. S. Marcolino, “On the throughput of the common target area for robotic swarm strategies,” 2022\. [Online]. Available: https://doi.org/10.3390/math10142482
  * [22] G. Yu and M. Wolf, “Congestion prediction for large fleets of mobile robots,” in _ICRA 2023_ , 2023. [Online]. Available: https://www.amazon.science/publications/congestion-prediction-for-large-fleets-of-mobile-robots
  * [23] L. Soriano Marcolino and L. Chaimowicz, “Traffic control for a swarm of robots: Avoiding group conflicts,” 11 2009, pp. 1949 – 1954.
  * [24] F. Wu, V. S. Varadharajan, and G. Beltrame, “Collision-aware task assignment for multi-robot systems,” in _2019 International Symposium on Multi-Robot and Multi-Agent Systems (MRS)_ , 2019, pp. 30–36.
  * [25] M. Barciś and H. Hellwagner, “Information distribution in multi-robot systems: Adapting to varying communication conditions,” in _2021 Wireless Days (WD)_ , 2021, pp. 1–8.
  * [26] P. Rybski, S. Stoeter, M. Gini, D. Hougen, and N. Papanikolopoulos, “Performance of a distributed robotic system using shared communications channels,” _Robotics and Automation, IEEE Transactions on_ , vol. 18, pp. 713 – 727, 11 2002.
  * [27] M. Bettini, A. Shankar, and A. Prorok, “Heterogeneous multi-robot reinforcement learning,” 2023.
  * [28] E. Ferrante, A. E. Turgut, E. A. Duéñez-Guzmán, M. Dorigo, and T. Wenseleers, “Evolution of self-organized task specialization in robot swarms,” _PLoS Computational Biology_ , vol. 11, 2015.
  * [29] N. Ayanian, “Dart: Diversity-enhanced autonomy in robot teams,” _The International Journal of Robotics Research_ , vol. 38, no. 12-13, pp. 1329–1337, 2019. [Online]. Available: https://doi.org/10.1177/0278364919839137
  * [30] A. Ozdemir, M. Gauci, and R. Groß, “Shepherding with robots that do not compute,” 09 2017.
  * [31] V. S. Varadharajan, D. St-Onge, B. Adams, and G. Beltrame, “Swarm relays: distributed self-healing ground-and-air connectivity chains,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 4, pp. 5347–5354, 2020.
  * [32] P.-Y. Lajoie and G. Beltrame, “Swarm-slam : Sparse decentralized collaborative simultaneous localization and mapping framework for multi-robot systems,” 2023\.
  * [33] I. D. Miller, F. Cladera, T. Smith, C. J. Taylor, and V. Kumar, “Stronger together: Air-ground robotic collaboration using semantics,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 9643–9650, 2022.
  * [34] M. Dorigo, D. Floreano, L. M. Gambardella, F. Mondada, S. Nolfi, T. Baaboura, M. Birattari, M. Bonani, M. Brambilla, A. Brutschy, D. Burnier, A. Campo, A. L. Christensen, A. Decugniere, G. Di Caro, F. Ducatelle, E. Ferrante, A. Forster, J. M. Gonzales, J. Guzzi, V. Longchamp, S. Magnenat, N. Mathews, M. Montes de Oca, R. O’Grady, C. Pinciroli, G. Pini, P. Retornaz, J. Roberts, V. Sperati, T. Stirling, A. Stranieri, T. Stutzle, V. Trianni, E. Tuci, A. E. Turgut, and F. Vaussard, “Swarmanoid: A novel concept for the study of heterogeneous robotic swarms,” _IEEE Robotics Automation Magazine, vol. 20, no. 4, pp. 60-71_ , 2013.
  * [35] M. Saska, V. Vonásek, T. Krajník, and L. Preucil, “Coordination and navigation of heterogeneous mav–ugv formations localized by a ‘hawk-eye’-like approach under a model predictive control scheme,” _The International Journal of Robotics Research_ , vol. 33, pp. 1393 – 1412, 2014.
  * [36] C. Pinciroli, A. Lee-Brown, and G. Beltrame, “A tuple space for data sharing in robot swarms,” in _9th EAI International Conference on Bio-inspired Information and Communications Technologies (BICT 2015)_. European Union Digital Library, May 2016. [Online]. Available: https://publications.polymtl.ca/4727/


# Skeletal Cut Loci on Convex Polyhedra

Joseph O’Rourke  Costin Vîlcu

###### Abstract

The _cut locus_ ${\mathcal{C}}(x)$ on a convex polyhedron $P$ with respect to
a point $x$ is a tree of geodesic segments (shortest paths) on $P$ that
includes every vertex. In general, edges of ${\mathcal{C}}(x)$ are not edges
of $P$, i.e., not part of the _$1$ -skeleton_ ${\operatorname{Sk}}(P)$ of $P$.
We say that $P$ has a _skeletal cut locus_ if there is some $x\in P$ such that
${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$. In this paper we study
skeletal cut loci, obtaining three main results.

First, given any combinatorial tree $T$, there exists a convex polyhedron $P$
and a point $x$ with a skeletal cut locus that matches the combinatorics of
$T$. Second, any (non-degenerate) polyhedron $P$ has at most a finite number
of points $x$ for which ${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$.
Third, we show that almost all polyhedra have no skeletal cut locus.

Because the source unfolding of $P$ with respect to $x$ is always a non-
overlapping net for $P$, and because the boundary of the source unfolding is
the (unfolded) cut locus, source unfoldings of polyhedra with skeletal cut
loci are edge-unfoldings, and moreover “blooming,” avoiding self-intersection
during an unfolding process.

##  1 Introduction

Our focus is the cut locus ${\mathcal{C}}(x)$ on a convex polyhedron, and the
relationship of ${\mathcal{C}}(x)$ to the _$1$ -skeleton_ of $P$—the graph of
vertices and edges—which we denote by ${\operatorname{Sk}}(P)$. The cut locus
${\mathcal{C}}(x)$ is the closure of the set of points on $P$ to which there
is more than one geodesic segment (shortest path) from $x$. ${\mathcal{C}}(x)$
is a tree whose leaves are vertices of $P$. ${\mathcal{C}}(x)$ is a spanning
tree of the vertices; it may contain vertices of degree-$2$. Nodes of degree
$k\geq 3$ are _ramification points_ to which there are $k$ distinct geodesic
segments from $x$.

The $1$-skeleton of a non-degenerate polyhedron is a $3$-connected graph by
Steinitz’s theorem. We call a doubly-covered convex polygon a _degenerate_
convex polyhedron, for which the $1$-skeleton is a cycle. In general there
seems to be little relation between the cut locus and the $1$-skeleton. We say
that $P$ has a _skeletal cut locus_ if there is some $x\in P$ such that
${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$.

The edges of ${\mathcal{C}}(x)$ are known to be geodesic segments [AAOS97], so
it is at least conceivable that an edge of ${\mathcal{C}}(x)$ lies along an
edge of $P$. Theorem 1 shows that, for certain $P$ and points $x$, all of
${\mathcal{C}}(x)$ lies in the $1$-skeleton of $P$:
${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$.

As a simple example, we will see in Lemma 4 that the three edges incident to a
vertex $v_{i}$ of a tetrahedron form ${\mathcal{C}}(x)$ for an appropriate
$x$, and are therefore skeletal cut loci.

###### Example 1

Another example is shown in Fig. 1, where $T$ has one node $a$ at the apex of
degree-$4$, eight degree-$2$ nodes, and four leaves.

Figure 1: A polyhedron $P$ with a skeletal cut locus. The top is a regular
pyramid. Underneath are frustums. ${\mathcal{C}}(x)$ shown red; $x$ is at the
center of the bottom face.

Although Theorems 2 and 3 will show that skeletal cut loci are “rare” in
senses we’ll make precise, Theorem 1 and its proof establish that uncountably
many polyhedra do admit skeletal cut loci (Proposition 1).

Theorem 1 can be viewed as a companion to the result in [OV23], where we
proved that any _length tree_ —a tree with specified edge lengths—can be
realized as the cut locus on some polyhedron. Here we only match the
combinatorics of $T$, not metrical properties, but requiring additionally for
$T$ to be included in ${\operatorname{Sk}}(P)$.

##### Connection to Unfolding.

It has long been known that cutting the cut locus ${\mathcal{C}}(x)$ and
unfolding to the plane leads to the non-overlapping _source unfolding_ : If
$x$ is not itself at a vertex, then the unfolding arrays all the shortest
paths $2\pi$ around $x$, with the image of the cut locus forming the boundary
of the unfolding [Mou85] [SS86]. For the polyhedra in Theorem 1, the source
unfolding is an edge-unfolding. And because it is known that the source
unfolding can be _bloomed_ —unfolded continuously from ${\mathbb{R}}^{3}$ to
${\mathbb{R}}^{2}$ without self-intersection [DDH+11]—Theorem 1 and its
companion Proposition 1 provide perhaps the first infinite class of examples
of blooming edge-unfoldings.

Our central open problem (Section 1.4) asks for an accounting of all the
polyhedra $P$ that support a skeletal cut locus. All of these enjoy the
property that source unfoldings are also blooming edge-unfoldings.

###  1.1 Theorem 1 Construction

In this section we prove Theorem 1:

###### Theorem 1

Given any combinatorial tree $T$, there is a convex polyhedron $P$ and a point
$x\in P$ such that the cut locus ${\mathcal{C}}(x)$ is entirely contained in
${\operatorname{Sk}}(P)$, and the combinatorics of ${\mathcal{C}}(x)$ match
the given $T$.

We first illustrate the main idea of the construction before addressing
details. Suppose the given tree $T$ is the $7$-leaf tree shown in Fig. 2. We
select a degree-$3$ node as root $a$, which corresponds to the apex of a
regular tetrahedron $av_{1}v_{2}v_{3}$. We fix $x$ at the centroid of the base
$Q$.

Figure 2: Tree $T$ with $7$ leaves.

Fig. 4 show one possible construction of $P$. The edges incident to $a$ are
clearly in ${\mathcal{C}}(x)$ with $x$ at the centroid of the base triangle.
All three base vertices of the tetrahedron are then truncated, with the
truncation of $v_{1}$ truncated a second time. Now $T$ corresponds to all the
non-base edges of $P$.

The truncations are not arbitrary: the truncation planes must have precise
tilts in order for the edges of each truncation to lie in ${\mathcal{C}}(x)$.
Fig. 4 shows the source unfolding of $P$, with $a_{1},a_{2},a_{3}$ the three
images of $a$. The red bisector rays from $x$ through the truncation vertices
on the base $Q$ suggest that indeed any point $p$ on a truncation edge is
equidistant from $x$ and therefore on ${\mathcal{C}}(x)$.

Figure 3: $P$ is created from a regular tetrahedron by four vertex
truncations.

Figure 4: Source unfolding of $P$ from $x$. Bisectors shown red.

Returning to the need for precise tilts of the tuncation planes, let $z$ be
the point on the edge $av_{1}$ through which the truncation plane passes,
creating a truncation triangle $zt_{1}t_{2}$. As indicated in Fig. 5, the tilt
is uniquely determined by the location of $z$: the placement of $z$ determines
$t_{1},t_{2}$, and the edge $t_{1}t_{2}$ determines $z$.

Figure 5: The tilt of the truncation plane is determined by the position of
$z$.

###  1.2 Cut locus preliminaries

For the readers convenience, we list next several basic properties of cut
loci, sometimes use implicitly in the following.

  1. (i)

${\mathcal{C}}(x)$ is a tree drawn on the surface of $P$. Its leaves are
vertices of $P$, and all vertices of $P$, excepting $x$ (if it is a vertex)
are included in ${\mathcal{C}}(x)$. All points interior to ${\mathcal{C}}(x)$
of degree $3$ or more are known as _ramification points_ of
${\mathcal{C}}(x)$. All vertices of $P$ interior to ${\mathcal{C}}(x)$ are
also considered as ramification points, of degree at least $2$.

  2. (ii)

Each point $y$ in ${\mathcal{C}}(x)$ is joined to $x$ by as many geodesic
segments as the number of connected components of
${\mathcal{C}}(x)\setminus{y}$. For ramification points in ${\mathcal{C}}(x)$,
this is precisely their degree in the tree.

  3. (iii)

The edges of ${\mathcal{C}}(x)$ are geodesic segments on $P$.

  4. (iv)

Assume the distinct geodesic segments ${\gamma}$ and ${\gamma}^{\prime}$ from
$x$ to $y\in C(x)$ are bounding a domain $D$ of $P$, which intersects no other
geodesic segment from $x$ to $y$. Then there is an arc of ${\mathcal{C}}(x)$
at $y$ which intersects $D$ and bisects the angle of $D$ at $y$.

  5. (v)

If the tree ${\mathcal{C}}(x)$ is reduced to a path, the polyhedron is a
doubly-covered (planar) convex polygon, with $x$ on the rim.

Further details can be found in [OV24, Ch. 2].

###  1.3 Construction Details

If the given $T$ has no nodes of degree $\geq 3$, then it must be path, say of
$n$ edges. Then $P$ a doubly-covered convex $(n+1)$-gon satisfies Theorem 1
with $x$ on the interior of any edge. So henceforth assume $T$ has at least
one node of degree $n\geq 3$. Start with $P$ a pyramid with apex $a$ centered
over a regular $n$-gon base $Q$, with $x$ the centroid of $Q$. Label the
vertices of $Q$ as $v_{1},\ldots,v_{n}$.

####  1.3.1 No degree-$2$ nodes

The construction is a bit different when $T$ has degree-$2$ nodes, so we defer
that case to Section 1.3.2, and assume in this section that $T$ has no
degree-$2$ nodes.

The construction does not depend on the degree of apex $a$, so it is no loss
of generality to assume $a$ has degree-$3$ so that $P$ starts as a regular
tetrahedron. Let $z$ be a node of $T$ adjacent to $a$. (We will often use $a$
and $z$ and other variables to both refer to a node of $T$ and a corresponding
vertex of $P$.) Let $z$ have degree $k+2$ in $T$. Truncation of $k$ planes
through $z$ will create a vertex at $z$ of degree $k+2$. E.g., if $z$ is
degree-$3$, $k=1$ plane through $z$ creates a vertex of degree-$3$, as we’ve
seen in earlier figures

We aim to understand how to truncate $k\geq 1$ planes through $z$ so that the
$k+1$ truncation edges incident to the base $Q$ are part of
${\mathcal{C}}(x)$. We will illustrate in detail the case $k=2$ shown in Fig.
7. Looking ahead, if we know how to construct $k$ planes through $z$, then we
can apply the same logic to construct $j$ planes through a child $y$ of $z$.
The $j=1$ case is illustrated in Fig. 7, with the red truncation triangle
incident to $y$. Then the same construction technique can be used to
inductively create the full subtree rooted at $z$. We will show later that the
subtrees rooted at the other two children of $a$ can be arranged to avoid
interfering with one another.

Figure 6: $k=2$ truncation planes through $z$.

Figure 7: $k=2$, $j=1$. The $y$-truncation cuts the $zt_{2}$ edge in Fig. 7.

We express the construction as a multi-step algorithm, and later prove that
the truncation edges are in ${\mathcal{C}}(x)$. Fix $k\geq 1$, and position
$z$ anywhere in the interior of $av_{1}$. The goal is to compute the
_truncation chain_ $t_{1},t_{2},\ldots,t_{k},t_{k+1}$ on base $Q$, where
$t_{1}\in v_{1}v_{n}$ and $t_{k+1}\in v_{1}v_{2}$ (in Fig. 7,
$t_{1},t_{2},t_{3}$). Each truncation triangle is then $zt_{i}t_{i+1}$.

The construction of the truncation chain is effected by first computing the
unfolded positions $z_{i}$, the images of $z$ in the unfolding. It is perhaps
counterintuitive, but we can calculate $z_{i}$ without knowing $t_{i}t_{i+1}$;
instead we use $z_{i}$ to calculate $t_{i}t_{i+1}$. The next construction
depends of our choice of several parameters; we’ll see later that it provides
a suitable polyhedron.

  1. (1)

$z_{0}$ is the position of $z$ unfolded with the left face of the tetrahedron,
$av_{3}v_{1}$. $z_{0}$ can be determined by $|v_{1}z|=|v_{1}z_{0}|$. Then
$z_{k+1}$ is the reflection of $z_{0}$ across $xv_{1}$.

  2. (2)

Set $r_{z}=|xz_{0}|=|xz_{k+1}|$.

  3. (3)

All the $z_{i}$’s are chosen to lie on the circle $C_{z}$ centered on $x$ of
radius $r_{z}$.

  4. (4)

Let $A$ be the angle $z_{0}xz_{k+1}$. Partition $A$ into $k+1$ angles
${\alpha}$. This is another choice, to maximize the symmetry of the
construction.

  5. (5)

The $z_{i}$’s lie on rays from $x$ separated by ${\alpha}$. Together with
$C_{z}$, this determines the location of the $z_{i}$’s.

  6. (6)

Set $B_{i}$ to bisect the angle at $x$ between the $z_{i-1},z_{i}$ rays,
$i=1,\ldots,k+1$.

  7. (7)

We determine $t_{1}$ and $t_{k+1}$ using the first and last bisector:
$t_{1}=v_{1}v_{n}\cap B_{1}$. $t_{k+1}=v_{1}v_{2}\cap B_{k+1}$. The
intermediate chain vertices $t_{2},\ldots,t_{k}$ are not yet determined.

  8. (8)

Let $\Pi_{i}$ be the mediator plane through $zz_{i}$, the plane orthogonal to
$zz_{i}$ through its midpoint. It is these planes that determine $t_{i}$,
$i=2,\ldots,k$.

  9. (9)

$\Pi_{i}$ intersects the $xy$-plane in a line $L_{i}$ containing
$t_{i}t_{i+1}$.

  10. (10)

$t_{i}=L_{i}\cap B_{i}$.

First note that the mediator plane construction of $t_{i}t_{i+1}$ guarantees
that $z$ unfolds to $z_{i}$. Second, the angles between edges $t_{i}z_{i-1}$
and $t_{i}z_{i}$ are split by $B_{i}$ by construction. So any point $p$ on the
interior of edge $zt_{i}$ unfolds to two images in the plane equidistant from
$x$.

###### Lemma 1

Each truncation edge $zt_{i}$ is an edge of ${\mathcal{C}}(x)$.

Proof: We first prove that $zt_{1}$ lies in ${\mathcal{C}}(x)$. Throughout
refer to Fig. 8.

Before truncation, the segment $zt_{1}$ lies on the face $av_{3}v_{1}$ of the
polyhedron $P$, which is a regular tetrahedron in this case.

Fix a point $p\in zt_{1}$. The unique shortest path ${\gamma}$ to $p$ crosses
edge $v_{1}v_{3}$. After truncation, ${\gamma}$ remains a geodesic arc. We aim
to prove that it remains shortest, and moreover there is another companion
geodesic segment ${\gamma}^{\prime}$, establishing that
$p\in{\mathcal{C}}(x)$.

Now we consider the situation after truncation. Let ${\delta}$ be a geodesic
arc from $x$ to $p$, approaching $p$ from the other side of $zt_{1}$. If
${\delta}$ crosses the edge $t_{1}t_{2}$, then we have $|{\gamma}|=|{\delta}|$
by construction, and we have found ${\gamma}^{\prime}={\delta}$.

Suppose instead that ${\delta}$ crosses edge $t_{i}t_{i+1}$ for $i\geq 2$, and
then crosses the truncation triangles
$zt_{i}t_{i+1},zt_{i-1}t_{i},\ldots,zt_{1}t_{2}$ (right to left, i.e.,
clockwise, in Fig. 8(a)) before reaching $p$. To simplify the discussion, we
illustrate $i=2$, so ${\delta}$ crosses $t_{2}t_{3}$ and then triangles
$zt_{2}t_{3}$ and $zt_{1}t_{2}$. See Fig. 8(b).

Let $q_{2}$ be the quasigeodesic $xt_{2}z$ on $P^{\prime}$; it must be crossed
by ${\delta}$ to reach $p$. There are two triangles $xt_{2}z_{1}$ and
$xt_{2}z_{2}$ bounding $q_{2}$ to either side, congruent by the construction.
Thus the construction has local intrinsic symmetry about $q_{2}$.

Figure 8: Proof that $p\in zt_{1}$ is on ${\mathcal{C}}(x)$. (a) Quasigeodesic
$q_{2}=xt_{2}z$ shown purple and congruent triangles $xt_{2}z_{1}$ and
$xt_{2}z_{2}$ shaded green. (b) Abstract picture depicting geodesic segments
${\gamma},{\delta},{\delta}^{\prime}$.

Let $s$ be the point at which ${\delta}$ crosses $t_{2}t_{3}$,
$\\{s\\}={\delta}\cap t_{2}t_{3}$. First assume that $s$ lies in the triangle
$xt_{2}z_{2}$. Then ${\delta}$ remains in $xt_{2}z_{2}$ until it crosses
$q_{2}$. Then there must be another geodesic arc ${\delta}^{\prime}$ symmetric
with ${\delta}$ about $q_{2}$, as illustrated in (b). So ${\delta}$ and
${\delta}^{\prime}$ meet at a point of $q_{2}$. Because ${\delta}$ and
${\delta}^{\prime}$ have the same length, neither can be a shortest path
beyond that point of intersection. Therefore ${\delta}$ cannot reach $p$ as a
geodesic segment.

Second, if $s$ instead lies in the triangle $xt_{3}z_{2}$, then it is clear
from the planar image in (a) of the figure that ${\delta}$ cannot cross the
segment $xz_{2}$ clockwise, which it must to reach $p$ from the right in the
figures. So ${\delta}$ must head counterclockwise, crossing $q_{3}=xt_{3}z$.
Then the same argument applies, based this time on the local intrinsic
symmetry about $q_{3}$, and shows that ${\delta}$ cannot be a shortest path
beyond $q_{3}$.

We have established that every point $p$ on $zt_{1}$ is on ${\mathcal{C}}(x)$,
and so $zt_{1}\subset{\mathcal{C}}(x)$. The same argument applies to
$zt_{k+1}$, the rightmost truncation edge in the figures.

So now we know that two geodesic segments from $x$ to $z$ cross $t_{1}t_{2}$
and $t_{k}t_{k+1}$. These two segments determine a digon $D$ within which the
remaining segments of ${\mathcal{C}}(x)$ lie. But within $D$ we have local
intrinsic symmetry with respect to the quasigeodesics $q_{i}=xt_{i}z$, because
$q_{i}$ is surrounded by the congruent triangles $xt_{i}z_{i-1}$ and
$xt_{i}z_{i}$. Therefore, the previous argument shows that all the edges
$zt_{i}$ are included on $C(x)$.

We now return to the claim that the three subtrees descendant from $a$ do not
interfere with one another.

###### Lemma 2

The truncations for one subtree descendant of apex $a$ do not interfere with
another subtree descendant.

Proof: First, as $k\to\infty$, $t_{1}$ approaches the line $xz_{0}$. This is
evident in Fig. 14 where $k=8$. Thus the leftmost truncation triangle stays to
the $v_{1}$-side of the midpoint of $v_{1}v_{3}$, say by ${\varepsilon}$.
Second, subsequent truncations to all but the extreme edges $zt_{1}$ and
$zt_{k+1}$ stay inside the $t_{1},\ldots,t_{k}$ chain. The only concern would
be that truncation of the $zt_{1}$ edge crossed the midpoint of $v_{1}v_{3}$
(and so possibly interfering with truncations of $av_{3}$). However, as is
evident in the earlier Fig. 5, the position of $t_{1}$ moves monotonically
toward $v_{1}$ as $z$ moves down $av_{1}$. Thus we can widen ${\varepsilon}$
to accommodate a truncation of $zt_{1}$ (or of $zt_{k+1}$). So the entire
subtree rooted at $z$ stays between the midpoints of $v_{1}v_{3}$ and
$v_{1}v_{2}$.

Further examples are shown in Appendix A: $k=4$ in Figs. 12 and 12, and $k=8$
in Figs. 14 and 14.

####  1.3.2 Degree-$2$ nodes

We turn now to degree-$2$ nodes.

###### Lemma 3

A degree-$2$ vertex $u$ can realized by modifying the construction that
achieves Lemma 1.

Proof: It will suffice to show how to deal with a degree-$2$ node $u$ a child
of $a$ in the tree $T$, and $z$ a child of $u$ of degree $\geq 3$. The
construction inductively generalizes to arbitrary placements of degree-$2$
nodes.

So let $u$ be on edge $av_{1}$ but $z$ on edge $uv^{\prime}_{1}$, where
$v^{\prime}_{1}\neq v_{1}$ is on the line segment $xv_{1}$. See Fig. 9. Thus
$u$ is a degree-$4$ vertex of $P$ but we want to arrange that two of its edges
are not part of ${\mathcal{C}}(x)$. The two segments $au$ and $uz$ are in
${\mathcal{C}}(x)$, as they lie on the vertical symmetry plane containing
$axv_{1}$.

Figure 9: $u$ is degree-$2$ node. $k=1$ truncation at $z$.

Note that the triangle $uzt_{1}$ is not coplanar with the left face
$v_{3}t_{1}ua$. Still, when we truncate through $z$, cut the truncation edges
and unfold, that triangle $uzt_{1}$ unfolds attached to the unfolding of the
left face. We perform the same calculations to truncate $k$ times at $z$, and
the same logic (bisectors $B_{i}$ and mediator planes $\Pi_{i}$) leads to the
conclusion that the truncation edges are part of ${\mathcal{C}}(x)$.

The two side edges $ut_{1}$ and $ut_{k+1}$ are not part of ${\mathcal{C}}(x)$:
a point $p\in ut_{1}$ is closer to $x$ via a geodesic segment up the left
face, closer than any other path from $x$ to $p$. So $u$ has degree-$4$ in
${\operatorname{Sk}}(P)$ but degree-$2$ in ${\mathcal{C}}(x)$.

Lemmas 1, 2, and 3 together establish Theorem 1:
${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$ matches the given $T$.

###  1.4 Theorem 1 Discussion and Open Problem

We mentioned in Section 1 that Theorem 1 leads to an uncountable number of
skeletal polyhedra. This follows immediately from the freedom to place $z$ at
any point interior to $av_{1}$ in the construction detailed in Section 1.3. We
can be more quantitatively precise, as follows.

Assume that $T$ is a cubic tree without degree-$2$ nodes, so it has $n$ leaves
and $n-2$ ramification points. Aside from the first ramification point, which
is chosen as the apex of the starting tetrahedron, all others are free to vary
on their respective edges in our construction, which implies $n-3$ free
parameters. Because ${\mathcal{C}}(x)$ is skeletal, each ramification point of
$T$ is a vertex of $P$, so $P$ has $V=2n-2$ vertices, and $n=V/2+1$. Since the
space of all convex polyhedra with $V$ vertices, up to isometries, has
dimension $3V-6$ (see for example [LP22]), we have the next result.

###### Proposition 1

The set of convex polyhedra admitting skeletal cut loci—and hence blooming
edge-unfoldings—contains a subset of dimension $\geq V/2-2$ in the
$(3V{-}6)$-dimensional space of all convex polyhedra with $V$ vertices, up to
isometries.

If $T$ has no degree-$2$ nodes, then our construction for Theorem 1 results in
a _dome_ , a convex polyhedron $P$ with a distinguished base face $Q$, with
every other face sharing an edge with $Q$. It was already known that domes
have edge-unfoldings [DO07, p. 325], although the proof of non-overlapping for
our domes is almost trivial—the source unfolding does not overlap.

If $T$ has degree-$2$ nodes, our construction results in what we called in
[OV24] _g-domes_ , slight generalizations requiring that every face to share
at least a point with base $Q$. In Fig. 9, triangle $uzt_{1}$ shares just the
vertex $t_{1}$ with $Q$.

Beside the g-domes we have constructed, other convex polyhedra may well have
skeletal cut loci, see e.g., Example 1. Our main open question is: Which do?

###### Open Problem 1

Characterize all convex polyhedra $P$ which admit skeletal cut loci.

As motivation for the following considerations, note that every such $P$ has a
blooming edge-unfolding, for the same reasons as do the constructed g-domes:
The source unfolding is a net, and the boundary of the source unfolding is an
image of the cut locus, cut along edges of ${\operatorname{Sk}}(P)$.

The remainder of the paper addresses and partially answers Problem 1,
completing Proposition 1.

##  2 Several Skeletal Cut Loci

Beside the previous open problem, several natural questions suggest
themselves:

  1. (1)

For a fixed $P$, how many distinct points $x$ can lead to skeletal cut loci?
(Theorem 2).

  2. (2)

Can all of ${\operatorname{Sk}}(P)$ for a given $P$ be covered by several cut
loci? (Proposition 2).

  3. (3)

How common / rare are skeletal cut loci in the space of all convex polyhedra?
(Theorem 3).

In the first two questions above, degenerate $P$ play a special role:

###### Proposition 2

  1. (a)

There exists infinitely many points $x$ with
${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$ if and only if $P$ is
degenerate.

  2. (b)

There exists two points $x_{1},x_{2}$ on $P$ whose cut loci together cover
${\operatorname{Sk}}(P)$ if and only if $P$ is degenerate.

Theorem 2 is then a corollary of claim (a). Before arguing for a quantitative
statement of this theorem, we make two observations. First, for $P$
degenerate, ${\operatorname{Sk}}(P)$ is the rim of $P$, and for any $x$ on the
rim, ${\mathcal{C}}(x)$ is a subset of ${\operatorname{Sk}}(P)$. So one
direction (a) of the proposition is trivial. Second, a special case asks
whether it could be that each vertex $v$ of $P$ leads to a skeletal cut locus
${\mathcal{C}}(v)$. The answer is yes, realized, for example, by the regular
octahedron.

###### Theorem 2

For non-degenerate $P$ with $E$ edges, there are at most $2{E\choose 2}$ flat
points $x$ of $P$ such that ${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$.

Proof: (of the Theorem). Assume there exists a flat point $x$ of $P$, such
that ${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$. Then $x$ belongs to one
or two faces, $x\in F_{j}$, with $j\in\\{1,2\\}$. Let $F$ denote either
$F_{1}$ if $j=1$, or the union $F_{1}\cup F_{2}$ if $j=2$.

Denote by $v_{i}$, $i\geq 3$, the vertices of $F$, and by $e_{i}$ the edge of
${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$ incident to $v_{i}$ and not
included in $F$. Finally, denote by ${\gamma}_{i}$ the geodesic segment from
$x$ to $v_{i}$.

Because $e_{i}\subset C(x)$, ${\gamma}_{i}$ and $e_{i}$ together bisect the
complete angle at $v_{i}$, by the bisection property (iv) of the cut locus. In
other words, the straight extensions $E_{i}$ into $F$ by all $e_{i}$ are
concurrent: they intersect at the point $x$.

Now we count all the possible locations $x$ over all edges of $P$. Consider a
pair of edges $e_{i},e_{j}$. Each has possible edge extensions from each
endpoint. So the edge extensions are geodesic rays. Two such straight
extensions could intersect several times on $P$. However, only their first
intersection beyond the endpoints is a possible location for $x$. Each edge
has two extensions, one from each endpoint, and because there are $E$ straight
extensions of the $E$ edges of $P$, there are at most $2{E\choose 2}$ possible
locations for $x$.

So this theorem settles the other direction of Proposition 2(a).

Now we prove Proposition 2(b), that only degenerate $P$ allows covering
${\operatorname{Sk}}(p)$ by only two cut loci.

Proof: If $P$ is degenerate then any two points on its rim, but not on the
same edge, satisfy the conclusion.

Assume now that $P$ is non-degenerate and $x\in P$ such that
${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$. Then ${\mathcal{C}}(x)$ has
at least one ramification point of degree $d\geq 3$, as it is known that only
degenerate $P$ support path cut loci. The $d$ edges of ${\mathcal{C}}(x)$ lie
in at least $3$ faces of $P$. Then there exists a cycle in
${\operatorname{Sk}}(P)$, formed by edges of those faces which are not in
${\mathcal{C}}(x)$. But such a cycle cannot be covered by only one other cut
locus, which is a tree.

###### Example 2

Consider a regular dipyramid $P$ over a convex $2m+1$-gon; see Fig. 10. One
can see that, for every midpoint $x$ of a “base edge” $e$, ${\mathcal{C}}(x)$
is included in ${\operatorname{Sk}}(P)$. More precisely, $C(x)$ contains all
base edges other than $e$, and the two “lateral edges” opposite to $x$. In
particular, this provides $2m+1$ such points, for $V=2m+3$ vertices.

Figure 10: $P$: pentagonal dipyramid. ${\mathcal{C}}(x)$: red and blue edges
of ${\operatorname{Sk}}(P)$.

The following lemma will explain a condition in Theorem 3 to follow.

###### Lemma 4

Every tetrahedron $T$ has four points $x\in T$ such that
${\mathcal{C}}(x)\subset{\operatorname{Sk}}(T)$.

Proof: For each vertex $v_{i}$, denote by $x_{i}$ the ramification point of
$C(v_{i})$. It follows, from cut locus property (ii), that that $v_{i}$ is the
ramification point of $C(x_{i})$. Then, by (i) and (iii), $C(x_{i})$ consists
of the three edges incident to $v_{i}$.

The next theorem establishes the rarity of skeletal cut loci. In the
statement, by _almost all_ we mean “all in an open and dense set.”

###### Theorem 3

For almost all convex polyhedra $P$ with $V>4$ vertices, there exists no point
$x\in P$ with ${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$.

Note that Lemma 4 establishes the need for $V>4$.

Proof: Notice first that almost all convex polyhedra $P$ are non-degenerate.

Assume, for the simplicity of the exposition, that every face of $P$ is a
triangle and ${\operatorname{Sk}}(P)$ is a cubic graph.

Case 1.

Assume there exists a flat point $x$ interior to some face $F$ of $P$, such
that ${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$.

Repeating the notation in Theorem 2, denote by $v_{i}$, $i=1,2,3$, the
vertices of $F$, and by $e_{i}$ the edges of $P$ incident to $v_{i}$ and not
included in $F$. Moreover, denote by ${\gamma}_{i}$ the geodesic segment from
$x$ to $v_{i}$.

As in Theorem 2, it follows that $e_{i}\subset C(x)$ so, together,
${\gamma}_{i}$ and $e_{i}$ bisect the complete angle at $v_{i}$. In other
words, the straight extensions $E_{i}$ into $F$ by all the $e_{i}$ are
concurrent: they all intersect at the same point.

Now we perturb the vertices of $P$ to destroy this concurrence. If $P$ were a
tetrahedron, then perturbing the apex would simultaneously move the edges
incident to it. But the assumption that $V>4$ means that there are at least
two vertices outside the $3$-vertex face $F$ containing $x$. Perturbing these
two vertices independently moves the edges incident to $F$ independently,
breaking the concurrence at $x$.

Because there are at most finitely many such points $x$ by Theorem 2, the
conclusion follows in this case.

Case 2.

Assume there exists a flat point $x$ interior to some edge $e$ of $P$, such
that ${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$. Denote by $v_{i}$,
$i=1,2$, the vertices of $e$, and by $e_{i}$ the edges of $P$ incident to
$v_{i}$ included in ${\mathcal{C}}(x)$. As above, it follows that the straight
extensions of $e_{1},e_{2}$ coincide with $e$. Now, small perturbations of the
vertices of $P$ destroy this coincidence. Note that if $e,e_{1},e_{2}$ form a
triangle, then $e_{1},e_{2}$ will move together. But still, perturbations at
other vertices of $P$ (not $v_{1},v_{2},e_{1}\cap e_{2}$) will destroy the
concurrence.

Case 3.

Assume finally there exists a vertex $v$ of $P$, such that
$C(v)\subset{\operatorname{Sk}}(P)$. Here we obtain again that the straight
extensions of two edges contain (other) edge-pair extensions, and small
perturbations of the vertices of $P$ destroy this coincidence.

We mentioned that the octahedron has the property that for every vertex $v$,
${\mathcal{C}}(v)$ is skeletal. In Appendix B we detail the special conditions
such polyhedra must satisfy.

##  Appendix A Appendix: Theorem 1 Examples

Figure 11: $k=4$.

Figure 12: $k=4$, $j=3$.

Figure 13: $k=8$.

Figure 14: $k=8$, $j=1$.

##  Appendix B Every Vertex is a Skeletal Source

By Theorem 3, few convex polyhedra $P$ have a point $x$ with
${\mathcal{C}}(x)\subset{\operatorname{Sk}}(P)$. So assuming that every vertex
of $P$ has this property should yield some exceptional polyhedra.

###### Theorem 4

Assume that every vertex of $P$ has a skeletal cut locus. Then the following
statements hold.

  1. 1.

Every face of $P$ is a triangle.

  2. 2.

Every vertex of $P$ has even degree in ${\operatorname{Sk}}(P)$.

  3. 3.

The edges at every vertex $v$ split the complete angle at $v$ into evenly many
sub-angles, every two opposite such angles being congruent.

  4. 4.

If, moreover, every vertex of $P$ has degree $4$ in ${\operatorname{Sk}}(P)$
then $P$ is an octahedron:

     * •

with three planar symmetries, and

     * •

all faces of which are acute congruent (but not necessarily equilateral)
triangles.

Proof:

  1. (1)

Assume there exists a non-triangular face $F$ of $P$, so there are non-
adjacent vertices $u,v$ of $F$. Because $v\in
C(u)\subset{\operatorname{Sk}}(P)$, there exists an edge $vw$ of $P$ with
$vw\subset C(u)$. Moreover, the diagonal $uv$ of $F$ and $vw$ bisect the
complete angle at $v$.

Because $vw$ is an edge, it is a geodesic segment from $w$ to $v$. So $v$ is a
leaf of $C(w)$, and $C(w)$ starts at $v$ in the direction of the diagonal
$vu$, hence $C(w)\not\subset{\operatorname{Sk}}(P)$.

  2. (2)

Consider now a vertex $u$ of $P$ of degree $d$ in ${\operatorname{Sk}}(P)$,
and denote by $u_{1},\ldots,u_{d}$ its neighbors in ${\operatorname{Sk}}(P)$.

For every $u_{i}$, $i=1,\ldots,d$, $u$ is a leaf of $C(u_{i})$, so the edge
$u_{i}u$ and the edge of $C(u_{i})\cap{\operatorname{Sk}}(P)$ at $u$ bisect
the complete angle at $u$. Hence the edges at $u$ can be paired two-by-two,
hence their number is even.

  3. (3)

Denote by $e_{1},\ldots,e_{k},e_{k+1},\dots,e_{2k}$ the edges sharing the
vertex $u$, indexed circularly, and put ${\alpha}_{i}=\angle(e_{i},e_{i+1})$,
with index equality $2k+1=1$.

The bisecting property of cut loci implies that the edge $e_{1}$ (as a
geodesic segment from vertex $u_{1}$ to $u$) and the edge $e_{k+1}$ (as the
branch of $C(u_{1})$ at leaf $u$) bisect the complete angle at $u$:

$\sum_{i=1}^{k}{\alpha}_{i}=\sum_{i=1}^{k}{\alpha}_{k+i}.$

Similarly,

$\sum_{i=2}^{k+1}{\alpha}_{i}=\sum_{i=2}^{k+1}{\alpha}_{k+i}.$

Subtracting, we get ${\alpha}_{1}={\alpha}_{k+1}$.

Analogous reasoning implies the other equalities:
${\alpha}_{i}={\alpha}_{k+i}$, with index equality $2k+j=j$.

  4. (4)

For the combinatorial part, denote by $F,E,V$ the number of faces, edges, and
respectively vertices of $P$. Euler’s formula for convex polyhedra gives
$F-E+V=2$. Our assumptions imply $3F=2E$, and $4V=2E$. These equations yield
$V=6$ and $F=8$, hence $P$ is an octahedron.

Denote by $u,v,a,b,c,d$ the vertices of $P$, with $a,b,c,d$ neighbor to both
$u$ and $v$.

Applying the hypothesis for $a,b,c,d$ shows that the cycle $C=abcda$ in
${\operatorname{Sk}}(P)$ is a bisecting polygon. Therefore, there exists a
local isometry ${\iota}$ of the ‘upper’ and ‘lower’ neighborhoods
$N_{u},N_{v}$ of $C$. In particular, the curvatures at $u$ and $v$ are equal,
by Gauss-Bonnet.

It follows even more, that the local isometry ${\iota}$ extends to an
intrinsic isometry between the ‘upper’ and the ‘lower’ closed half-surfaces
bounded by $C$ (regarding them as cones), hence it further extends to an
isometry of $P$ fixing $C$. Therefore, $C$ is planar and $P$ is symetric with
respect to the respective plane, by the rigidity part of Alexandrov’s Gluing
Theorem.

Repeating the reasoning for other pairs of ‘opposite’ vertices shows that all
faces of $P$ are congruent triangles.

The four faces sharing the vertex $u$ have congruent angles at $u$, hence
those angles are acute.

###### Example 3

Suitable dipyramids over convex $2m$-gons, similar to Example 2, provide non-
octahedron polyhedra whose the cut loci of the vertices cover the
$1$-skeleton.

## References

  * [AAOS97] Pankaj K. Agarwal, Boris Aronov, Joseph O’Rourke, and Catherine A. Schevon.  Star unfolding of a polytope with applications.  SIAM J. Comput., 26:1689–1713, 1997.
  * [DDH+11] Erik D Demaine, Martin L Demaine, Vi Hart, John Iacono, Stefan Langerman, and Joseph O’Rourke.  Continuous blooming of convex polyhedra.  Graphs and Combinatorics, 27:363–376, 2011.
  * [DO07] Erik D. Demaine and Joseph O’Rourke.  Geometric Folding Algorithms: Linkages, Origami, Polyhedra.  Cambridge University Press, 2007.  http://www.gfalop.org.
  * [LP22] Nina Lebedeva and Anton Petrunin.  Alexandrov’s embedding theorem.  arXiv:2212.10479, 2022.
  * [Mou85] David M. Mount.  On finding shortest paths on convex polyhedra.  Technical Report 1495, Dept. Computer Science, Univ. Maryland, 1985\.
  * [OV23] Joseph O’Rourke and Costin Vîlcu.  Cut locus realizations on convex polyhedra.  Comput. Geom.: Theory & Appl., 114, 2023.  doi.org/10.1016/j.comgeo.2023.102010.
  * [OV24] Joseph O’Rourke and Costin Vîlcu.  Reshaping Convex Polyhedra.  Springer-Verlag, 2024.  ISBN 978-3-031-47510-8. To appear.
  * [SS86] Micha Sharir and Amir Schorr.  On shortest paths in polyhedral spaces.  SIAM J. Computing, 15(1):193–215, 1986.