University of Aizu,
Japanviglietta@gmail.comhttps://orcid.org/0000-0001-6145-4602 Mathematics of
computing Geometric topology Mathematics of computing Extremal graph theory

# Minimal Arrangements of Spherical Geodesics

Giovanni Viglietta

###### Abstract

We study arrangements of geodesic arcs on a sphere, where all arcs are
internally disjoint and each arc has its endpoints located within the interior
of other arcs. We establish fundamental results concerning the minimum number
of arcs in such arrangements, depending on local geometric constraints such as
_one-sidedness_ and _$k$ -orientation_.

En route to these results, we generalize and settle an open problem from CCCG
2022, proving that any such arrangement has at least two _clockwise swirls_
and at least two _counterclockwise swirls_.

###### keywords:

Minimal arrangement, spherical geodesic, visibility map, polyhedron, swirl
graph, one-sided, $k$-oriented

###### category:

##  1 Introduction

###  1.1 Art Gallery Problem and Spherical Diagrams

In Discrete and Computational Geometry, the _Art Gallery Problem_ asks how
many “light sources” are required to “illuminate” a given geometric
environment [7, 9]. The environment may be an enclosure, such as a polygon or
a polyhedron, or more broadly, a spatial arrangement of “opaque” objects that
obstruct light rays.

In recent years, a line of research on the Art Gallery Problem has focused on
illuminating $3$-dimensional polyhedra by choosing a subset of their edges as
light sources. In this setting, the facets of a polyhedron are interpreted as
opaque obstacles, and one wants to illuminate the polyhedron’s interior with
as few “edge lights” as possible [1, 2, 4, 11].

To this end, a technique developed in [4] involves selecting a small set of
edges whose endpoints collectively include all vertices of the polyhedron.
Interestingly, however, these edges may not be sufficient to fully illuminate
the polyhedron’s interior, as there is an abundance of polyhedra having
internal points that do not directly see any vertices [7, 12, 13]. We say that
such points are _vertex-hidden_. Thus, the study of vertex-hidden points and
the combinatorics of their visibility maps becomes central in [4], as well as
in the development of a general theory of visibility-related problems for
polyhedral objects in $3$-space [8].

In order to systematize these fundamental investigations, Spherical Occlusion
Diagrams (SODs) were introduced as a model for visibility maps of vertex-
hidden viewpoints relative to _polygonal scenes_ , i.e., arrangements of
interior-disjoint polygons in $3$-space [12, 13].

We give some preliminary definitions. A _geodesic arc_ on a sphere is the
unique shortest curve connecting two non-antipodal points. Clearly, any
geodesic arc lies within a great circle on the sphere. We say that a geodesic
arc $a$ _blocks_ a geodesic arc $b$ if an endpoint of $b$ lies in the relative
interior of $a$. If $a$ blocks $b$, we say that $b$ _hits_ $a$.

######  Definition 1.1.

A _Spherical Diagram (SD)_ is a finite non-empty collection $\mathcal{D}$ of
pairwise interior-disjoint geodesic arcs on the unit sphere in
$\mathbb{R}^{3}$, such that each arc of $\mathcal{D}$ is blocked by arcs of
$\mathcal{D}$ at each endpoint.

######  Definition 1.2.

A _Spherical Occlusion Diagram (SOD)_ is a Spherical Diagram $\mathcal{D}$
with the additional property that all arcs in $\mathcal{D}$ that hit the same
arc of $\mathcal{D}$ reach it from the same side.

Figure 1: A polygonal scene of six rectangles (left), where the central point
$v$ is vertex-hidden. The portion of each edge that is visible to $v$ is
radially projected onto a sphere centered at $v$, creating a geodesic arc. The
resulting visibility map is an SOD (right).

SDs may also be referred to as _two-sided_ arrangements of arcs, whereas SODs
are _one-sided_ , to stress the fact that their arcs are hit only from one
side (the term “one-sided” was previously used in [5] in the context of
rectangular layouts). While SODs were introduced and studied in [8, 12, 13],
in this paper we also set out to investigate SDs as a natural generalization.
Notably, most of what is currently known about SODs is more generally true of
SDs (refer to Section 2.1), and SDs are interesting geometric objects in their
own right.

As illustrated in Figure 1, the visibility map of a vertex-hidden viewpoint in
a polygonal scene is necessarily an SOD (see [13]). Interestingly, the
converse is not always the case, as was shown in [6]. Nonetheless, SODs were
instrumental in proving that any vertex-hidden viewpoint in a polygonal scene
must see at least eight distinct edges (this number reduces to six for
viewpoints that are not vertex-hidden). This result was obtained in [8] by
showing that any SOD consists of at least eight arcs. In turn, this follows
from the observation that any SOD (in fact, any SD) must have at least four
_swirls_ , which are defined next.

######  Definition 1.3.

A _swirl_ in an SD is a cycle of arcs, each of which hits the next (and such
that the last hits the first), going either all clockwise or all
counterclockwise. The _degree_ of a swirl is the number of arcs constituting
it.

As an example, the SOD in Figure 1 has four clockwise swirls and four
counterclockwise swirls, all of degree three.

###  1.2 Polyhedra with Restricted Edge Orientations

In the study of the Art Gallery Problem, it is customary to investigate not
only polygons or polyhedra in their full generality, but also specific
subclasses with particular geometric properties. For example, alongside
general polyhedra, also _orthogonal polyhedra_ have been considered (Figure
2(a)): these are polyhedra whose faces meet at right angles [1, 2, 11].

Similarly, a _$k$ -face-oriented_ polyhedron has the property that there exist
$k$ unit vectors such that the normal of each face is parallel to one of these
vectors [10]. Note that orthogonal polyhedra are $3$-face-oriented, and any
polyhedron is $k$-face-oriented for a large-enough $k$.

In the same vein, we may define a polygonal scene to be _$k$ -edge-oriented_
if there exist $k$ unit vectors such that every edge of every polygon in the
scene is parallel to one of the vectors. Again, any orthogonal polyhedron is a
$3$-edge-oriented polygonal scene; in general, any $k$-face-oriented
polyhedron is also a ${k\choose 2}$-edge-oriented polygonal scene (Figure
2(c)).

(a)

(b)

(c)

Figure 2: (a) An orthogonal polyhedron. (b) A $7$-edge-oriented polyhedron
having only vertical and horizontal edges (and faces). (c) A $4$-face-oriented
and $6$-edge-oriented polyhedron.

Following the seminal result of [8] mentioned in Section 1.1, our motivating
question is: What is the minimum number of edges that are necessarily visible
to a vertex-hidden viewpoint in a $k$-edge-oriented polygonal scene? In order
to model the visibility maps of such viewpoints, we give the following
definition.

######  Definition 1.4.

An SD $\mathcal{D}$ is _$k$ -oriented_ if there exists a set $P$ of $k$ points
on the unit sphere, called _poles_ , no two of which are antipodal, as well as
a function $f\colon\mathcal{D}\to P$ such that each arc $a\in\mathcal{D}$ is
collinear with the pole $f(a)$, but contains neither $f(a)$ nor its antipodal
point.

With the notation of Definition 1.4, we refer to the point antipodal to a pole
$p\in P$ as the _anti-pole_ of $p$. Also, for any arc $a\in\mathcal{D}$, the
pole $f(a)$ and its anti-pole $-f(a)$ are said to be the _vanishing points_ of
$a$.111The term “vanishing point” comes from perspective theory, and indicates
a point where parallel lines in $3$-space appear to converge when projected
onto a surface such as a plane or, in this case, a sphere. If three of the $k$
poles are linearly dependent (as unit vectors), then $\mathcal{D}$ is said to
be _degenerate_. Otherwise, $\mathcal{D}$ is _non-degenerate_.

It is immediate to recognize that the visibility map of any vertex-hidden
point of a $k$-edge-oriented polygonal scene is a $k$-oriented SOD. The
converse is not true in general (a counterexample is found in [6]), but it may
be true for sufficiently small values of $k$.

Thus, we recast our motivating question: What is the minimum number of arcs
that a $k$-oriented SD or SOD can have? While this formulation may not be
strictly equivalent to the one about polygonal scenes, it stands as a question
of independent interest in extremal graph theory [3], because SDs can be
characterized as spherical drawings of certain graphs. Consider a non-empty
$3$-regular planar graph $G$ that can be drawn on a sphere by means of
internally disjoint geodesic arcs in such a way that each vertex of $G$ is
incident to two collinear arcs, and any chain of such collinear arcs is itself
a geodesic arc. Such a drawing coincides with an SD in which no two arcs have
a common endpoint, and vice versa. For the purpose of minimizing arcs, this is
not a restrictive assumption on SDs; also, it is easy to see that minimizing
arcs in SDs is equivalent to minimizing vertices (or edges) in such graphs.
$k$-oriented SDs and SODs can be characterized in similar ways, as well.

###  1.3 Statement of Results

In this paper, we give a complete answer to the above question for all _non-
degenerate_ SDs and SODs. That is, for every $k$, we provide non-degenerate
$k$-oriented SDs and SODs having the minimum possible number of arcs.

We are also able to do so for _degenerate_ $k$-oriented SDs and SODs of all
possible configurations, provided that $k\leq 5$. For $k\geq 6$ we have
sporadic results, but classifying and analyzing the numerous degenerate
configurations of the poles remains a challenge.

In addition, we also determine the minimum number of _swirls_ that a
$k$-oriented SD or SOD may have in all of the aforementioned cases (with one
exception; see below).

Our results are summarized in Table 1.

$k$-orientation | alignment | swirls | SD arcs | SOD arcs
---|---|---|---|---
$3$-oriented | $(2,2,2)$ | $8$ | $12$ | $12$
$4$-oriented | $(2,2,2,3)$ | $6$ | $9$ | $11$
$4$-oriented | $(3,3,3,3)$ | $6$ | $9$ | $10$
$5$-oriented | $(2,2,2,2,4)$ | $6$ | $9$ | $11$
$5$-oriented | $(2,3,3,3,3)$ | $5$ | $8$ | $9$
$5$-oriented | $(3,3,3,4,4)$ |  $4$–$5$ | $8$ | $9$
$5$-oriented | $(4,4,4,4,4)$ | $4$ | $8$ | $9$
$(k\geq 6)$-oriented | $(2,2,\dots,2,k-1)$ | $6$ | $9$ | $11$
$6$-oriented | $(3,3,3,3,3,3)$ | $4$ | $6$ | $8$
$6$-oriented | $(3,3,3,4,4,4)$ | $4$ | $6$ | $8$
$6$-oriented | $(3,4,4,4,4,5)$ | $4$ | $6$ | $8$
$6$-oriented | $(4,4,4,5,5,5)$ | $4$ | $6$ | $8$
$(k\geq 6)$-oriented | $(\geq 5,\geq 5,\dots,\geq 5)$ | $4$ | $6$ | $8$
Table 1: Minimum numbers of swirls and arcs in $k$-oriented SDs (two-sided
arrangements) and SODs (one-sided arrangements), depending on their alignment.
The list includes all non-degenerate configurations for every $k$, as well as
all degenerate configurations up to $k=5$.

To uniformly describe degenerate and non-degenerate $k$-oriented SDs with
respect to the configuration of their poles, we use the concept of
_alignment_. A $k$-oriented SD with poles $p_{1}$, $p_{2}$, …, $p_{k}$ has
alignment $(d_{1},d_{2},\dots,d_{k})$ if, for every $1\leq i\leq k$, there are
exactly $d_{i}$ distinct great circles that contain $p_{i}$ and another pole
(we may assume $d_{1}\leq d_{2}\leq\dots\leq d_{k}$).

Therefore, non-degenerate $k$-oriented SDs have alignment
$(k-1,k-1,\dots,k-1)$. Another important alignment is $(2,2,\dots,2,k-1)$,
which corresponds to the visibility map of a polyhedron having only vertical
and horizontal edges (Figure 2(b)), as well as $(3,3,3,3,3,3)$, which
corresponds to the visibility map of a $4$-face-oriented polyhedron (Figure
2(c)).

Notably, for nearly all of the alignment configurations listed in Table 1,
there are SDs and SODs that simultaneously minimize the number of arcs and the
number of swirls. The only exceptions are $(3,3,3,4,4)$, where we do not know
if four swirls are possible, and $(4,4,4,4,4)$, where any SD or SOD minimizing
the number of arcs has five swirls (the minimum is four).

Although the last row of Table 1 was partially established in [8, 12, 13], a
question was left open: Does any SOD have at least two clockwise and two
counterclockwise swirls? In this paper we answer it in the affirmative, not
only for SODs, but more generally for all SDs.

The technical proofs of most preliminary results are found in Appendices B, C,
D and E. Concluding remarks and several open problems are in Appendix F.

##  2 Basic Constructions and Preliminary Results

###  2.1 Previous Results

We summarize all previous results on SDs (also see Appendix A). Proofs of the
following statements are found in [8, 13]; although they were stated and
proved only for SODs, the reader may verify that none of the proofs makes use
of the one-sidedness of the arrangements.

Every arc in an SD hits exactly two distinct arcs (one at each endpoint), and
no two arcs in an SD intersect in more than one point. The union of all the
arcs in an SD is a connected set. An SD with $n$ arcs partitions the unit
sphere into $n+2$ spherically convex regions called _tiles_ , and no tile
contains antipodal points. The union of the arcs of a swirl separates the unit
sphere in two regions, exactly one of which is spherically convex; this region
is called the _eye_ of the swirl. Given an SD, the interior of any great
semicircle on the unit sphere is crossed by at least one arc of the SD, and
the interior of any hemisphere contains the eye of at least one swirl. The
_swirl graph_ of an SD is the undirected multigraph on the set of swirls
having an edge between two swirls for every arc shared by them; this graph is
planar. Every SD has at least four swirls, including a clockwise one and a
counterclockwise one.

In addition to the above properties, SODs also enjoy the following ones. The
swirl graph of any SOD is simple, planar, and bipartite. Also, every SOD has
at least eight arcs.

(a)

(b)

Figure 3: (a) The area in yellow is the right-side region of a sliding walk.
The eye of a clockwise swirl (in purple) can be found within this region by
doing a right-handed sliding walk from its boundary. (b) The initial steps of
a clockwise walk with fulcrum $p$ (in red).

###  2.2 Sliding Walks

Let $\mathcal{D}$ be an SD, and let $D$ be the union of the arcs in
$\mathcal{D}$. Note that any point $p\in D$ lies in the interior of exactly
one arc $r(p)\in\mathcal{D}$. A _sliding walk_ on $\mathcal{D}$ is defined as
a continuous function $w\colon[0,+\infty)\to D$ such that, for every maximal
interval $I\subseteq[0,+\infty)$ with $|r(w(I))|=1$, $I$ is left-closed and
right-open, and $w$ restricted to $I$ is a unit-speed regular curve.

That is, a sliding walk continues to move in the same direction at unit speed
along the same arc $a\in\mathcal{D}$ until it reaches one of its endpoints.
Then it turns left or right into the (unique) arc hit by $a$, follows it until
one of its endpoints, and so on indefinitely.

Since an SD $\mathcal{D}$ has finitely many arcs, a sliding walk $w$ cannot be
an injective function, and there exists a minimum $x$ and a unique interval
$[x,x^{\prime}]\subset[0,+\infty)$ such that the restriction of $w$ to
$[x,x^{\prime}]$ is a simple closed curve (it is easy to see that either $x=0$
or $w(x)$ is an endpoint of an arc of $\mathcal{D}$). This curve separates the
unit sphere into a _right-side region_ and a _left-side region_. Note that
these two regions are well defined and unique for any sliding walk.

A _right-handed walk_ (resp., _left-handed walk_) is a sliding walk that
always turns right (resp., left) upon hitting a new arc.

The right-side region (resp., left-side region) of any right-handed walk
(resp., left-handed walk) on an SD $\mathcal{D}$ coincides with the eye of a
clockwise swirl (resp., counterclockwise swirl) of $\mathcal{D}$.∎

The following lemma is illustrated in Figure 3(a); a complete proof is in
Appendix B.

######  Lemma 2.1.

The right-side region (resp., left-side region) of any sliding walk on an SD
$\mathcal{D}$ contains the eye of a clockwise swirl (resp., counterclockwise
swirl) of $\mathcal{D}$.∎

If $p$ is a point on the unit sphere, a _clockwise walk_ (resp.,
_counterclockwise walk_) with _fulcrum_ $p$ is a sliding walk that moves
clockwise (resp., counterclockwise) around $p$ in a weakly monotonic fashion,
without touching $p$ or the point $p^{\prime}$ antipodal to $p$.222In [13],
such a walk is called “monotonic walk”, and $p$ is called “pole”. We adopted a
different terminology in this paper to avoid confusion with the poles of
$k$-oriented SDs. In Figure 3(b), the initial steps of a clockwise walk with
fulcrum $p$ are shown.

We are ready to settle the open problem stated in [12, Conjecture 2], [13,
Conjecture 22], and [8, Section 6]. In fact, we prove it not only for all
SODs, but more generally for all SDs.

######  Theorem 2.2.

Any SD has at least two clockwise swirls and two counterclockwise swirls.

######  Proof 2.3.

Let $\mathcal{D}$ be an SD; it suffices to prove that $\mathcal{D}$ has two
clockwise swirls. Let $S$ be any clockwise swirl of $\mathcal{D}$ (found, for
instance, as in Section 2.2), and let $E$ be the eye of $S$. Let $p$ be any
point in the interior of $E$, and let $w$ be a counterclockwise walk with
fulcrum $p$ starting from the boundary of $E$.

Since $S$ is a clockwise swirl, whenever $w$ is in the interior of an arc
$a\in S$, it moves toward the endpoint of $a$ not on $E$. In particular, $w$
never reaches the interior of $E$, and therefore the left-side region of $w$
contains $E$. By Lemma 2.1, the right-side region of $w$ contains the eye of a
clockwise swirl, which cannot be $E$. Hence, $\mathcal{D}$ has a clockwise
swirl other than $S$.

###  2.3 Swirl Adjacency

The missing proofs of the results in this section are found in Appendix D.

Recall from Section 2.1 that the swirl graph of any SOD is simple, i.e., any
two swirls of an SOD can have at most one arc in common. Moreover, any arc can
contribute to at most two swirls. On the contrary, the swirl graph of a
general SD may actually be a non-simple multigraph. That is, two swirls in an
SD may share more than one arc, as shown in Figure 4(a). Also, a single arc of
an SD can contribute to up to four different swirls (one on each side of each
endpoint).

There are two essentially different ways in which two swirls may share
multiple arcs. The first configuration involves two _contiguous swirls_ whose
eyes are adjacent along an arc $a$ of the SD and also share an endpoint of
$a$. An example is given by the yellow and green swirls in Figure 4(a).

######  Proposition 2.4.

In any SD, pairs of contiguous swirls share exactly two arcs.∎

Even if two swirls are not contiguous, they may still share multiple arcs: an
example is given by the yellow and purple swirls in Figure 4(a).

######  Proposition 2.5.

In any SD, a swirl of degree $d$ may share at most $\lfloor d/2\rfloor$ arcs
with the same non-contiguous swirl.∎

Two swirls are said to be _discordant_ if one of them is clockwise and the
other is counterclockwise; they are _concordant_ otherwise.

######  Proposition 2.6.

In an SD, let $S_{1}$ and $S_{2}$ be two swirls that share more than one arc.
The following statements are equivalent: (i) $S_{1}$ and $S_{2}$ are not
contiguous; (ii) $S_{1}$ and $S_{2}$ are concordant; (iii) the eyes of $S_{1}$
and $S_{2}$ have antipodal interior points.∎

(a)

(b)

Figure 4: (a) The swirl in yellow shares two arcs with the contiguous swirl in
green and two arcs with the non-contiguous swirl in purple. (b) An attractor
hull and a sliding walk within its interior.

###  2.4 Attractors

The missing proofs of the results in this section are found in Appendix E.

######  Definition 2.7.

An _attractor_ of a $k$-oriented SD is a set of $k$ points, no two of which
are antipodal, chosen among its poles and anti-poles. An _attractor hull_ is
the spherical convex hull of an attractor.

Since no two poles are antipodal, a $k$-oriented SD has exactly $2^{k}$
distinct attractors.

Given any _attractor_ $A$ of a $k$-oriented SD $\mathcal{D}$, each arc of
$\mathcal{D}$ has a unique vanishing point in $A$, and is collinear with it.∎

######  Proposition 2.8.

The $k$ poles of a $k$-oriented SD cannot be all collinear. Thus, all
attractor hulls have non-empty interiors.∎

To state the following results, we have to define the terms _intersect_ ,
_cross_ , and _thrust_. By _intersect_ we simply mean “have a non-empty
intersection”. Thus, two arcs intersect each other even if they only share an
endpoint. Instead, an arc $a$ _crosses_ a curve when their intersection
includes an isolated point that is internal to $a$. Let $R$ be a spherical
polygon contained in the interior of a hemisphere. We say that an arc $a$
_thrusts_ the boundary of $R$ at a point $x$ if $a$ intersects the interior of
$R$ and intersects the boundary of $R$ at $x$.

######  Proposition 2.9.

If an arc of a $k$-oriented SD intersects the interior of an attractor hull
$H$, it intersects the boundary of $H$ in at most one point.∎

If $\mathcal{D}$ is an SD and $R$ is a region of the unit sphere, we say that
two points $x$ and $y$ are _$R$ -connected_ (with respect to $\mathcal{D}$) if
there is a path with endpoints $x$ and $y$ that follows the arcs of
$\mathcal{D}$ while remaining within $R$. If such a path is internal to $R$
(except for its endpoints $x$ and $y$, which may be on the boundary of $R$),
then $x$ and $y$ are _internally $R$-connected_.

######  Proposition 2.10.

If an arc of a $k$-oriented SD $\mathcal{D}$ intersects the boundary of an
attractor hull $H$ at a point $x$, then there is an arc of $\mathcal{D}$ that
crosses the boundary of $H$ at a point $y$, such that $x$ and $y$ are
$H$-connected (with respect to $\mathcal{D}$) and lie on a same edge of $H$.
Moreover, if $x\neq y$, then $y$ is not a vertex of $H$.∎

We say that an attractor hull is _total_ if it coincides with the entire unit
sphere. If an attractor hull is not total, then it is contained in the
interior of a hemisphere.

The following result justifies the choice of the term “attractor”.

######  Proposition 2.11.

Let $H$ be an attractor hull of a $k$-oriented SD $\mathcal{D}$. Then, there
exist arcs of $\mathcal{D}$ that intersect the interior of $H$. Moreover, any
point of intersection between an arc of $\mathcal{D}$ and the interior of $H$
is internally $H$-connected with the vertices of the eye of a swirl of
$\mathcal{D}$.

######  Proof 2.12.

Let $A$ be an attractor of $\mathcal{D}$, and let $H$ be the spherical convex
hull of $A$. If $H$ is total, there is nothing to prove, because $\mathcal{D}$
is connected and it has at least a swirl (see Section 2.1).

Otherwise, let $w$ be a sliding walk that starts from any arc of $\mathcal{D}$
and follows each arc in the direction of a vanishing point in $A$, which
exists due to Section 2.4.

As long as $w$ is outside of $H$, it keeps approaching points of $A\subset H$,
thus strictly reducing its distance from $H$, because $H$ is spherically
convex. Therefore, $w$ eventually reaches the boundary of $H$. Then, by
Proposition 2.10, there is an arc of $\mathcal{D}$ that crosses the boundary
of $H$, and therefore intersects the interior of $H$ (note that $H$ has an
interior, due to Proposition 2.8).

Now, let $x$ be any point of intersection between an arc of $\mathcal{D}$ and
the interior of $H$, and let us proceed with a sliding walk $w$ from $x$ as
described above. Since $H$ is convex and $w$ always moves toward a point of
$A\subset H$ without ever reaching it, we conclude that $w$ never leaves the
interior of $H$. An example of such a sliding walk is shown in Figure 4(b).

Thus, either the left-side or the right-side region of $w$ is entirely
contained in the interior of $H$. In turn, this region contains the eye of a
swirl, due to Lemma 2.1.

######  Corollary 2.13.

In any $k$-oriented SD $\mathcal{D}$, the interior of any attractor hull
contains the eye of a swirl of $\mathcal{D}$.∎

######  Proposition 2.14.

Given an SD $\mathcal{D}$, any great circle on the unit sphere is crossed by
at least three arcs of $\mathcal{D}$.∎

######  Proposition 2.15.

Let $H$ be a non-total attractor hull of a $k$-oriented SD $\mathcal{D}$, and
let $x$ be a point of intersection between an arc of $\mathcal{D}$ and the
interior of $H$. Then, there are three distinct arcs of $\mathcal{D}$ that
thrust the boundary of $H$ at three distinct points, not all lying on the same
edge of $H$, all of which are internally $H$-connected with $x$.∎

It is easy to see that the previous result cannot be improved, as there are
$k$-oriented SDs whose arcs thrust the boundary of an attractor hull at
exactly three points, two of which lie on the same edge of the attractor hull.

##  3 Minimal Arrangements

In this section, we will derive all the results listed in Table 1.

######  Proposition 3.1.

There are no $1$-oriented or $2$-oriented SDs.

######  Proof 3.2.

The poles of such SDs would be collinear, which contradicts Proposition 2.8.

An _attractor partition_ for a $k$-oriented SD $\mathcal{D}$ is a collection
of internally disjoint non-total attractor hulls of $\mathcal{D}$ that
collectively cover the unit sphere. The _vertices_ and _edges_ of an attractor
partition are the vertices and edges of the attractor hulls that constitute
it.

######  Lemma 3.3.

Let $\mathcal{D}$ be a $k$-oriented SD with an attractor partition
$\mathcal{S}$ consisting of $m$ attractor hulls. Then, $\mathcal{D}$ has at
least $m$ non-contiguous swirls, each of which has an eye in the interior of a
different attractor hull of $\mathcal{S}$. Moreover, $\mathcal{D}$ has at
least $\lceil 3m/2\rceil$ arcs that thrust edges of $\mathcal{S}$, and no arc
of $\mathcal{D}$ thrusts the boundaries of more than two attractor hulls.

######  Proof 3.4.

Since the attractor hulls constituting $\mathcal{S}$ are internally disjoint,
Proposition 2.11 guarantees that each of their interiors contains a swirl of
$\mathcal{D}$. Such swirls are distinct and non-contiguous, because their eyes
do not share any boundary points.

Moreover, Proposition 2.15 ensures that at least three arcs of $\mathcal{D}$
thrust the boundary of each attractor hull of $\mathcal{S}$. Also, no arc of
$\mathcal{D}$ thrusts the boundary of any attractor hull of $\mathcal{S}$ at
more than one point, due to Proposition 2.9. Hence, no arc of $\mathcal{D}$
thrusts the boundaries of more than two attractor hulls of $\mathcal{S}$. We
conclude that $\mathcal{D}$ has at least $\lceil 3m/2\rceil$ arcs that thrust
boundaries of attractor hulls of $\mathcal{S}$.

###  3.1 3-Oriented SDs

Observe that no $3$-oriented SDs are degenerate, otherwise their three poles
would be collinear, contradicting Proposition 2.8. In fact, there is
essentially one possible configuration for the poles of a $3$-oriented SD, and
the set of its $2^{3}=8$ attractor hulls constitutes an attractor partition.
We call each attractor hull of a $3$-oriented SD an _octant_ (see Figure
5(a)).

######  Theorem 3.5.

Any $3$-oriented SD has at least eight swirls and $12$ arcs; the bounds are
tight.

######  Proof 3.6.

Since any such SD has an attractor partition consisting of $m=8$ octants, it
follows from Lemma 3.3 that it has at least $m=8$ swirls and $3m/2=12$ arcs. A
$3$-oriented SOD with exactly eight swirls and $12$ arcs is shown in Figure
5(a).

(a)

(b)

Figure 5: (a) A $3$-oriented SD with exactly eight swirls and $12$ arcs. (b) A
non-degenerate $4$-oriented SOD with exactly six swirls and ten arcs. Each arc
has the same color as its vanishing points. Dashed lines mark the boundaries
of octants and sextants, respectively.

###  3.2 4-Oriented SDs

There are essentially two possible configurations of four poles on a sphere.
Starting from three poles determining eight octants, a fourth pole can be
placed either in the interior of an octant, giving rise to a non-degenerate
configuration with alignment $(3,3,3,3)$, or on the boundary between two
octants, giving rise to a degenerate configuration with alignment $(2,2,2,3)$.
Due to Proposition 2.8, there are no other configurations.

Every non-degenerate $4$-oriented SD has an attractor partition consisting of
six strictly convex quadrilaterals, which we call _sextants_.333The term
“sextant” traditionally refers to a navigation instrument. Its name is derived
from the fact that a sextant’s arc covers $60$ degrees, which is one sixth of
a circle. In this paper, we use the term to indicate each of six regions that
partition a sphere. An example is in Figure 5(b).

######  Theorem 3.7.

Any non-degenerate $4$-oriented SD has at least six swirls and nine arcs; if
it is an SOD, it has at least ten arcs. The bounds are tight.

######  Proof 3.8.

Since any such SD has an attractor partition consisting of $m=6$ sextants, it
follows from Lemma 3.3 that it has at least $m=6$ non-contiguous swirls and
$3m/2=9$ arcs. These six swirls, one per sextant, are called _sextant swirls_.

It remains to prove that any non-degenerate $4$-oriented SOD $\mathcal{D}$ has
at least ten arcs. Let $G$ be the subgraph of the swirl graph of $\mathcal{D}$
induced by its sextant swirls. As we recalled in Section 2.1, the swirl graph
of $\mathcal{D}$ is simple, planar, and bipartite; therefore, so is $G$. We
will prove that $G$ has at most eight edges.

Recall that $G$ has six vertices. If the partite sets of $G$ have $1$ and $5$
vertices, then $G$ has at most five edges. If the partite sets of $G$ have $2$
and $4$ vertices, then $G$ has at most eight edges. Finally, if the partite
sets of $G$ have $3$ and $3$ vertices, then $G$ has at most eight edges,
because the complete bipartite graph $K_{3,3}$ is not planar. Thus, $G$ has at
most eight edges.

Since a swirl involves at least three arcs, and each arc of an SOD contributes
to at most two swirls, the arcs of $\mathcal{D}$ that are involved in sextant
swirls are at least $6\times 3-8=10$, and hence $\mathcal{D}$ has at least ten
arcs.

A non-degenerate $4$-oriented SD with exactly six swirls and nine arcs is
obtained by perturbing the poles of the SD in Figure 6(a). A non-degenerate
$4$-oriented SOD with exactly six swirls and ten arcs is shown in Figure 5(b).

As for degenerate $4$-oriented SDs, we treat them as special cases of
$k$-oriented SDs with alignment $(2,2,\dots,2,k-1)$. It turns out that all of
these SDs have the same minimum number of swirls and arcs, for any $k\geq 4$.
However, since they do not have an attractor partition for $k>4$, analyzing
them will require an ad-hoc technique.

(a)

(b)

Figure 6: (a) A $4$-oriented SD with alignment $(2,2,2,3)$ having exactly six
swirls and nine arcs. (b) A $4$-oriented SOD with alignment $(2,2,2,3)$ having
exactly six swirls and 11 arcs.

######  Theorem 3.9.

If $k\geq 4$, any $k$-oriented SD with alignment $(2,2,\dots,2,k-1)$ has at
least six swirls and nine arcs; if it is an SOD, it has at least 11 arcs. The
bounds are tight.

######  Proof 3.10.

All poles lie on a same great circle $\gamma$, except for one pole $p$. Due to
Proposition 2.14, $\gamma$ is crossed by at least three arcs, which must have
$p$ as a vanishing point. Let $H$ and $H^{\prime}$ be the two hemispheres
bounded by $\gamma$, with $p\in H$. Let $w$ be a clockwise walk with fulcrum
$p$ starting from the interior of $H$, with the property that the arcs with
vanishing point $p$ are followed in the direction of $p$ (as opposed to the
anti-pole $-p$). Clearly, $w$ always remains within $H$, and it takes at least
three distinct arcs with vanishing points on $\gamma$ to do a complete turn
around $p$. Note that such arcs lie entirely in the interior of $H$.
Similarly, there are at least three arcs lying in the interior of
$H^{\prime}$, which yields nine arcs in total.

There are $2k-2$ distinct attractor hulls in $H$. By Proposition 2.11, each of
them contains the eye of a swirl; let $E$ be one of these eyes. Let
$\gamma^{\prime}$ be a great circle through $p$ that intersects the interior
of $E$. Note that $\gamma^{\prime}$ separates $H$ into two parts, each of
which contains an attractor hull, and hence the eye of a swirl distinct from
$E$. Thus, there are at least three swirls whose eyes are in $H$; for the same
reason, there are at least three swirls whose eyes are in $H^{\prime}$.

Let $G$ be the subgraph of the swirl graph induced by these six swirls; we
will prove that, in an SOD, $G$ has at most seven arcs. Observe that, in any
of these swirls, at most two arcs may have $p$ as a vanishing point (otherwise
the eye would not be spherically convex), and at most one of them may cross
$\gamma$. Recall from Section 2.1 that $G$ is simple and bipartite. Hence, at
most two arcs may be shared among the three swirls whose eyes are in $H$, and
at most two arcs may be shared among the other three swirls. Thus, $G$ has at
most three arcs crossing $\gamma$ and at most four other arcs. Therefore, the
six swirls involve at least $6\times 3-7=11$ arcs.

Matching examples for $k=4$ are shown in Figure 6; adding “dummy poles” on the
great circle that already contains three of them yields examples for all
$k>4$, as well.

(a)

(b)

Figure 7: (a) A $5$-oriented SD with alignment $(2,3,3,3,3)$ having exactly
five swirls and eight arcs. (b) A $5$-oriented SOD with alignment
$(2,3,3,3,3)$ having exactly five swirls and nine arcs.

###  3.3 5-Oriented SDs

There are essentially four distinct configurations of five poles. By
Proposition 2.8, the poles cannot all be collinear; nonetheless, four of them
may lie on a same great circle, giving rise to a configuration with alignment
$(2,2,2,2,4)$, which was already discussed in Theorem 3.9.

If three poles lie on a same great circle $\gamma$, we have two possible
alignments: $(2,3,3,3,3)$ if the two remaining poles are collinear with a pole
on $\gamma$ (see Figure 8(a)), and $(3,3,3,3,4)$ otherwise. Each of these
alignments completely determines the combinatorics of the configuration.

Finally, we have the non-degenerate alignment $(4,4,4,4,4)$. To see why all
configurations of five poles with this alignment are equivalent, consider four
poles with alignment $(3,3,3,3)$. The great circles through pairs of these
poles partition each sextant into four spherical triangles. Since these 24
triangles are all equivalent, placing a fifth pole in the interior of any one
of them yields combinatorially equivalent configurations with alignment
$(4,4,4,4,4)$.

(a)

(b)

Figure 8: (a) A configuration of five poles with alignment $(2,3,3,3,3)$, and
an attractor partition. (b) A non-degenerate $5$-oriented SDs with exactly
four swirls and nine arcs.

######  Theorem 3.11.

Any $5$-oriented SD with alignment $(2,3,3,3,3)$ has at least five swirls.
Moreover, there are SDs with alignment $(2,3,3,3,3)$ that have exactly five
swirls and eight arcs, and SODs with alignment $(2,3,3,3,3)$ that have exactly
five swirls and nine arcs.

######  Proof 3.12.

As shown in Figure 8(a), any SD with alignment $(2,3,3,3,3)$ has an attractor
partition consisting of $m=5$ attractor hulls. It follows from Lemma 3.3 that
it has at least $m=5$ non-contiguous swirls. An SD and an SOD with the desired
properties are found in Figure 7.

By perturbing the red poles in Figure 7, one obtains configurations of SDs and
SODs with alignments $(3,3,3,4,4)$ and $(4,4,4,4,4)$ with the same
characteristics. In the latter case, however, we can actually construct SDs
and SODs with only four swirls (which is minimum).

(a)

(b)

Figure 9: Sketch of the two cases in the proof of Lemma 3.13.

(a)

(b)

Figure 10: Case 1 in the proof of Lemma 3.13.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 11: Case 2 in the proof of Lemma 3.13.

######  Lemma 3.13.

If a $5$-oriented SD has exactly four swirls, then it has at least nine arcs.
There are matching non-degenerate examples.

######  Proof 3.14.

It is not restrictive to focus on non-degenerate SDs, because the poles of a
degenerate SD can be perturbed without altering the number of swirls and arcs,
making it non-degenerate.

As argued above, there is essentially a unique non-degenerate configuration of
five poles, in the sense that drawing great circles through pairs of such
poles yields combinatorially equivalent partitions of the sphere into
spherical polygons. Moreover, it is easy to see that there is always a
spherically convex pentagonal attractor hull. In fact, without loss of
generality, we may assume that the five poles $p_{1}$, …, $p_{5}$ are the
vertices of such an attractor hull $H$; likewise, the anti-poles
$p^{\prime}_{1}$, …, $p^{\prime}_{5}$ are also vertices of a spherically
convex pentagonal attractor hull $H^{\prime}$, as shown in Figure 10.

Assume that there are four swirls; we will identify four interior-disjoint
regions of the sphere where their eyes must be located. By Corollary 2.13,
every attractor hull contains the eye of a swirl. Hence, $H^{\prime}$ contains
the eye of a swirl: this is the first region. Consider the attractor hull $H$,
as well as the five quadrilateral attractor hulls $Q_{1}$, …, $Q_{5}$, each of
which shares an edge with $H^{\prime}$ and two non-consecutive vertices with
$H$. For example, $Q_{1}$ has vertices $p^{\prime}_{4}$, $p^{\prime}_{5}$,
$p_{3}$, $p_{1}$ and contains $p_{2}$ in its interior, etc., as shown in
Figure 9. The eyes of the remaining three swirls must be shared among these
six attractor hulls.

We will distinguish two cases. In Case 1, no eye lies in the intersection of
more than two of these six attractor hulls. Since the $Q_{i}$’s are all
equivalent, we may assume that the three eyes are in the regions $H\cap
Q_{1}$, $Q_{2}\cap Q_{3}$, and $Q_{4}\cap Q_{5}$, as sketched in Figure 9(a).
Since the interior of the attractor hull
$p^{\prime}_{1}p^{\prime}_{3}p_{5}p_{4}$ only intersects the chosen region
$H^{\prime}$ (Figure 10(a)), there must be an eye in their intersection.
However, this implies that the attractor hull
$p^{\prime}_{3}p^{\prime}_{5}p_{2}p_{1}$ has no eyes in its interior (Figure
10(b)), which is a contradiction.

In Case 2, an eye lies in the intersection of three of the six attractor
hulls, say $H\cap Q_{1}\cap Q_{2}$. Without loss of generality, the other two
eyes are in the regions $Q_{3}$ and $Q_{4}\cap Q_{5}$, as sketched in Figure
9(b). Again, we can progressively reduce these four regions by finding
attractor hulls whose interiors intersect only one region, as detailed in
Figure 11. Finally, we obtain the four regions $R_{1}$, $R_{2}$, $R_{3}$,
$R_{4}$ shown in Figure 11(f), where the only pairs of regions that may be
connected by an arc are $(R_{1},R_{3})$, $(R_{2},R_{4})$, and $(R_{3},R_{4})$.
Indeed, observe that $R_{2}$ and $R_{3}$ are equivalent to $R_{1}$ and
$R_{4}$, respectively. Thus, we only have to verify that no arc can connect
$R_{1}$ with $R_{2}$ or with $R_{4}$. Furthermore, due to Proposition 2.6, no
two swirls may share more than one arc, since no two regions have antipodal
internal points. Hence, there are at most three arcs that are shared between
pairs of swirls. We conclude that the arcs contributing to the four swirls are
at least $4\times 3-3=9$.

An SD with the desired properties is shown in Figure 8(b).

(a)

(b)

Figure 12: (a) If an arc $a$ contributes to four swirls, the SD has at least
eight arcs. (b) In an SD with seven arcs, if $a$ contributes to three swirls,
only $b$ and $g$ may have a common vanishing point.

######  Proposition 3.15.

In a $k$-oriented SD, if two non-collinear arcs $a$ and $b$ have a common
vanishing point, then the great circle containing $a$ does not intersect $b$,
and vice versa.

######  Proof 3.16.

The vanishing points of $a$ and $b$ are the two intersection points between
the great circles containing $a$ and $b$. By definition of $k$-oriented SD,
$b$ does not intersect its vanishing points, and thus it cannot intersect the
great circle containing $a$, and vice versa.

######  Theorem 3.17.

Any $5$-oriented SD has at least eight arcs; if it is an SOD, it has at least
nine arcs.

######  Proof 3.18.

Due to Theorems 2.2 and 3.13, we may assume that there are at least five
swirls.

Recall from Section 2.3 that, since swirls may be contiguous, each arc of an
SD may contribute to up to four different swirls. If an arc $a$ contributes to
four swirls, it must hit at least two arcs, and it must block four arcs, all
of which are distinct (see Figure 12(a)). Of these seven arcs, only the two
hit by $a$ cross the great circle containing $a$. Thus, by Proposition 2.14,
there must be another arc crossing this great circle, implying that there are
at least eight arcs in the SD.

Consider now an SD where an arc $a$ is shared by exactly three swirls (two of
which are contiguous), and assume that there are fewer than eight arcs. As
shown in Figure 12(b), two arcs $b$ and $e$ block $a$ (where $b$ contributes
to the two contiguous swirls), and three arcs $c$, $d$, $f$ hit $a$. As in the
previous case, there must be a seventh arc $g$ crossing the great circle
$\gamma$ containing $a$, otherwise the only two arcs crossing $\gamma$ would
be $b$ and $e$. Since there are five swirls, the arcs $c$, $d$, $e$, $f$, $g$
must form two swirls away from $a$, with eyes located on opposite sides of
$\gamma$ (we recalled in Section 2.1 that the interior of any hemisphere
contains the eye of a swirl). We argue that only two of these seven arcs may
have a common vanishing point. Indeed, by Proposition 3.15, incident arcs
cannot have a common vanishing point. Also, the extensions of some arcs
necessarily hit other arcs, as the dashed lines in Figure 12(b) illustrate.
Again, Proposition 3.15 implies that such pairs of arcs do not have a common
vanishing point. In fact, the only two arcs that may have the same vanishing
points are $b$ and $g$. Hence, there must be at least six distinct poles, and
the SD cannot be $5$-oriented.

Finally, assume that each arc contributes to at most two swirls, and recall
that each of the five swirls has degree at least three. Then, the arcs that
contribute to any five swirls are at least $\lceil(5\times 3)/2\rceil=8$. We
conclude that a $5$-oriented SD has at least eight arcs.

As for SODs, recall that their swirl graphs are simple and bipartite, and each
arc contributes to at most two swirls. Since each of the five swirls has
degree at least three, and a bipartite graph on five vertices has at most six
edges, we conclude that the arcs contributing to the five swirls are at least
$5\times 3-6=9$. Thus, a $5$-oriented SOD has at least nine arcs.

###  3.4 6-Oriented SDs and Beyond

As it turns out, $6$-oriented SDs and SODs with alignment $(3,3,3,3,3,3)$
already achieve the absolute minimum in terms of the number of swirls, as well
as the number of arcs.

######  Theorem 3.19.

Any SD has at least two clockwise swirls, two counterclockwise swirls, and six
arcs. Any SOD has at least eight arcs. Moreover, there are matching examples
that are $6$-oriented with alignment $(3,3,3,3,3,3)$.

######  Proof 3.20.

We recalled in Section 2.1 that any SOD has at least eight arcs; this was
proved in [8]. Also, we have proved in Theorem 2.2 that any SD has at least
two clockwise swirls and two counterclockwise swirls. It remains to prove that
any SD has at least six arcs.

Let $S_{1}$ and $S_{2}$ be two clockwise swirls of an SD $\mathcal{D}$, of
degrees $d_{1}\geq 3$ and $d_{2}\geq 3$, respectively. Without loss of
generality, assume that $d_{1}\geq d_{2}$. Due to Proposition 2.6, $S_{1}$ and
$S_{2}$ cannot be contiguous, because they are concordant.

Thus, by Proposition 2.5, $S_{1}$ and $S_{2}$ share at most $\lfloor
d_{2}/2\rfloor$ arcs. As a consequence, the arcs involved in these two swirls
are at most $d_{1}+d_{2}-\lfloor d_{2}/2\rfloor=d_{1}+\lceil d_{2}/2\rceil$.
If $d_{1}\geq 4$, then $d_{1}+\lceil d_{2}/2\rceil\geq 6$, and $\mathcal{D}$
has at least six arcs.

So, assume that $d_{1}=d_{2}=3$ and exactly $d_{1}+\lceil d_{2}/2\rceil=5$
arcs are involved in $S_{1}$ and $S_{2}$. In this case, the two swirls share
exactly one arc $a\in\mathcal{D}$. Let $\gamma$ be the great circle containing
$a$. Of the arcs involved in $S_{1}$ and $S_{2}$, two hit $a$ and two block
$a$; only the latter cross $\gamma$. Due to Proposition 2.14, there must be a
third arc that crosses $\gamma$, and so $\mathcal{D}$ has at least six arcs.

Matching examples with alignment $(3,3,3,3,3,3)$ are found in Figure 13.

(a)

(b)

Figure 13: (a) A $6$-oriented SD with alignment $(3,3,3,3,3,3)$ having exactly
four swirls and six arcs. (b) A $6$-oriented SD with alignment $(3,3,3,3,3,3)$
having exactly four swirls and eight arcs.

By perturbing the poles of the SDs in Figure 13, one obtains a continuum of
configurations of $6$-oriented SDs and SODs having the absolute minimum number
of swirls and arcs. These include degenerate and non-degenerate configurations
of all the alignments listed in Table 1 for $k=6$ (except for $(2,2,2,2,2,5)$,
which is covered by Theorem 3.9). Adding “dummy poles” to these configurations
yields similar results for $k>6$. In particular, this covers all non-
degenerate configurations for any $k\geq 6$, i.e., those with alignment
$(k-1,k-1,\dots,k-1)$.

## References

  * [1] Israel Aldana-Galván, Jose Luis Álvarez-Rebollar, Juan Carlos Catana-Salazar, Mazay Jimenez-Salinas, Erick Solis-Villarreal, and Jorge Urrutia.  Minimizing the solid angle sum of orthogonal polyhedra and guarding them with $\pi$/2-edge guards.  In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016), pages 175–181, 2016.
  * [2] Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Anastasia Kurdia, Joseph O’Rourke, Godfried T. Toussaint, Jorge Urrutia, and Giovanni Viglietta.  Edge-guarding orthogonal polyhedra.  In Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), pages 461–466, 2011.
  * [3] Béla Bollobás.  Extremal graph theory.  Dover Publications, 2004.
  * [4] Javier Cano, Csaba D. Tóth, Jorge Urrutia, and Giovanni Viglietta.  Edge guards for polyhedra in three-space.  Computational Geometry, 104:101859, 2022.
  * [5] David Eppstein, Elena Mumford, Bettina Speckmann, and Kevin Verbeek.  Area-universal and constrained rectangular layouts.  SIAM Journal on Computing, 41(3):537–564, 2012.
  * [6] Kimberly Kokado and Csaba D. Tóth.  Nonrealizable planar and spherical occlusion diagrams.  In Abstract of the 24th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2022), pages 60–61, 2022\.
  * [7] Joseph O’Rourke.  Art gallery theorems and algorithms, volume 3 of International Series of Monographs on Computer Science.  Oxford University Press, 1987.
  * [8] Csaba D. Tóth, Jorge Urrutia, and Giovanni Viglietta.  Minimizing visible edges in polyhedra.  Graphs and Combinatorics, 39(5):111:1–111:21, 2023.
  * [9] Jorge Urrutia.  Art gallery and illumination problems.  In Handbook of Computational Geometry, chapter 22, pages 973–1027. North-Holland, Amsterdam, 2000.
  * [10] Giovanni Viglietta.  Face-guarding polyhedra.  Computational Geometry, 47(8):833–846, 2014.
  * [11] Giovanni Viglietta.  Optimally guarding 2-reflex orthogonal polyhedra by reflex edge guards.  Computational Geometry: Theory and Applications, 86:101589, 2020\.
  * [12] Giovanni Viglietta.  A theory of spherical diagrams.  In Proceedings of the 34th Canadian Conference on Computational Geometry (CCCG 2022), pages 306–313, 2022.
  * [13] Giovanni Viglietta.  A theory of spherical diagrams.  Computing in Geometry and Topology, 2(2):2:1–2:24, 2023.

##  Appendix A Previous Results

###  A.1 Properties of SDs

We summarize what is currently known about SDs. Proofs of the following
statements are found in [13]; although they were stated and proved only for
SODs, the reader may verify that none of the proofs makes use of the one-
sidedness of the arrangements.

######  Proposition A.1.

Every arc in an SD hits exactly two distinct arcs, one at each endpoint.∎

######  Proposition A.2.

No two arcs in an SD intersect in more than one point.∎

######  Proposition A.3.

Given an SD $\mathcal{D}$, the relative interior of any great semicircle on
the unit sphere is crossed by at least one arc of $\mathcal{D}$.444In [13],
the word “intersect” is used instead of “cross”. However, the proof therein
actually yields this slightly stronger result.∎

######  Proposition A.4.

An SD partitions the unit sphere into spherically convex regions.∎

######  Definition A.5.

A _tile_ is each of the (spherically convex) regions into which the unit
sphere is partitioned by an SD.

######  Corollary A.6.

In an SD, no tile (including its boundary) contains two antipodal points.∎

######  Proposition A.7.

Removing any one arc from an SD and taking the union of the remaining arcs
yields a connected subset of the unit sphere.∎

######  Corollary A.8.

The union of all the arcs in an SD is a connected set.∎

######  Proposition A.9.

An SD with $n$ arcs partitions the unit sphere into $n+2$ tiles.∎

######  Proposition A.10.

In an SD $\mathcal{D}$, let $\mathcal{S}$ be a swirl of degree $d$.

  * •

The union of the $d$ arcs of $\mathcal{S}$ separates the unit sphere in two
regions, exactly one of which is spherically convex; this region is a
spherical $d$-gon called the _eye_ $E$ of $\mathcal{S}$.

  * •

The only points of intersection between pairs of arcs of $\mathcal{S}$ are the
vertices of $E$.∎

######  Proposition A.11.

In an SD, if the eyes of two distinct swirls have intersecting interiors, then
their boundaries are disjoint.∎

######  Definition A.12.

The _swirl graph_ of an SD $\mathcal{D}$ is the undirected multigraph on the
set of swirls of $\mathcal{D}$ having an edge between two swirls for every arc
in $\mathcal{D}$ shared by the two swirls.

######  Theorem A.13.

The swirl graph of any SD is planar; moreover, any SD has at least one
clockwise swirl and at least one counterclockwise swirl.∎

The following results on SDs were proved in [8]. Again, they were stated only
for SODs, but their proofs do not require the one-sidedness of the
arrangements.

######  Lemma A.14.

Given an SD $\mathcal{D}$, the relative interior of any hemisphere contains
the eye of at least one swirl of $\mathcal{D}$.∎

######  Theorem A.15.

Every SD has at least four swirls.∎

###  A.2 Properties of SODs

In addition to the previous properties, SODs also enjoy the following ones.
All proofs are found in [13].

######  Proposition A.16.

In an SOD, any arc coincides with an edge of a tile.∎

######  Proposition A.17.

In an SOD $\mathcal{D}$, let $\mathcal{S}$ be a swirl of degree $d$, and let
$E$ be its eye. Then, the tiles of $\mathcal{D}$ adjacent to $E$ are exactly
$d$; any two such tiles are either disjoint or intersect only along a single
arc of $\mathcal{S}$.∎

######  Theorem A.18.

The swirl graph of any SOD is a simple planar bipartite graph with non-empty
partite sets.∎

Since there are at least four swirls in an SOD (Theorem A.15) and the swirl
graph of an SOD is simple, planar and bipartite (Theorem A.18), it easily
follows that any SOD has at least eight arcs. A proof is found in [8].

######  Corollary A.19.

Every SOD has at least eight arcs.∎

##  Appendix B Sliding Walks

We will prove Lemma 2.1; our technique is inspired by the proof of Lemma A.14
(cf. [8, Lemma 9]).

######  Lemma B.1.

The right-side region (resp., left-side region) of any sliding walk on an SD
$\mathcal{D}$ contains the eye of a clockwise swirl (resp., counterclockwise
swirl) of $\mathcal{D}$.

######  Proof B.2.

Let $w$ be any sliding walk and let $A$ be its right-side region. Consider a
right-handed walk $w^{\prime}$ starting from any point on the boundary of $A$,
as shown in Figure 3(a). Note that $w^{\prime}$ never leaves $A$, because it
is a right-handed walk: upon reaching the boundary of $A$, $w^{\prime}$
follows it clockwise until it reaches one of its vertices. Then it turns
right, either remaining on the boundary of $A$ or entering its interior. In
particular, the right-side region $E$ of $w^{\prime}$ is contained in $A$. By
Section 2.2, $E$ is the eye of a clockwise swirl.

For a similar reason, the left-side region of $w$ contains the eye of a
counterclockwise swirl.

##  Appendix C Arc Doubling

An _overlap_ in an SD is any endpoint shared by two arcs.555In [13], SODs with
overlaps are called “degenerate”. We adopted a different terminology in this
paper to avoid confusion with degenerate $k$-oriented SDs. Observe that an
overlap must lie in the relative interior of some arc.

Let $\mathcal{D}$ be an SD, and let $a\in\mathcal{D}$. For a sufficiently
small positive real number $\epsilon$, we define the _$\epsilon$ -doubling_ of
$a$. This operation consists of replacing $a$ with two disjoint arcs
$a^{\prime}$ and $a^{\prime\prime}$ defined as follows. Let $x$ and $y$ be the
endpoints of $a$, located in the relative interiors of arcs $b\in\mathcal{D}$
and $c\in\mathcal{D}$, respectively. Then, $a^{\prime}$ and $a^{\prime\prime}$
also hit $b$ at $x^{\prime}$ and $x^{\prime\prime}$, respectively, such that
the geodesic arc $x^{\prime}x^{\prime\prime}$ has length $\epsilon$ and its
midpoint is $x$. Similarly, $a^{\prime}$ and $a^{\prime\prime}$ hit $c$ at
points $\epsilon$ apart with midpoint $y$. Moreover, any arc of $\mathcal{D}$
that hit $a$ or shared and endpoint with $a$ is now slightly shortened to hit
either $a^{\prime}$ or $a^{\prime\prime}$.

$\epsilon$-doubling an arc of an SD preserves the number of its swirls.∎

######  Proposition C.1.

Any SD, possibly with overlaps, can be converted into an SOD without overlaps
by $\epsilon$-doubling of arcs.

######  Proof C.2.

Observe that $\epsilon$-doubling an arc eliminates any overlaps involving that
arc without introducing new overlaps, provided that $\epsilon$ is sufficiently
small. Furthermore, if an arc is hit from both sides, the $\epsilon$-doubling
operation replaces it with two arcs, each of which is hit only from one side.

##  Appendix D Swirl Adjacency

These are the missing proofs from Section 2.3.

######  Proposition D.1.

In any SD, pairs of contiguous swirls share exactly two arcs.

######  Proof D.2.

Let $S_{1}$ and $S_{2}$ be contiguous swirls sharing two arcs $a$ and $b$,
with $a$ hitting $b$ at point $p$. The great circles containing $a$ and $b$
subdivide the unit sphere into four spherical lunes. Each of the eyes of
$S_{1}$ and $S_{2}$, being spherically convex, lies in one such spherical
lune; moreover, the two eyes lie in lunes that are adjacent along $a$. Thus,
if there is a third arc $c$ shared by $S_{1}$ and $S_{2}$, then $a$ must hit
$c$ at the endpoint opposite to $p$. However, any arc of a swirl hits exactly
one other arc in the same swirl, meaning that $c$ cannot be shared by $S_{1}$
and $S_{2}$.

######  Corollary D.3.

If two swirls $S_{1}$ and $S_{2}$ of an SD $\mathcal{D}$ are contiguous along
an arc $a\in\mathcal{D}$, then $\epsilon$-doubling $a$ separates the eyes of
$S_{1}$ and $S_{2}$ and results in a swirl graph where $S_{1}$ and $S_{2}$ are
connected by a single edge.

######  Proof D.4.

By Proposition D.1, the swirls $S_{1}$ and $S_{2}$ share exactly two arcs $a$
and $b$. Thus, $\epsilon$-doubling $a$ yields two swirls that share only $b$.

######  Proposition D.5.

In any SD, non-contiguous swirls may only share arcs that are not consecutive
in either swirl.

######  Proof D.6.

Assume that two swirls $S_{1}$ and $S_{2}$ share two arcs $a$ and $b$ that are
consecutive in $S_{1}$, with $a$ hitting $b$ at a vertex $p$ of the eye of
$S_{1}$. By Proposition A.10 applied to $S_{2}$, we have that $p$ must be a
vertex of the eye of $S_{2}$, as well. It follows that $S_{1}$ and $S_{2}$ are
contiguous.

######  Corollary D.7.

In any SD, a swirl of degree $d$ may share at most $\lfloor d/2\rfloor$ arcs
with the same non-contiguous swirl.

######  Proof D.8.

In a cycle of $d$ arcs, any subset of more than $\lfloor d/2\rfloor$ arcs
contains a pair of consecutive arcs. If these arcs were shared with the same
non-contiguous swirl, Proposition D.5 would be contradicted.

######  Proposition D.9.

In an SD, let $S_{1}$ and $S_{2}$ be two swirls that share more than one arc.
The following statements are equivalent.

  * •

$S_{1}$ and $S_{2}$ are not contiguous.

  * •

$S_{1}$ and $S_{2}$ are concordant.

  * •

The eyes of $S_{1}$ and $S_{2}$ have antipodal interior points.

######  Proof D.10.

Contiguous swirls are obviously discordant. Also, their eyes lie on the same
side of one of the two arcs shared by the two swirls. Hence, both eyes lie in
the same hemisphere determined by that arc, and therefore cannot have
antipodal (interior) points.

We have proved that the first statement is implied by the second and by the
third. We will now prove the converse. Let $S_{1}$ be a swirl with eye
$E_{1}$, and let $E^{\prime}_{1}$ be the spherical polygon antipodal to
$E_{1}$. Let $a$ and $b$ be two arcs that are shared between $S_{1}$ and a
non-contiguous swirl $S_{2}$; by Proposition D.5, $a$ and $b$ are disjoint.

The two great circles containing $a$ and $b$ subdivide the unit sphere into
four spherical lunes, one of which, say $L_{1}$, contains $E_{1}$. Assume that
the lune containing the eye $E_{2}$ of $S_{2}$ is adjacent to $L_{1}$. Without
loss of generality, $E_{1}$ and $E_{2}$ lie on the same side of $a$ and on
opposite sides of $b$. However, this implies that $S_{1}$ and $S_{2}$ are
contiguous along $b$, which is a contradiction.

We conclude that $E_{2}$ lies in the lune $L_{2}$ opposite to $L_{1}$. Note
that $a$ and $b$, departing from $E_{1}$, follow the edges of $L_{1}$ in
opposite directions. Then, they continue along the edges of $L_{2}$ in the
same directions, implying that $S_{1}$ and $S_{2}$ are concordant swirls.

Let $p_{1}\in L_{1}$ and $p_{2}\in L_{2}$ be the endpoints of $a$, and let
$q_{1}\in L_{1}$ and $q_{2}\in L_{2}$ be the endpoints of $b$. Since $p_{1}$
and $q_{1}$ are vertices of $E_{1}$, the segment $p_{1}q_{1}$ is contained in
$E_{1}$. Likewise, $p_{2}q_{2}$ is contained in $E_{2}$. Since $a$ and $b$ are
shorter than great semicircles, the points $p_{2}^{\prime}$ and
$q_{2}^{\prime}$, antipodal to $p_{2}$ and $q_{2}$ respectively, lie outside
of $a$ and $b$. Nonetheless, $p_{2}^{\prime},q_{2}^{\prime}\in L_{1}$. It
follows that $p_{1}q_{1}$ and $p_{2}^{\prime}q_{2}^{\prime}$ cross each other
at a point $x$ internal to $E_{1}$. The point $x^{\prime}$ antipodal to $x$
lies in $p_{2}q_{2}$, and is therefore internal to $E_{2}$.

##  Appendix E Attractors

These are the missing proofs from Section 2.4.

Given any _attractor_ $A$ of a $k$-oriented SD $\mathcal{D}$, each arc of
$\mathcal{D}$ has a unique vanishing point in $A$, and is collinear with it.∎

######  Proposition E.1.

The $k$ poles of a $k$-oriented SD cannot be all collinear. Thus, all
attractor hulls have non-empty interiors.

######  Proof E.2.

Assume for a contradiction that all poles of a $k$-oriented SD $\mathcal{D}$
(and therefore all its anti-poles) lie on the same great circle $\gamma$. Due
to Proposition A.3, there is an arc $a\in\mathcal{D}$ that crosses $\gamma$,
say at $x$. By definition of $k$-oriented SD, $a$ is collinear with a pole
$f(a)\neq x$. However, since $f(a)$ and $x$ lie on $\gamma$, then so does $a$,
contradicting the fact that $a$ crosses $\gamma$ at $x$.

Thus, no $k$ points among poles and anti-poles can be collinear, and therefore
their spherical convex hull must have a non-empty interior. It follows that
all attractors hulls have non-empty interiors.

######  Proposition E.3.

If an arc of a $k$-oriented SD intersects the interior of an attractor hull
$H$, it intersects the boundary of $H$ in at most one point.

######  Proof E.4.

By Appendix E, any arc $a$ is collinear with a vanishing point $p$ within $H$.
Also, by definition of $k$-oriented SD, $a$ does not contain $p$. It follows
that, if $a$ intersects the interior of $H$, it cannot intersect its boundary
in two points, because such points would be on opposite sides of $p$ (or
coincident with $p$).

######  Proposition E.5.

If an arc of a $k$-oriented SD $\mathcal{D}$ intersects the boundary of an
attractor hull $H$ at a point $x$, then there is an arc of $\mathcal{D}$ that
crosses the boundary of $H$ at a point $y$, such that $x$ and $y$ are
$H$-connected (with respect to $\mathcal{D}$) and lie on a same edge of $H$.
Moreover, if $x\neq y$, then $y$ is not a vertex of $H$.

######  Proof E.6.

If $\mathcal{D}$ has an arc that crosses $H$ at $x$, there is nothing to
prove. Otherwise, Appendix E implies that $\mathcal{D}$ has an arc $a$
collinear with an edge $e$ of $H$ containing $x$. Moreover, $x$ lies in the
interior of $a$; thus, $a$ partially overlaps with $e$. Hence, there is a
vanishing point $v\in e$ that $a$ cannot reach, by Appendix E. So, $a$ hits an
arc $a^{\prime}\in\mathcal{D}$ at a point $y\in e$, strictly between $x\in e$
and $v\in e$. Therefore, $y$ is internal to $e$, it is $H$-connected with $x$,
and $a^{\prime}$ crosses $e$ at $y$.

######  Proposition E.7.

Let $H$ be an attractor hull of a $k$-oriented SD $\mathcal{D}$. Then, there
exist arcs of $\mathcal{D}$ that intersect the interior of $H$. Moreover, any
point of intersection between an arc of $\mathcal{D}$ and the interior of $H$
is internally $H$-connected with the vertices of the eye of a swirl of
$\mathcal{D}$.

######  Proof E.8.

Let $A$ be an attractor of $\mathcal{D}$, and let $H$ be the spherical convex
hull of $A$. If $H$ is total, there is nothing to prove (cf. Corollaries A.8
and 2.2).

Otherwise, let $w$ be a sliding walk that starts from any arc of $\mathcal{D}$
and follows each arc in the direction of a vanishing point in $A$, which
exists due to Appendix E.

As long as $w$ is outside of $H$, it keeps approaching points of $A\subset H$,
thus strictly reducing its distance from $H$, because $H$ is spherically
convex. Therefore, $w$ eventually reaches the boundary of $H$. Then, by
Proposition E.5, there is an arc of $\mathcal{D}$ that crosses the boundary of
$H$, and therefore intersects the interior of $H$ (note that $H$ has an
interior, due to Proposition E.1).

Now, let $x$ be any point of intersection between an arc of $\mathcal{D}$ and
the interior of $H$, and let us proceed with a sliding walk $w$ from $x$ as
described above. Since $H$ is convex and $w$ always moves toward a point of
$A\subset H$ without ever reaching it, we conclude that $w$ never leaves the
interior of $H$. An example of such a sliding walk is shown in Figure 4(b).

Thus, either the left-side or the right-side region of $w$ is entirely
contained in the interior of $H$. In turn, this region contains the eye of a
swirl, due to Lemma B.1.

######  Corollary E.9.

In any $k$-oriented SD $\mathcal{D}$, the interior of any attractor hull
contains the eye of a swirl of $\mathcal{D}$.

######  Proof E.10.

If $H$ is an attractor hull, by Proposition E.7 there is a point $x$ of
intersection between an arc of $\mathcal{D}$ and the interior of $H$. Also,
there is an eye $E$ of a swirl of $\mathcal{D}$ whose vertices lie in the
interior of $H$ and are $H$-connected with $x$. Since $H$ is spherically
convex, its interior contains $E$.

It is easy to see that, for a fixed $k$-oriented SD, any hemisphere contains
an attractor hull. Such an attractor hull is unique, provided that no poles
lie on the hemisphere’s boundary. Thus, we may view Corollary E.9 as a
stronger version of Lemma A.14 for $k$-oriented SDs.

######  Proposition E.11.

Let $R$ be a spherical polygon contained in the interior of a hemisphere of
the unit sphere, and let $x$ be a point of an SD $\mathcal{D}$ that lies in
the interior of $R$. Then, for every great circle $\gamma$ through $x$, there
are arcs of $\mathcal{D}$ that thrust the boundary of $R$ at two distinct
points $y$ and $z$ located on opposite sides of $\gamma$ (or on $\gamma$).
Moreover, $y$ and $z$, are internally $R$-connected with $x$.

######  Proof E.12.

Let $p$ be a point of intersection between $\gamma$ and the boundary of a
hemisphere containing $R$. Let $y$ (resp., $z$) be the first point where a
clockwise (resp., counterclockwise) walk with fulcrum $p$ starting from $x$
intersects the boundary of $R$. In the special case where $x$ lies on an arc
of $\mathcal{D}$ contained in $\gamma$, we choose the two walks to go in
different directions, so $y$ and $z$ are necessarily distinct. Also, $y$ and
$z$ clearly satisfy the desired conditions.

######  Proposition E.13.

Let $R$ be a spherical polygon contained in the interior of a hemisphere of
the unit sphere, and let $\mathcal{D}$ be an SD having an arc with an endpoint
$x$ internal to $R$. Then, there are arcs of $\mathcal{D}$ that thrust the
boundary of $R$ in at least three distinct points that are all internally
$R$-connected with $x$.

######  Proof E.14.

Let $x$ be an internal point of $R$ where an arc of $\mathcal{D}$ hits another
arc. Let $\gamma$ be any great circle through $x$; by Proposition E.11, there
are two distinct points $y$ and $z$ where arcs of $\mathcal{D}$ thrust the
boundary of $R$. Moreover, $x$, $y$, and $z$ are $R$-connected.

Assume that $y$ and $z$ are not collinear with $x$. Then there is a great
circle $\gamma^{\prime}$ through $x$ such that $y$ and $z$ are strictly on the
same side of $\gamma^{\prime}$. By Proposition E.11, there is a third point
$w$ lying on the opposite side of $\gamma^{\prime}$ (or on $\gamma^{\prime}$)
where an arc of $\mathcal{D}$ thrusts the boundary of $R$. Moreover, $x$ and
$w$ are internally $R$-connected, implying that $y$, $z$, and $w$ are
internally $R$-connected.

Assume that $y$ and $z$ are collinear with $x$. Because $x$ is shared by two
arcs $a,b\in\mathcal{D}$, there is a point $x^{\prime}$ in $R\cap(a\cup b)$
such that $x^{\prime}$ is not collinear with $y$ and $z$. Hence, there is a
great circle $\gamma^{\prime}$ through $x^{\prime}$ such that $y$ and $z$ are
strictly on the same side of $\gamma^{\prime}$ (because $y$ and $z$ are not
antipodal, since $R$ lies in the interior of a hemisphere). Now we can
conclude the proof as in the previous case, observing that $x$ and
$x^{\prime}$ are internally $R$-connected.

Observe that Propositions E.11 and E.13 do not require $R$ to be spherically
convex or even simply connected.

We can also prove a version of Proposition E.13 in the limit case where $R$ is
an entire hemisphere.

######  Proposition E.15.

Given an SD $\mathcal{D}$, any great circle on the unit sphere is crossed by
at least three arcs of $\mathcal{D}$.

######  Proof E.16.

Let $\gamma$ be a great circle, and let $p,p^{\prime}\in\gamma$ be two
antipodal points which divide $\gamma$ into two great semicircles. By
Proposition A.3, the interior of each of these two semicircles is crossed by
an arc of $\mathcal{D}$. Note that the two crossing points $x$ and $y$ are
distinct, because the two semicircles have disjoint interiors. Now, $x$ and
$y$ divide $\gamma$ into two arcs, at least one of which is not shorter than a
great semicircle. The interior of this arc is crossed by an arc of
$\mathcal{D}$, again by Proposition A.3. Thus, we have found three distinct
points where arcs of $\mathcal{D}$ cross $\gamma$. Since a geodesic arc cannot
cross a great circle in more than one point, there must be three distinct arcs
of $\mathcal{D}$ crossing $\gamma$.

We can improve Propositions E.11 and E.13 in the case where $R$ is an
attractor hull.

######  Proposition E.17.

Let $H$ be a non-total attractor hull of a $k$-oriented SD $\mathcal{D}$, and
let $x$ be a point of $\mathcal{D}$ that lies in the interior of $H$. Then,
for every great circle $\gamma$ through $x$, there are three distinct arcs of
$\mathcal{D}$ that thrust the boundary of $H$ at three distinct points, all
internally $H$-connected with $x$, two of which lie on strictly opposite sides
of $\gamma$ (i.e., not on $\gamma$).

######  Proof E.18.

Since any non-total attractor hull is a spherical polygon contained in the
interior of a hemisphere, Proposition E.13 implies that there are at least
three points, all internally $H$-connected with $x$, where arcs of
$\mathcal{D}$ thrust the boundary of $H$. Moreover, each of these points
belongs to a distinct arc of $\mathcal{D}$, due to Proposition E.3. To
conclude the proof, it suffices to show that two such points lie on opposite
sides of $\gamma$.

Proposition A.1 implies that $x$ is internal to a unique arc
$a\in\mathcal{D}$. By Proposition E.3, at least one endpoint $x^{\prime}$ of
$a$ lies in the interior of $H$; $a$ hits another arc
$a^{\prime}\in\mathcal{D}$ at $x^{\prime}$.

Assume first that $a$ crosses $\gamma$ at $x$, i.e., $a$ does not lie on
$\gamma$. Proceeding as in the proof of Proposition E.11, we construct two
paths from $x$, following $a$ in opposite directions away from $\gamma$. The
points $y$ and $z$ thus obtained are therefore on strictly opposite sides of
$\gamma$.

Assume now that $a$ does not cross $\gamma$, hence it lies on it. Therefore,
$a^{\prime}$ crosses $\gamma$ at $x^{\prime}$, which is internally
$H$-connected with $x$. Thus, we can repeat the previous argument with
$x^{\prime}$ and $a^{\prime}$ in lieu of $x$ and $a$.

######  Proposition E.19.

Let $H$ be a non-total attractor hull of a $k$-oriented SD $\mathcal{D}$, and
let $x$ be a point of intersection between an arc of $\mathcal{D}$ and the
interior of $H$. Then, there are three distinct arcs of $\mathcal{D}$ that
thrust the boundary of $H$ at three distinct points, not all lying on the same
edge of $H$, all of which are internally $H$-connected with $x$.

######  Proof E.20.

By Proposition E.17, there are three arcs of $\mathcal{D}$ that thrust the
boundary of $H$ at distinct points, all internally $H$-connected with $x$. If
no edge of $H$ contains all such points, we are finished. Otherwise, all such
points lie on the same edge $e$ of $H$. Also, $e$ is unique, because at least
one of the three points is internal to $e$. Let $\gamma$ be a great circle
through $x$ that does not intersect $e$ (note that $\gamma$ exists because $e$
is shorter than a great semicircle). By Proposition E.17 there is a point,
internally $H$-connected with $x$ and not lying on $e$, where an arc of
$\mathcal{D}$ thrusts the boundary of $H$. Such an arc is distinct from the
previous ones due to Proposition E.3.

It is easy to see that the previous results cannot be improved, as there are
$k$-oriented SDs whose arcs thrust the boundary of an attractor hull at
exactly three points, two of which lie on the same edge of the attractor hull.

Let $A$ be an attractor of and SD $\mathcal{D}$, and let $H$ be the attractor
hull relative to $A$, i.e., the spherical convex hull of $A$. A point of $A$
is a _boundary point_ if it lies on the boundary of $H$, and is an _internal
point_ if it lies in the interior of $H$.

######  Proposition E.21.

Let $H$ be a non-total attractor hull relative to an attractor $A$ of an SD
$\mathcal{D}$, and let $h_{1}$, $h_{2}$, …, $h_{m}$ be the boundary points of
$A$, taken in clockwise order. Let $3\leq i\leq m$, and let $p$ be the point
of intersection between $h_{1}h_{i-1}$ and $h_{2}h_{i}$. Assume that the
interiors of the triangles $h_{1}h_{2}p$ and $h_{i-1}h_{i}p$ are devoid of
points of $A$, while the triangle $h_{1}ph_{i}$ contains at most one internal
point of $A$. Then, if a point $x$ of $\mathcal{D}$ lies in the interior of
$h_{1}ph_{i}$, there exists an arc of $\mathcal{D}$ that crosses the interior
of $h_{1}h_{i}$ at a point internally $H$-connected with $x$.

######  Proof E.22.

Let $q$ be the unique internal point of $A$ contained in $h_{1}ph_{i}$, if
such point exists. Let $w$ be a sliding walk starting from $x$ with the
following properties. As long as $w$ is in the interior of an arc
$a\in\mathcal{D}$ with a vanishing point $v\in h_{1}h_{i}h_{i+1}\dots h_{m}$,
$w$ proceeds along $a$ in the direction of $v$. Instead, if $a$ has a
vanishing point $v\in ph_{2}h_{3}\dots h_{i-1}$, then $w$ follows $a$ in the
direction away from $v$. If $q$ is a vanishing point of $a$, then $w$ follows
$a$ in the direction of $q$ if and only if $w$ is outside of the triangle
$h_{1}qh_{i}$.

Observe that $h_{1}ph_{i}$ is the intersection of all the triangles of the
form $h_{1}vh_{i}$, with $v$ in the spherical polygon $ph_{2}h_{3}\dots
h_{i-1}$. Therefore, $w$ always remains within the interior of $h_{1}ph_{i}$,
approaching the triangle $h_{1}qh_{i}$ as long as it is outside of it, and
then approaching $h_{1}h_{i}$ while it is in $h_{1}qh_{i}$. Thus, $w$
eventually crosses the interior of $h_{1}h_{i}$ at a point internally
$H$-connected with $x$.

Note that Proposition E.21 cannot be improved, as there are counterexamples
where $h_{1}h_{2}p$ or $h_{i-1}h_{i}p$ contains an internal attractor point or
$h_{1}ph_{i}$ contains two internal attractor points.

######  Corollary E.23.

With the notation of Proposition E.21, if a point $x$ of $\mathcal{D}$ lies in
the interior of $h_{1}h_{2}h_{3}$, and $h_{1}h_{2}h_{3}$ contains at most one
internal point of $A$, then there is an arc of $\mathcal{D}$ that crosses the
interior of $h_{1}h_{3}$ at a point internally $H$-connected with $x$.

######  Proof E.24.

It is immediate from Proposition E.21 with $i=3$. Note that $p=h_{2}$, and
therefore the triangles $h_{1}h_{2}p$ and $h_{i-1}h_{i}p$ degenerate to the
edges $h_{1}h_{2}$ and $h_{2}h_{3}$. Since the interiors of such edges are
empty, they are automatically devoid of points of $A$.

We say that an attractor hull of a $k$-oriented SD is _void_ if it is a
spherical $k$-gon, i.e., there are no poles or anti-poles in its interior. In
the case of void attractor hulls, we have an improved version of Proposition
E.19.

######  Proposition E.25.

Let $H$ be a void non-total attractor hull of a $k$-oriented SD $\mathcal{D}$,
and let $x$ be a point of $\mathcal{D}$ that lies in the interior of $H$.
Then, there are at least three distinct arcs of $\mathcal{D}$ that cross
(respectively, thrust) the boundary of $H$ at distinct points, not all lying
on the same two edges of $H$, all of which are $H$-connected (respectively,
internally $H$-connected) with $x$.

######  Proof E.26.

Note that it suffices to prove that there are arcs of $\mathcal{D}$ that
thrust (rather than cross) the boundary of $H$ in at least three distinct
points, not all lying on the same two edges of $H$, all of which are
internally $H$-connected with $x$. Indeed, given these points, Proposition E.5
easily implies that there are also at least three crossing points with the
desired properties. In addition, Proposition E.3 implies that all such points
lie on distinct arcs of $\mathcal{D}$.

Let $Y$ be the set of points on the boundary of $H$ such that, for all $y\in
Y$ there is an arc of $\mathcal{D}$ that thrusts the boundary of $H$ at $y$,
and $y$ is internally $H$-connected with $x$. By Proposition E.19, $Y$
contains at least three points, and no single edge of $H$ contains all of
them. Assume for a contradiction that all points of $Y$ lie within two edges
of $H$, say $e_{1}=h_{1}h_{2}$ and $e_{2}=h_{i-1}h_{i}$. Without loss of
generality, $e_{1}$ contains at least two points of $Y$, say $y_{1}$ and
$y_{2}$, and $e_{2}$ contains at least one point of $Y$, say $y_{3}$.

Recall that $y_{1}$ and $y_{3}$ are internally $H$-connected (with respect to
$\mathcal{D}$) by a path $P_{1}$ along $\mathcal{D}$. Similarly, $y_{2}$ and
$y_{3}$ are internally $H$-connected (with respect to $\mathcal{D}$) by a path
$P_{2}$. It is easy to recognize that the union of $P_{1}$ or $P_{2}$ (whose
points are all internal to $H$, except for $y_{1}$, $y_{2}$, $y_{3}$) contains
a point $x^{\prime}$ such that either $x^{\prime}=p$ or $x^{\prime}$ lies in
the interior of one of the triangles $h_{1}ph_{i}$ and $h_{2}h_{i-1}p$.

We can exclude the case $x^{\prime}=p$, because any arc $a\in\mathcal{D}$ that
has $p$ in its interior and avoids the interiors of $h_{1}ph_{i}$ and
$h_{2}h_{i-1}p$ must overlap with $h_{1}h_{i-1}$ or with $h_{2}h_{i}$. This is
because $a$ is collinear with a vertex of $H$, and there are no vertices of
$H$ in the interior of $h_{1}h_{2}$ or in the interior of $h_{i-1}h_{i}$.
Then, by Proposition E.3, $a$ has an endpoint in the interior of
$h_{1}h_{i-1}$ or in the interior of $h_{2}h_{i}$, where it hits another arc
$a^{\prime}\in\mathcal{D}$, which in turn intersects the interior of
$h_{1}ph_{i}$ or $h_{2}h_{i-1}p$, respectively.

Therefore, without loss of generality, we may assume that $x^{\prime}$ is in
the interior of $h_{1}ph_{i}$. Also, $x^{\prime}$ is internally $H$-connected
with $x$, because it lies on $P_{1}$ or on $P_{2}$. Note that $H$ and
$x^{\prime}$ satisfy the hypotheses of Proposition E.21, because $H$ is void.
Thus, there is an arc of $\mathcal{D}$ that crosses $h_{1}h_{i}$ at an
internal point $x^{\prime\prime}$, which is internally $H$-connected with
$x^{\prime}$ (hence with $x$). If $h_{1}h_{i}$ is an edge of $H$, we have
reached a contradiction, because $x^{\prime\prime}\in Y$, but
$x^{\prime\prime}$ is not in $e_{1}$ or in $e_{2}$.

Otherwise, $h_{1}h_{i}$ is a diagonal of $H$; let $\gamma$ be the great circle
containing $h_{1}h_{i}$. By Proposition E.17, since $x^{\prime\prime}$ lies in
the interior of $H$, there is an arc of $\mathcal{D}$ that thrusts the
boundary of $H$ at a point $z$ on the side of $\gamma$ opposite to $e_{1}$ and
$e_{2}$. Moreover, $z$ is internally $H$-connected with $x^{\prime\prime}$,
and therefore with $x$. Hence $z\in Y$, which contradicts the fact that $z$ is
not in $e_{1}$ or in $e_{2}$.

We conclude that no two edges of $H$ contain all points of $Y$, as desired.

Again, Proposition E.25 cannot be improved, in the sense that there are
counterexamples where exactly one attractor point lies in the interior of $H$.

##  Appendix F Open Problems

We conclude this paper with some directions for future research.

Although we have proved all the results listed in Table 1, which include all
non-degenerate configurations of $k$-oriented SDs and SODs, several degenerate
configurations are still unexplored. These include $6$-oriented SDs with
alignment $(2,3,3,3,4,4)$ and $(4,4,4,4,4,4)$, both of which have two triplets
of collinear poles (in the former case, one pole lies at the intersection of
the two great circles containing all other poles). In fact, even classifying
all degenerate configurations of $k\geq 6$ poles is a challenge in itself.

######  Open Problem 1.

Extend Table 1 to all degenerate $k$-oriented SDs and SODs for $k\geq 6$.

In particular, Table 1 still leaves a small uncertainty on the minimum number
of swirls in a $5$-oriented SD with alignment $(3,3,3,4,4)$, which is either
four or five. Although the analysis in Lemma 3.13 can give insights on this
configuration, it is not quite sufficient.

######  Open Problem 2.

Determine if there are $5$-oriented SDs with alignment $(3,3,3,4,4)$ having
exactly four swirls.

Figure 8(b) shows a non-degenerate $5$-oriented SD with exactly four swirls
and nine arcs. By $\epsilon$-doubling the green and the red arc, we obtain a
non-degenerate $5$-oriented SOD with exactly four swirls and $11$ arcs.
However, there is still a gap between this number and the absolute minimum
number of arcs in a non-degenerate $5$-oriented SOD, which is nine.

######  Open Problem 3.

Determine if there exist non-degenerate $5$-oriented SODs with exactly four
swirls and fewer than $11$ arcs.

In Section 1.1, we remarked that, for any sufficiently large $k$, there are
$k$-oriented SODs that are not the visibility map of any vertex-hidden point
in a polygonal scene, due to the main result of [6]. It would be interesting
to determine if this is true for all $k$.

######  Open Problem 4.

Determine all values of $k$ such that any $k$-oriented SOD is the visibility
map of a vertex-hidden point in a $k$-edge-oriented polygonal scene.

Furthermore, to address our original motivating question in Section 1.2, we
would like to find examples of $k$-edge-oriented polygonal scenes matching the
numbers in the last column of Table 1. The main contribution of [8] is a first
step in this direction, as it provides a polygonal scene where a vertex-hidden
point sees exactly eight edges.

######  Open Problem 5.

For every $k$, determine whether there are $k$-edge-oriented polygonal scenes
where a vertex-hidden point sees a number of edges that matches the minimum
number of arcs in a non-degenerate $k$-oriented SOD.

In Theorem 2.2, we proved that any SD has at least two clockwise swirls and
two counterclockwise swirls. However, this says nothing about whether these
swirls are contiguous.

######  Open Problem 6.

Determine if all SDs have at least two clockwise swirls and two
counterclockwise swirls, all of which are non-contiguous.

Theorem 2.2 cannot be improved for $4$-oriented SDs, since it is possible to
slightly modify the SD in Figure 6(a) to obtain a $4$-oriented SD with
alignment $(2,2,2,3)$ having exactly two clockwise swirls. Doubling some of
its edges also yields an SOD with the same property. However, perhaps Theorem
2.2 can be improved for $3$-oriented SDs.

######  Open Problem 7.

Determine if all $3$-oriented SDs have at least four clockwise swirls and four
counterclockwise swirls.

Since every octant of a $3$-oriented SD is a void attractor hull, it
immediately follows from Corollary E.23 that the interiors of all three edges
of each octant must be crossed by arcs. Thus, the swirl graph of any
$3$-oriented SD with exactly $12$ arcs has an induced subgraph isomorphic to
the cubical graph. However, this is not enough to characterize the swirl
graphs of such minimal $3$-oriented SDs: in fact, there are $3$-oriented SDs
that have more than eight swirls in spite of having exactly $12$ arcs (some
swirls may revolve around poles and be contiguous to some of the other
swirls).

######  Open Problem 8.

Characterize the swirl graphs of $3$-oriented SDs with exactly $12$ arcs.

Observe that, in a $k$-oriented SD, the degree of a swirl cannot exceed $2k$,
because at most two arcs in the swirl may have the same vanishing points.
Nonetheless, the degree of a swirl may very well exceed $k$, although it is
shown in [13] that any _swirling_ SOD must have a swirl of degree exactly
three. Still, not much is known about non-swirling SODs.

######  Open Problem 9.

Determine if there is a $k$-oriented SOD where all swirls have degrees
exceeding $k$.

Theorem 3.19 implies that there is a continuum of configurations of six poles
that allow for the construction of $6$-oriented SDs with exactly six arcs. In
principle, however, there may be non-degenerate configurations of six (or
more) poles that make this construction impossible.

######  Open Problem 10.

Determine if it is always possible to construct a non-degenerate $6$-oriented
SD with exactly six arcs, given the locations of its six poles.