# Partitioning a Polygon Into Small Pieces

Mikkel Abrahamsen Department of Computer Science, University of Copenhagen,
<EMAIL_ADDRESS>Supported by Starting Grant 1054-00032B from the Independent
Research Fund Denmark under the Sapere Aude research career programme and is
part of Basic Algorithms Research Copenhagen (BARC), supported by the VILLUM
Foundation grant 16582. Nichlas Langhoff Rasmussen Department of Computer
Science, University of Copenhagen<EMAIL_ADDRESS>
(November 2022)

###### Abstract

We study the problem of partitioning a given simple polygon $P$ into a minimum
number of polygonal pieces, each of which has bounded size. We give algorithms
for seven notions of ‘bounded size,’ namely that each piece has bounded area,
perimeter, straight-line diameter, geodesic diameter, or that each piece must
be contained in a unit disk, an axis-aligned unit square or an arbitrarily
rotated unit square.

A more general version of the area problem has already been studied. Here we
are, in addition to $P$, given positive real values $a_{1},\ldots,a_{k}$ such
that the sum $\sum_{i=1}^{k}a_{i}$ equals the area of $P$. The goal is to
partition $P$ into exactly $k$ pieces $Q_{1},\ldots,Q_{k}$ such that the area
of $Q_{i}$ is $a_{i}$. Such a partition always exists, and an algorithm with
running time $O(nk)$ has previously been described, where $n$ is the number of
corners of $P$. We give an algorithm with optimal running time $O(n+k)$. For
polygons with holes, we get running time $O(n\log n+k)$.

For the other problems, it seems out of reach to compute optimal partitions
for simple polygons; for most of them, even in extremely restricted cases such
as when $P$ is a square. We therefore develop $O(1)$-approximation algorithms
for these problems, which means that the number of pieces in the produced
partition is at most a constant factor larger than the cardinality of a
minimum partition. Existing algorithms do not allow Steiner points, which
means that all corners of the produced pieces must also be corners of $P$.
This has the disappointing consequence that a partition does often not exist,
whereas our algorithms always produce useful partitions. Furthermore, an
optimal partition without Steiner points may require $\Omega(n)$ pieces for
polygons where a partition consisting of just $2$ pieces exists when Steiner
points are allowed.

##  1 Introduction

Polygons are among the geometric structures that are most widely used to model
physical objects, as they are suitable for representing a wide variety of
shapes and figures in computer graphics and vision, pattern recognition,
robotics, computer-aided design and manufacturing, and other computational
fields. It is often desirable to _decompose_ a polygon $P$ into polygonal
_pieces_ which are in some sense simpler than the original polygon $P$. Here,
the union of the pieces should be $P$, and we usually seek a partition into as
few pieces as possible. A decomposition where the pieces can overlap is also
called a _cover_ , and if they are pairwise interior-disjoint, it is called a
_partition_. Depending on the assumptions about the input polygon $P$ and the
requirements of the pieces, this leads to a wealth of interesting problems.
There is a vast literature about such decomposition problems, as documented in
several highly-cited books and survey papers that give an overview of the
state-of-the-art at the time of publication [51, 21, 19, 39, 40, 47, 48]. A
_Steiner point_ is a corner of a piece in a decomposition which is not a
corner of the input polygon $P$. In this paper, we study partitioning problems
with Steiner points allowed where we require each piece to be of _bounded
size_. We will describe algorithms for constructing the following six types of
partitions:

  * •

Aligned square partition: Each piece is contained in an axis-aligned unit
square.

  * •

Rotated square partition: Each piece is contained in an arbitrarily rotated
unit square.

  * •

Disk partition: Each piece is contained in a unit disk, i.e., a disk of radius
$1$.

  * •

Straight diameter partition: The straight-line diameter of each piece is at
most $1$.

  * •

Geodesic diameter partition: The geodesic diameter of each piece is at most
$1$.

  * •

Perimeter partition: The perimeter of each piece is at most $1$.

An additional and very natural variant would be to partition $P$ into pieces
of area at most $1$. In fact, a partition into the optimal number
$\lceil\operatorname{area}P\rceil$ of such pieces always exists. We study the
following more general _area partitioning problem_ : Given a polygon $P$ and
positive real values $a_{1},\ldots,a_{k}$ with
$\operatorname{area}P=\sum_{i=1}^{k}a_{i}$, compute a partition of $P$ into
pieces $Q_{1},\ldots,Q_{k}$ such that $\operatorname{area}Q_{i}=a_{i}$. As we
will see, such a partition can be found in optimal time $O(n+k)$ if $P$ is a
simple polygon and in time $O(n\log n+k)$ if $P$ has holes. This improves on a
result by Bast and Hert [7], who gave an algorithm with running time $O(nk)$.

######  Theorem 1.

There exists an algorithm that for a given simple polygon $P$ with $n$ corners
and positive real values $a_{1},\ldots,a_{k}$ with
$\operatorname{area}P=\sum_{i=1}^{k}a_{i}$ produces a partition
$Q_{1},\ldots,Q_{k}$ with $\operatorname{area}Q_{i}=a_{i}$ in optimal time
$O(n+k)$. If $P$ is a polygon with holes, a partition can be found in time
$O(n\log n+k)$.

For the other problems, it seems very difficult to compute optimal partitions
of simple polygons. Except for aligned square partitions, this is even the
case in extremely restricted settings: if $P$ is a (big) square or an
equilateral triangle, it seems out of reach to efficiently compute optimal
rotated square, disk, diameter (straight as well as geodesic) and perimeter
partitions of $P$. Indeed, the disk partitioning problem is closely related to
the problem of covering a square or an equilateral triangle by a given number
$k$ of disks, minimizing the size of the largest disk. When covering a square,
optimal solutions are only known for $k\in\\{1,\ldots,5,7\\}$ [31] and for an
equilateral triangle, optimal solutions for $k\leq 6$ are known [44].
Likewise, the rotated square partitioning problem is closely related to the
problem of covering a bigger square with a minimum number of unit squares,
which has received some attention in mathematics [34, 52]. It is, for
instance, not known if $6$ or $7$ unit squares are needed to cover a square
with edge length $2+\varepsilon$ for an arbitrarily small value
$\varepsilon>0$ [34]. See also the webpage [28] for an overview of the best-
known solutions to these and similar problems.

We therefore develop approximation algorithms instead, i.e., algorithms that
produce partitions of cardinality at most a constant factor $\alpha$ larger
than that of a minimum partition. We use opt to denote the cardinality of an
optimal partition of a particular type. We distinguish between _estimation
time_ and _construction time_. Estimation time is the time it takes to compute
a number $x$ such that ${\textsc{opt}}\leq x\leq\alpha\cdot{\textsc{opt}}$.
Construction time is the time it takes to construct an actual partition with
at most $\alpha\cdot{\textsc{opt}}$ pieces. Note that
$\Omega(n+{\textsc{opt}})$ time is needed for construction, and opt can be
superpolynomial in $n$, for instance if $P$ is just a big square. In contrast
to many other partitioning problems, such as triangulation, trapezoidation or
partitioning into convex pieces, it is therefore not possible to solve the
construction problem in $O(\operatorname{poly}n)$ time. Our results can be
seen in Table 1.

Type | Apx. factor | Estimation time | Construction time
---|---|---|---
Aligned square | $13$ | $O(n)$ | $O(n^{2}+{\textsc{opt}}\log n)$
Rotated square | $21$ | $O(n\log n)$ | $O(n^{2}+{\textsc{opt}}\log n)$
Disk | $20+\pi/2$ | $O(n\log n)$ | $O(n^{2}+{\textsc{opt}}\log n)$
Straight diameter | $20+\pi/2$ | $O(n\log n)$ | $O(n^{2}+{\textsc{opt}}\log n)$
Geodesic diameter | $72$ | $O(n^{2}\log n)$ | $O(n^{2}\log n+{\textsc{opt}}\log n)$
Perimeter | $3728$ | $O(n^{2})$ | $O(n^{2}+{\textsc{opt}}\log n)$
Table 1: Approximation factors and running times of our algorithms for solving
the various partitioning problems. Recall that opt denotes the cardinality of
an optimal partition of the respective type and $n$ the number of corners of
$P$.

######  Theorem 2.

For aligned and rotated square, disk, straight and geodesic diameter, and
perimeter partitions, there exist algorithms with running times
$O(\operatorname{poly}n)$ for computing a constant factor estimate of opt and
algorithms with running times $O(\operatorname{poly}n+{\textsc{opt}}\log n)$
for constructing a partition with at most that cardinality. The approximation
factors and running times for each type are stated in Table 1.

Figure 1: The spirals indicate that we cannot use an algorithm for aligned
square partitions or straight diameter partitions to get an algorithm for the
other problem.

Let us note that a $O(1)$-approximation algorithm for one of our problems does
not seem to be useful (as a black box) in order to get a $O(1)$-approximation
algorithm for another; see Figure 1. A polygon of straight diameter at most
$1$ is also contained in an aligned unit square, but a straight diameter
partition of the left spiral has $\Omega(n)$ pieces while an aligned square
partition of one piece exists. On the other hand, a polygon contained in an
aligned square of side length $1/\sqrt{2}$ has straight diameter at most $1$,
but a partition into aligned $1/\sqrt{2}$-squares of the right spiral needs
$\Omega(n)$ pieces while a straight diameter partition of one piece exists.

Variants of some of our partitioning problems have been studied before when
Steiner points are not allowed in the produced partition. Damian and Pemmaraju
[24] described a polynomial-time algorithm to produce an optimal disk
partition without using Steiner points. Unfortunately, such a partition does
often not exist, which may be rather unsatisfactory. For instance, no disk
partition exists if $P$ is a triangle with an edge of length more than $2$.

Another advantage of our partitions is that they are often significantly
smaller than partitions without Steiner points. Figure 2 shows that
$\Omega(n)$ pieces are sometimes needed when Steiner points are not allowed
for polygons where $2$ pieces are enough when they can be used.

Figure 2: Two disk partitions of the same polygon $P$. The corners of $P$ are
contained in two concentric circular arcs. The concave arc has radius
$1+\varepsilon$ for a small value $\varepsilon>0$. The convex arc has radius
$2$. The left partition is a disk partition when Steiner points are not
allowed, where $\Omega(n)$ pieces are needed. The right is a partition of
cardinality $2$ using Steiner points.

###  1.1 Practical motivation

Besides being intriguing from a theoretical point of view, our partitioning
problems are motivated by practical situations in various domains. Damian and
Pemmaraju [24] described collision detection as their motivation for finding
optimal disk partitions (without Steiner points allowed). When testing if two
objects collide, a common technique is to first check if their bounding boxes
overlap, and only then consider the actual geometry of the objects. Experience
suggests that the method of first testing the bounding boxes works best if the
objects are of similar size. It might therefore be advantageous to first
partition the objects into pieces of bounded size and use the bounding box
heuristic on these pieces.

Hert and Lumelsky [33] described a version of the area partitioning problem
where we want to partition a workspace, i.e., a polygon $P$, among a set of
agents, so that each agent gets assigned a region with a certain area. The
area of a region corresponds to the amount of work that the respective agent
is capable of. Carlsson, Armbruster and Ye [17] gave a solution to another
version where $P$ is convex and all regions are also required to be convex.
The motivation was that an agent in each region should be able to service a
set a clients in the region and get back to its depot as quickly as possible.
Convex regions are desirable because the authors “expect that odd-shaped
regions take longer to service than more compact regions with the same area.”
However, a convex region may have arbitrarily large diameter, so it can take
arbitrarily long time for the agent to get from one costumer to another. In
this context it would then be natural to require the straight or geodesic
diameter of each region to be bounded, so that the agent in a region could get
to any other desired point in the region within a certain amount of time.
Bounded straight diameter is relevant for flying agents like drones, whereas
geodesic is relevant for land vehicles. We would therefore seek a partition of
the workspace into a minimum number of regions of bounded straight or geodesic
diameter, which are among our studied variants.

Rotated square partitions are motivated by sheet metal cutting: Suppose we
want to cut out pieces from a big sheet of metal so that they can be welded
together to form a certain shape $P$. The pieces are to be shipped in a
container whose base is a unit square. We then want to partition $P$ into
pieces that fit in a unit square, and the number of pieces should be minimized
so that it takes less work to weld them in the end. In a related everyday
situation, we want to print a map of an area $P$ which is bigger than the
paper size, so we seek a partition of $P$ into few pieces each of which can be
printed on one paper.

###  1.2 Techniques

We use completely different techniques for the area partitioning problem and
the other problems. For the area partitioning problem, we first construct a
_Hamiltonian triangulation_ of the polygon $P$ using Steiner points. This is a
triangulation where the dual graph contains a Hamiltonian cycle $C$. The
Hamiltonian triangulation is obtained from a usual triangulation by adding the
medians of all the triangles. We then construct the pieces of our partition in
a greedy manner as we traverse the cycle $C$. Figure 3 shows an example of the
triangulation and a partition produced by the algorithm. The details are given
in Section 3.

Figure 3: Left: A triangulated polygon. Middle: The triangulation we obtain
after adding all medians of the triangles. The Hamiltonian cycle $C$ is also
shown. Right: An area partition into five pieces produced by our algorithm.
Figure 4: An aligned square partition. The boundary pieces are blue, and they
cover all of the boundary, although they are in some places degenerate so that
they cannot be seen. The yellow, red and green pieces are so-called complete,
edge and chip pieces, respectively. Color codes: 1 blue, 2 yellow, 3 red, 4
green.

The algorithms for the other problems are more involved, but they all follow
the same two main steps; see Figure 4 for an example of an aligned square
partition produced by our algorithm.

  1. 1.

We first construct a set of pieces $\mathcal{Q}_{\partial}$ that cover all of
the boundary of $P$. We use a greedy algorithm that repeatedly finds a maximal
interval on the boundary of $P$ which can be contained in a single piece. The
way we turn these intervals into actual pieces depends on the specific
problem. These pieces are called _boundary_ pieces. As we will see,
constructing the pieces in a greedy manner results in at most
$2\,{\textsc{opt}}$ pieces (recall that opt denotes the cardinality of an
optimal partition of the entire polygon $P$). This step is described in
Section 4.

  2. 2.

After constructing the boundary pieces, we consider a regular square grid
which covers all of $P$, where the edge length of each square is some constant
$\gamma>0$ to be chosen depending on the problem. This grid is used to
construct the _interior pieces_ $\mathcal{Q}_{\circ}$. For square111When we
speak about “square partitions” without specifying whether it is aligned or
rotated square partitions, we mean both types., disk and straight diameter
partitions, the interior pieces are simply chosen as the regions in each grid
square which are inside $P$ but not inside a boundary piece. As we will see,
there are $O({\textsc{opt}})$ of these regions due to the way we construct the
boundary pieces.

The construction is more involved for geodesic diameter and perimeter
partitions, as a region in a square can have arbitrarily large geodesic
diameter or perimeter. Here we develop a method to split each region into
smaller subregions, each of which has bounded geodesic diameter and perimeter.
The pieces will then be unions of these subregions. This step is described in
Section 5.

###  1.3 Other related work

Fekete, Kamphans, Kröller, Mitchell and Schmidt [27] (see also the video [8])
gave an algorithm for placing robots in a polygon $P$ such that their
communication graph is a triangulation of $P$. The robots have restricted
communication range which means that each edge of the triangulation can have
length at most $1$. In other words, we are seeking a triangulation of $P$ with
Steiner points allowed so that each edge has length at most $1$. The objective
is to minimize the number of robots, i.e., vertices in the triangulation. The
robots are placed in three phases. In each of these phases, it is shown that
at most opt robots are placed, so it follows that the algorithm gives a
$3$-approximation to the minimal number of robots. The first phase is
analogous to our phase 1 of covering the boundary of $P$, and the other two
phases correspond to some degree to our phase 2.

Motivated by indoor localization using tripwire lasers, Arkin, Das, Gao,
Goswami, Mitchell, Polishchuk and Tóth [5] recently studied problems of the
type where we want to cut a polygon into small pieces using a minimum number
of chords of $P$ (each chord corresponds to a laser which can detect if
something is blocking the beam). As measures for the size of a piece $Q$, they
used area, straight diameter and in-circle radius, i.e., the radius of the
largest circle contained in $Q$. They gave, among other results, an
$O(1)$-approximation algorithm for finding the minimum number of chords used
to partition $P$ into pieces of bounded straight diameter.

The algorithmic problems of partitioning polygons into pieces of bounded size
have older roots in pure mathematics. For instance, in the _Borsuk problem_ ,
we consider a convex body $P$ in $\mathbb{R}^{d}$ of diameter $1$ and want to
partition $P$ into a minimum number of pieces, each of which has diameter less
than $1$. This problem has a rich history; see [14, 35, 37] for a few
references. In _Conway’s fried potato problem_ [11, 12, 16, 23], we seek to
minimize the maximum in-radius of each piece after a given number of
successive cuts by hyperplanes for a given convex polyhedron in
$\mathbb{R}^{d}$.

Hert and Lumelsky [33] studied a specialized version of area partitioning
problem: The input consists of the polygon $P$, the areas $a_{1},\ldots,a_{k}$
and _anchor points_ $p_{1},\ldots,p_{k}$. We must find a partition where each
piece $Q_{i}$ has area $a_{i}$ and contains its anchor point $p_{i}$.
Carlsson, Armbruster and Ye [17] and Adjiashvili and Peleg [3] studied a
version of the same problem where $P$ is convex and each piece must also be
convex. Other problems related to the area partitioning problem are the
_equipartition problems_ , where we seek to partition a convex polygon into
convex pieces all having the same area or the same perimeter or both (or
another measure) [13, 29, 38, 46, 6].

###  1.4 Open questions

We close this introduction by suggesting some directions for future research.
We believe that our techniques can also be adapted to find
$O(1)$-approximations of other natural variants of the problem of partitioning
a simple polygon into small pieces. These include partitions into pieces each
of which is contained in an equilateral triangle of fixed size (or any other
fixed polygon), which can either be allowed to be arbitrarily rotated or not.
Another version is pieces with bounded geodesic radius, which is closely
related to the geodesic diameter partitioning problem, but it seems more
involved to find a good boundary partition.

Despite some efforts, we were not able to find algorithms for partitioning
polygons with holes (except for the area partitioning problem, where our
algorithm does handle polygons with holes). Here we would also allow the
pieces to have holes. It is interesting whether such algorithms can be found.
Another interesting direction, which, however, seems even more difficult,
would be to find algorithms for partitioning three-dimensional (non-convex)
polyhedra into small pieces. One could imagine applications of such algorithms
in computer-aided design and manufacturing, in particular in 3D printing:
Suppose we want to print a polyhedron $P$ which is too large to fit in the
printing volume of the printer. We may then want to partition $P$ into a
minimum number of pieces, each of which is sufficiently small to be printed,
and then glue together the pieces in the end to obtain the polyhedron $P$.
Heuristics have been proposed to solve this problem [42, 22, 36], and several
videos can be found on YouTube showing how it can be done manually using
various software (for instance, search for “splitting large part for 3D
printing”).

Worman [55] showed that it is NP-hard to find an optimal aligned square
partition of a polygon _with holes_ when Steiner points are not allowed by a
reduction from Planar 3,4-SAT. Buchin and Selbach [15] recently showed that
the same holds for disk partitions by a similar reduction. We would expect
that the same technique can be used to show NP-hardness of finding optimal
partitions when Steiner points are allowed, also for the remaining types of
partitions. It would, however, be much more interesting to show some form of
hardness for the case where $P$ is a simple polygon. In general, it seems that
no partitioning problem for simple polygons is known to be hard (but see the
paper [49], which comes close).

Another research direction would be to consider covers instead of partitions.
Some covering problems have been shown to be $\exists\mathbb{R}$-complete [2,
1], but these proofs rely on the use of some very long pieces that can cover
distant regions of the polygon, so we wonder if size-constraint covering
problems are also $\exists\mathbb{R}$-complete. It is interesting if
$O(1)$-factor approximation algorithms can also be devised for the covering
versions of the problems of this paper.

Yet another direction would be to consider a dual version of the partitioning
problems: We specify the number of pieces as part of the input and seek a
partition of the polygon $P$ into that number of pieces, where the objective
is to minimize the size of the largest piece. The size would be measured as
the smallest enclosing disk or square, the straight or geodesic diameter or
the perimeter. The paper [5] contains results on problems of this sort, where
instead of fixing the number of pieces, we fix the number of cuts we are
allowed to make along chords in $P$.

##  2 Preliminaries

A _simple polygon_ is a compact region in the plane whose boundary is a
simple, closed curve consisting of finitely many line segments. For technical
reasons, we allow the pieces of a partition to be weakly simple polygons. A
_weakly simple polygon_ $Q$ is a simply-connected and compact region in the
plane whose boundary is a union of finitely many line segments. In particular,
a simple polygon is also a weakly simple polygon, but the opposite is not true
in general. For instance, a weakly simple polygon $Q$ may have a disconnected
or even empty interior. However, just as for a simple polygon, a weakly simple
polygon $Q$ can be defined by its edges in counterclockwise order around the
boundary. These edges form a closed boundary curve $\gamma$ of $Q$. Since $Q$
is weakly simple, some corners may coincide, and edges may overlap. After a
perturbation of $\gamma$ which is arbitrarily small with respect to Frechet
distance, $Q$ can be turned into a simple polygon [4, 18]. This perturbation
may involve the introduction of more corners. For instance, if $Q$ is just a
line segment, then $Q$ has only two corners, and one more is needed to obtain
a simple polygon.

We denote the boundary of a weakly simple polygon $P$ as $\partial P$. For two
boundary points $a,b\in\partial P$, we denote by $\partial P[a,b]$ the
interval on the boundary from $a$ to $b$ in counterclockwise direction. As
with intervals on the real number line, we can use square or round brackets to
indicate whether each of the endpoints $a$ and $b$ are included in the
interval or not.

We now define a _partition_ of a polygon $P$ to be a set of weakly simple
polygons $Q_{1},\ldots,Q_{k}$ such that after an arbitrarily small
perturbation of the pieces, we obtain _simple_ polygons
$Q^{\prime}_{1},\ldots,Q^{\prime}_{k}$ with the following properties:

  1. 1.

The polygons $Q^{\prime}_{1},\ldots,Q^{\prime}_{k}$ are pairwise interior-
disjoint.

  2. 2.

$\bigcup_{i=1}^{k}Q^{\prime}_{i}=P$.

Note that it follows that the weakly simple polygons $Q_{1},\ldots,Q_{k}$ must
also have properties 1 and 2 (with $Q^{\prime}_{i}$ replaced by $Q_{i}$ for
all $i\in\\{1,\ldots,k\\}$), since otherwise a large perturbation would be
needed for them to be transformed into simple polygons with the required
properties. However, it would not be sufficient to define a partition as a set
of weakly simple polygons with properties 1 and 2 alone. This would, for
instance, allow two pieces with empty interiors (such as two segments) to
properly intersect each other, which is not intended.

For a weakly simple polygon $P$, we define the _straight-line diameter_ (or
simply _straight diameter_) of $P$ as $\operatorname{diam}P=\sup_{p,q\in
P}\lVert p-q\rVert$. For two points $p,q\in P$, we denote by
$\pi(p,q)=\pi_{P}(p,q)$ a shortest path in $P$ from $p$ to $q$. We define the
_geodesic diameter_ of $P$ as
$\operatorname{diam}_{\mathrel{\leadsto}}P=\sup_{p,q\in P}\|\pi_{P}(p,q)\|$,
where $\|\cdot\|$ denotes the length. Note that $\pi(p,q)$ is a polygonal
curve whose corners, except possibly the endpoints, are concave corners of
$P$.

##  3 The area partitioning problem

In this section, we consider the area partitioning problem and consequently
prove Theorem 1. In the area partitioning problem we are given a simple
polygon $P$ and $k$ positive real values $a_{1},a_{2},\ldots,a_{k}$ such that
$\operatorname{area}P=\sum_{i=1}^{k}a_{i}$. The goal is to compute a partition
of $P$ into exactly $k$ pieces $Q_{1},Q_{2},\ldots,Q_{k}$ such that $Q_{i}$ is
a simple polygon and $\operatorname{area}Q_{i}=a_{i}$.

######  Remark.

We will assume that $P$ is a simple polygon, but the algorithm can easily be
extended to work for polygons with holes. The only additional step is to first
“remove the holes” of $P$ by connecting the holes to the outer boundary of $P$
via diagonals, ensuring that the final polygon remains connected. However, the
running time becomes $O(n\log n+k)$ instead of $O(n+k)$, since triangulating a
polygon with holes takes $O(n\log n)$ time [10].

Figure 5: Left: The triangulation $\mathcal{T}$ of the input polygon $P$.
Right: The Steiner triangulation $\mathcal{T}_{S}$ with the wall shown in blue
and the hamiltonian cycle $C$ in red.

We first compute an ordinary triangulation $\mathcal{T}$ of $P$, i.e., without
using Steiner points. We then split each triangle $\triangle\in\mathcal{T}$
into six pieces by adding the medians of $\triangle$. The resulting Steiner
triangulation is denoted $\mathcal{T}_{S}$; see Figure 5. We can compute the
original triangulation $\mathcal{T}$ in $O(n)$ time using Chazelle’s algorithm
[20], and then it is easy to compute $\mathcal{T}_{S}$ in $O(n)$ time as well
(we note that $\mathcal{T}_{S}$ has $6n-12$ triangles and $3n-5$ Steiner
points).

Each triangle in $\mathcal{T}_{S}$ either has exactly one corner or one edge
contained in $\partial P$. The cyclic order in which the triangles appear
around $\partial P$ thus induces a Hamiltonian cycle $C$ in $\mathcal{T}_{S}$.

We define the _wall_ of $\mathcal{T}_{S}$ to be the graph induced by the
vertices of $\mathcal{T}_{S}$, which are not on $\partial P$. These vertices
are the centroids of the triangles in the original triangulation $\mathcal{T}$
and the midpoints of the diagonals of $\mathcal{T}$, so it follows that the
wall is a tree. It is easy to see that each triangle in $\mathcal{T}_{S}$
either has (i) a single edge on $\partial P$ and a single vertex on the wall,
or (ii) a single edge on the wall and a single vertex on $\partial P$.

Figure 6: The construction of the two first pieces $Q_{1}$ and $Q_{2}$.

We now construct our pieces in the following way; see Figure 6. Let the
triangles of $\mathcal{T}_{S}$ be $\triangle_{1},\ldots,\triangle_{m}$ in the
order of $C$. We find the first triangle $\triangle_{i}$ such that
$\sum_{j=1}^{i}\operatorname{area}\triangle_{j}\geq a_{1}$. If $\triangle_{i}$
has an edge $e$ on $\partial P$, we cut it along a segment from the vertex on
the wall to the point on $e$ such that the part incident with
$\triangle_{i-1}$ together with the triangles
$\triangle_{1},\ldots,\triangle_{i-1}$ has area $a_{1}$, and these triangles
(the last of which is just a subset of $\triangle_{i}$) constitute the first
piece $Q_{1}$. Since $Q_{1}$ is the union of triangles visited on a path in
$C$, then $Q_{1}$ is a simple polygon. The case that $\triangle_{i}$ has an
edge $e$ on the wall and a vertex on $\partial P$ is handled similarly.

In general, when constructing a piece $Q_{i}$ with area $a_{i}$, we start at a
segment connecting $\partial P$ to the wall, which was introduced when
constructing the previous piece $Q_{i-1}$. We then proceed to traverse the
triangles in the order of $C$ until the traversed triangles have total area at
least $a_{i}$ and then make an appropriate cut.

Since we traverse through $O(n)$ triangles and we make $O(k)$ cuts, this
approach results in an algorithm with optimal running time $O(n+k)$, proving
Theorem 1.

##  4 Computing the boundary pieces

In this and the next section, we turn our attention to square, disk, straight
and geodesic diameter and perimeter partitions in order to prove Theorem 2.

A _boundary partition_ of a polygon $P$ is a set of weakly simple polygons
$Q_{1},\ldots,Q_{k}$ of bounded size such that after an arbitrarily small
perturbation of the pieces, we obtain _simple_ polygons
$Q^{\prime}_{1},\ldots,Q^{\prime}_{k}$ with the following properties:

  1. 1.

The polygons $Q^{\prime}_{1},\ldots,Q^{\prime}_{k}$ are pairwise interior-
disjoint.

  2. 2.

Each polygon $Q^{\prime}_{i}$ is contained in $P$.

  3. 3.

$\partial P\subset\bigcup_{i=1}^{k}\partial Q^{\prime}_{i}$.

  4. 4.

$\partial P\cap\partial Q^{\prime}_{i}$ is connected for each polygon
$Q^{\prime}_{i}$.

In particular, it follows that $\partial P\cap\partial Q_{i}$ may be
disconnected for a piece $Q_{i}$ in a boundary partition, but after an
arbitrarily small perturbation, we get a piece $Q^{\prime}_{i}$ where
$\partial P\cap\partial Q^{\prime}_{i}$ is connected, so other pieces must
“take over” covering the parts of $\partial P$ that $\partial Q_{i}$ covers
but $\partial Q^{\prime}_{i}$ does not. Figure 7 demonstrates the
perturbation. See also Figure 4, where the blue pieces form a boundary
partition produced by one of our algorithms. We require the pieces
$Q_{1},\ldots,Q_{k}$ of a boundary partition to have bounded size, but the
perturbed pieces $Q^{\prime}_{1},\ldots,Q^{\prime}_{k}$ might be exceed the
size constraint a bit.

Figure 7: The blue pieces form a boundary partition of a polygon $P$. The
pieces $Q_{1}$ and $Q_{2}$ are degenerate and follow the boundary of $P$ to
the point $p$. It is shown how we can make a small perturbation so that the
intersection of each piece with $\partial P$ is just a single interval.

Note that more than opt pieces may be needed to create a boundary partition
because of the last requirement that $\partial P\cap\partial Q^{\prime}_{i}$
be connected. However, as the following lemma shows, at most
$2\,{\textsc{opt}}-2$ are needed.

######  Lemma 3.

For each type of partition mentioned in Theorem 2 and any simple polygon $P$,
there exists a boundary partition of $P$ of cardinality at most
$2\,{\textsc{opt}}-2$.

###### Proof.

Consider any of the six types of partitions and let $\mathcal{Q}^{*}$ denote
an optimal partition of $P$ of that type so that
$|\mathcal{Q}^{*}|={\textsc{opt}}$. Let
$\mathcal{Q}^{*}_{b}\subset\mathcal{Q}^{*}$ denote the set of pieces of
$\mathcal{Q}^{*}$ that intersect $\partial P$, i.e.,

$\mathcal{Q}^{*}_{b}=\left\\{Q\in\mathcal{Q}^{*}\mid\partial Q\cap\partial
P\neq\emptyset\right\\}.$

Let $C$ denote the directed cycle with vertex set $\mathcal{Q}^{*}_{b}$ and
edges induced by traversing $\partial P$ in counterclockwise order: Whenever
we leave a piece $Q$ and enter another piece $Q^{\prime}$, we add an edge from
$Q$ to $Q^{\prime}$ in $C$; see Figure 8. (If some pieces of
$\mathcal{Q}^{*}_{b}$ are degenerate weakly simple polygons, this cycle $C$
may not be well-defined, but then we can consider an infinitesimal
perturbation of $\mathcal{Q}^{*}_{b}$ instead, resulting in pairwise interior-
disjoint simple polygons which we use to define $C$.) We now observe that
$|E(C)|\leq 2m-2$ by induction on the number of pieces
$m=|\mathcal{Q}^{*}_{b}|$. The base-case is $|\mathcal{Q}^{*}_{b}|=1$, where
the claim holds trivially. Suppose that the claim holds for any cycle of at
most $m-1$ pieces, and consider a cycle $C$ of $m=|\mathcal{Q}^{*}_{b}|$
pieces. If $C$ is a simple cycle of $m\geq 2$ pieces, then $|E(C)|=m\leq
2m-2$. Otherwise, there is a piece $Q$ which is visited at least twice as we
traverse $C$. We can then write $C=C_{1}\cup C_{2}$, where $C_{1}$ and $C_{2}$
are two cycles that are disjoint except that $Q$ appears in both, so we can
write the numbers of pieces as $m_{1}$ and $m_{2}$, respectively, where
$m=m_{1}+m_{2}-1$. We then get from the induction hypothesis that
$|E(C)|=|E(C_{1})|+|E(C_{2})|\leq 2m_{1}-2+2m_{2}-2=2(m_{1}+m_{2}-1)-2=2m-2$.

Figure 8: We split the pieces of an optimal partition (left) along shortest
paths in order to obtain a partition that includes a boundary partition
(right). For clarity, the endpoints of the shortest paths are not chosen as
described in the text.

We now partition each piece $Q\in\mathcal{Q}^{*}_{b}$ into
$d=\deg^{-}(Q)=\deg^{+}(Q)$ pieces as follows, where $\deg^{-}(\cdot)$ and
$\deg^{+}(\cdot)$ denote the in- and out-degree, respectively. Note that $d$
is equal to the number of intervals in $\partial P\cap\partial Q$. Denote
these intervals as $I_{1},\ldots,I_{d}$. For $i\in\\{1,\ldots,d-1\\}$, we
split $Q$ along a shortest path in $Q$ between the endpoints of $I_{i}$. It is
then clear that each of the resulting $d$ pieces has bounded size and that we
obtain a boundary partition of $P$.

We can then bound the number of pieces in our boundary partition as
$\sum_{Q\in\mathcal{Q}^{*}_{b}}\mathrm{deg}^{-}(Q)=|E(C)|\leq 2m-2\leq
2\,{\textsc{opt}}-2$, and the lemma holds. ∎

All our algorithms construct the boundary pieces in a greedy manner, as
follows. We pick an arbitrary point $a_{0}\in\partial P$. For $i=1,2,\ldots$,
we then choose the next point $a_{i}$ such that the interval $\partial
P[a_{i-1},a_{i}]$ is as large as possible while it can be covered by a single
piece $Q_{i}$ satisfying the respective size constraint. We stop when we get
to a point $a_{k-1}$ such that $\partial P[a_{k-1},a_{0}]$ can be covered by a
piece $Q_{k}$ of bounded size.

######  Lemma 4.

Let $a_{0}=a_{k}$ be an arbitrary point on $\partial P$ and let
$\mathcal{Q}_{\partial}=\\{Q_{1},\ldots,Q_{k}\\}$ be a set of pieces of
bounded size where $Q_{i}$ covers the interval $\partial P[a_{i-1},a_{i}]$ and
for $i=1,\ldots,k-1$, the endpoint $a_{i}$ is chosen so that a piece of
bounded size cannot cover a larger interval starting at $a_{i-1}$. Then
$k=|\mathcal{Q}_{\partial}|\leq 2\,{\textsc{opt}}-1$.

###### Proof.

By Lemma 3 there exists a boundary partition, $\mathcal{Q}^{*}_{\partial}$, of
cardinality at most $2\,{\textsc{opt}}-2$. Since the interval $\partial
P(a_{i-1},a_{i}]$ is chosen to be maximal, it must contain the last point of
an interval covered by one of the pieces in $\mathcal{Q}^{*}_{\partial}$. In
other words, there is at least one piece in $\mathcal{Q}^{*}_{\partial}$ for
each of the pieces $Q_{1},\ldots,Q_{k-1}$, and we have
$|\mathcal{Q}_{\partial}|\leq 2\,{\textsc{opt}}-1$. ∎

Next, we first describe how to find the maximal intervals and then how we
construct the actual pieces.

###  4.1 Finding maximal intervals

In the following we show for each type of partition how to obtain a single
maximal interval $\partial P[a_{i-1},a_{i}]$ for a given starting point
$a_{i-1}$. The remaining intervals are computed by applying this algorithm
repeatedly until we get to a point $a_{k-1}$ where $\partial P[a_{k-1},a_{0}]$
can be covered by a piece of bounded size. The point $a_{0}$ is chosen as an
arbitrary point on $\partial P$. For most types of partitions, the algorithm
consists of two phases.

  1. 1.

Given $a_{0}$ and $a_{i-1}$, consider the interval $\partial P[a_{i-1},a_{0}]$
that remains to be covered, and let $\left\\{p_{1},\ldots,p_{m}\right\\}$
denote the corners of this interval in order from $a_{i-1}$, so that
$p_{1}=a_{i-1}$ and $p_{m}=a_{0}$. In this first phase we determine the
largest index $s\in\\{2,\ldots,m+1\\}$ such that there exists a piece of
bounded size that contains the interval $\partial P[p_{1},p_{s-1}]$. If
$s=m+1$, it means the remaining part of $\partial P$ can be covered by a
single piece, and we have found all our intervals and proceed to construct the
pieces as described in Section 4.2. For each type of partition, we describe
how to find the index $s$.

  2. 2.

The maximum interval $\partial P[a_{i-1},a_{i}]$ that can be covered by a
single piece must consist of the interval $\partial P[p_{1},p_{s-1}]$ and a
prefix of the edge $p_{s-1}p_{s}$. In this second phase we find the point
$a_{i}\in p_{s-1}p_{s}$ such that $p_{s-1}a_{i}$ is this prefix.

#### Aligned square partitions.

We describe the two phases for finding the maximal intervals for the aligned
square partitions.

  1. 1.

To find the index $s$, we run through the points $\\{p_{1},\ldots,p_{m}\\}$
and keep track of the smallest and largest $x$\- and $y$\- coordinates, which
define the smallest containing axis-aligned square. The index $s$ is thus
found in $O(s)$ time.

  2. 2.

Let $R$ be the minimum axis-aligned bounding rectangle of the interval
$\partial P[p_{1},p_{s-1}]$. Clearly, there is an axis-aligned unit square $S$
covering a maximum interval of $\partial P[a_{i-1},a_{0}]$ which also has a
corner coincident with the corresponding corner of $R$. There are four unit
squares with this property, and we just need to test which one covers most of
$p_{s-1}p_{s}$; see Figure 9.

In total, the point $a_{i}$ can be found in $O(s)$ time.

Figure 9: We test four unit squares in order to find one that covers most of
the edge $p_{s-1}p_{s}$.

#### Rotated square partitions.

We describe the two phases for finding the maximal intervals for rotated
square partitions.

  1. 1.

We perform an exponential search among the points $\\{p_{1},\ldots,p_{m}\\}$
in order to find the index $s$. In each round of the search, we need to test
if an interval $\partial P[p_{1},p_{j}]$ can be covered by a rotated square.
To this end, we first compute the convex hull $\mathcal{C}$ of $\partial
P[p_{1},p_{j}]$, which can be done in $O(j)$ time, for instance using
Melkmann’s algorithm [45]. Toussaint [53] described an algorithm that runs
through the angle interval $\varphi\in[0,\pi/2)$ and at all times keep track
of the smallest rectangle $R_{\varphi}$ containing $\mathcal{C}$ and with a
pair of edges making the angle $\varphi$ with the $x$-axis. The algorithm uses
the technique of rotating calipers and the running time is $O(j)$. Let
$\ell_{\varphi}$ be the length of the longest edges of $R_{\varphi}$ (it may
change several times which pair of edges are longest). Thus, if ever
$\ell_{\varphi}\leq 1$, there exists a unit square containing $\mathcal{C}$,
otherwise not. We can therefore determine in $O(j)$ time if there exists a
unit square containing $\partial P[p_{1},p_{j}]$ and use in total $O(s\log s)$
time to find $s$. Another algorithm is described in [9].

Figure 10: Left: In some angle intervals, we have $\ell_{\varphi}\leq 1$, so
there exists a unit square containing $\mathcal{C}$ and with the same
orientation as $R_{\varphi}$. We then keep track of the unit square
$S_{\varphi}$ that covers most of $p_{s-1}p_{s}$, and this square shares a
corner with $R_{\varphi}$, so there are only four candidates. Right: In other
intervals, we have $\ell_{\varphi}>1$, so there is no unit square containing
$\mathcal{C}$ with that orientation.

  2. 2.

In order to find out how much of the edge $p_{s-1}p_{s}$ we can cover with a
unit square that also covers $\partial P[p_{1},p_{s-1}]$, we can extend the
algorithm described under point 1; see Figure 10. While running through the
whole interval $\varphi\in[0,\pi/2)$, we keep track of the angle subintervals
where $\ell_{\varphi}\leq 1$. Whenever this is the case, we monitor how much
of the edge $p_{s-1}p_{s}$ we can cover with a unit square aligned with
$R_{\varphi}$. As in the case of axis-aligned unit squares, the optimal such
unit square $S_{\varphi}$ has a corner coincident with the corresponding
corner of $R_{\varphi}$, so we just need to keep track of four unit squares.
We can therefore find the optimal square over all angles in $O(s)$ time.

In total, the point $a_{i}$ can be found in $O(s\log s)$ time.

#### Disk partitions.

We describe the two phases for finding maximal intervals for disk partitions.

  1. 1.

We perform an exponential search among the points $\\{p_{1},\ldots,p_{m}\\}$
to find the index $s$. At each step we can use an algorithm by Megiddo [43] to
test if an interval $\partial P[p_{1},p_{j}]$ is contained in a unit disk in
$O(j)$ time. The index $s$ can thus be found in $O(s\log s)$ time.

  2. 2.

The _circular hull_ of a set $M\subset\mathbb{R}^{2}$ is the intersection of
all unit disks that contain $M$. The circular hull is convex and if $M$ is
finite, the boundary of the circular hull is a finite union of circular arcs
of unit radius. Let $\mathcal{C}$ be the circular hull of $\partial
P[p_{1},p_{s-1}]$, which is the same as the circular hull of the points
$\\{p_{1},\ldots,p_{s-1}\\}$. Consider the unit disk $D$ that contains
$\partial P[p_{1},p_{s-1}]$ and a maximum prefix $p_{s-1}a_{i}$ of
$p_{s-1}p_{s}$. The following claim states that the disk $D$ falls under one
of two possible cases which are depicted in Figure 11.

Figure 11: The figure shows two cases of a unit disk covering a maximum prefix
of $\partial P[p_{1},p_{s}]$. The circular hull of $\partial P[p_{1},p_{s-1}]$
is in gray.

######  Claim.

If there exists a disk $D^{\prime}$ such that $\mathcal{C}\subset D^{\prime}$
and $\partial D^{\prime}$ contains a vertex $v$ of $\partial\mathcal{C}$ and
the segment $va_{i}$ is a diameter of $D^{\prime}$, then there is only one
such disk $D^{\prime}$ and we have $D=D^{\prime}$. Otherwise, $\partial D$
contains a unit radius arc from $\partial\mathcal{C}$.

###### Proof.

Clearly a disk $D^{\prime}$ with the described properties is the unique disk
$D$ that covers most of $p_{s-1}p_{s}$, as no other disk can cover more of
$p_{s-1}p_{s}$ while also containing $v$.

If such a disk $D^{\prime}$ does not exist, then the optimal disk $D$ must
anyway contain a vertex $v$ of $\partial\mathcal{C}$, since otherwise it could
be moved to cover more of $p_{s-1}p_{s}$. Since $va_{i}$ is not a diameter of
$D$, rotating $D$ either counterclockwise or clockwise while keeping $v$ a
fixed point on $\partial D$ will result in a disk covering more of
$p_{s-1}p_{s}$. In the former case (rolling counterclockwise) it must
therefore be the case that the unit radius arc after $v$ in counterclockwise
order is contained in $\partial D$, while in the latter, the arc before $v$ is
in $\partial D$. ∎

The claim suggests an algorithm to find the optimal disk $D$. We first compute
the circular hull $\mathcal{C}$ using an algorithm by Edelsbrunner,
Kirkpatrick and Seidel [25], which runs in time $O(s\log s)$. We let
$D^{\prime}$ be a disk whose boundary contains a unit radius arc on
$\partial\mathcal{C}$ and can then informally “roll” $D^{\prime}$ around
$\mathcal{C}$, keeping track of when $D^{\prime}$ covers most of
$p_{s-1}p_{s}$. To be precise, let $A_{1},\ldots,A_{m}$ be the unit radius
arcs on $\partial\mathcal{C}$ in counterclockwise order, and let
$v_{1},\ldots,v_{m}$ be the vertices such that $v_{i}$ is the last point in
$A_{i}$ in counterclockwise direction. We first define $D^{\prime}$ to be the
disk such that $A_{i}\subset\partial D^{\prime}$. We the rotate $D^{\prime}$
in counterclockwise direction while keeping $v_{1}$ on the boundary until we
obtain $A_{2}\subset\partial D^{\prime}$. We then rotate around $v_{2}$
instead and continue in this way until we get back to $A_{1}$. While rotating
around a vertex $v_{i}$, we check if we eventually cover a point $q\in
p_{s-1}p_{s}$ such that $v_{i}q$ is a diameter of $D^{\prime}$, in which case
we know that we found the optimal disk and can stop. Otherwise, we keep track
of the disk containing an arc $A_{i}$ that covers most of $p_{s-1}p_{s}$,
which must be the optimal disk. We can therefore find the optimal disk in
$O(s)$ time once we know the circular hull $\mathcal{C}$.

In total, the point $a_{i}$ can be found in $O(s\log s)$ time.

#### Straight diameter partitions.

We describe the two phases for finding the maximal intervals for the straight
diameter partitions.

  1. 1.

We use exponential search among the points $\\{p_{1},\ldots,p_{m}\\}$ to find
the index $s$. In order to compute the straight diameter of an interval
$\partial P[p_{1},p_{j}]$, we compute the convex hull $\mathcal{C}$ of this
interval, which can be done in $O(j)$ time, for instance using Melkmann’s
algorithm [45]. We then compute the straight diameter of $\mathcal{C}$ using
the technique of the rotating calipers [50, Theorem 4.19] in time proportional
to the complexity of $\mathcal{C}$.

  2. 2.

In order to compute the maximal prefix of the edge $p_{s-1}p_{s}$ that can be
covered by a piece of bounded diameter, we first construct the farthest point
Voronoi diagram $\mathcal{V}$ of the points $\\{p_{1},\ldots,p_{s-1}\\}$,
which can be done in $O(s\log s)$ time [50, pp. 252–253]; see Figure 12. The
diagram $\mathcal{V}$ is a subdivision of the plane into convex regions
$V_{1},\ldots,V_{s-1}$ such that $V_{j}$ consists of all points $q$ where
$p_{j}$ is the point among $\\{p_{1},\ldots,p_{s-1}\\}$ with the largest
distance to $q$. We now traverse the segment $p_{s-1}p_{s}$ and keep track of
the region $V_{j}$ in which we are. When the distance to the farthest point
$p_{j}$ reaches $1$, we stop and have found the point $a_{i}$. Since
$\mathcal{V}$ has complexity $O(s)$ and the regions are convex, this traversal
can be done in $O(s)$ time.

In total, the point $a_{i}$ can be found in $O(s\log s)$ time.

Figure 12: In this example, we have $s=13$. The farthest point Voronoi diagram
of the vertices $\\{p_{1},\ldots,p_{12}\\}$ is shown. In order to find the
maximal prefix of the interval $\partial P[p_{1},p_{13}]$ of diameter at most
$1$, we traverse the edge $p_{12}p_{13}$ and thus pass through the regions
$V_{2},V_{3},V_{5},V_{9}$ and finally get to the point $a_{i}$ where the
distance to the farthest point $p_{9}$ is $1$.

#### Geodesic diameter partitions.

We describe the two phases for finding the maximal intervals for the geodesic
diameter partitions.

  1. 1.

We use exponential search among the points $\\{p_{1},\ldots,p_{m}\\}$ to find
the index $s$. In order to test if there exists a piece of bounded geodesic
diameter covering a given interval $\partial P[p_{1},p_{j}]$, we first
construct the weakly simple polygon $Q_{j}$ bounded by the union of $\partial
P[p_{1},p_{j}]$ and the shortest path $\pi(p_{1},p_{j})$ from $p_{1}$ to
$p_{j}$. We then compute the geodesic diameter of $Q_{j}$. We can use an
algorithm by Lee and Preparata [41] to compute the shortest path
$\pi(p_{1},p_{j})$ in $O(n)$ time, using Chazelle’s algorithm [20] for
triangulation in $O(n)$ time as preprocessing. We can then use an algorithm by
Hershberger and Suri [32] to compute the geodesic diameter of $Q_{j}$ in
$O(n)$ time (note that $Q_{j}$ might have complexity $\Omega(n)$ since many
corners of $P$ which are not on the interval $\partial P[p_{1},p_{j}]$ can be
corners of $Q_{j}$). We therefore use $O(n\log s)$ time to find the index $s$.

  2. 2.

This phase is similar to the second phase for straight diameter partitions,
using a geodesic farthest point Voronoi diagram instead of a usual one: In
order to find the maximal prefix of the edge $p_{s-1}p_{s}$ that can be
covered by a piece that also covers the interval $\partial P[p_{1},p_{s-1}]$,
we compute the geodesic farthest point Voronoi diagram $\mathcal{V}$ of the
corners $p_{1},\ldots,p_{s-1}$ in $P$. This can be done in $O(n+s\log s)$ time
using an algorithm by Wang [54]. We then traverse the edge $p_{s-1}p_{s}$ and
keep track of the region of $\mathcal{V}$ in which we are, and we stop when we
reach the point $a_{i}$ where the geodesic distance to the farthest point will
exceed $1$ by any further movement. This traversal takes $O(n)$ time.

In total, the point $a_{i}$ can be found in $O(n\log n)$ time.

Figure 13: We traverse the boundary $\partial P$ with the point $q$ and stop
when the perimeter of $Q_{q}$ is $1$. The shortest path tree is shown.

#### Perimeter partitions.

When constructing perimeter partitions, we can do both phases at once, as
follows. We first compute the _shortest path tree_ $T$ from the point $p_{1}$.
The tree $T$ partitions $P$ into regions such that for all points $q$ in one
region, the shortest path $\pi(p_{1},q)$ from $p_{1}$ to $q$ passes through
the same sequence of corners of $P$. The tree $T$ can be constructed in $O(n)$
time using an algorithm by Guibas, Hershberger, Leven, Sharir, and Tarjan [30]
and using Chazelle’s algorithm [20] for triangulation in $O(n)$ time as
preprocessing. We then traverse the interval $\partial P[p_{1},p_{m}]$ with a
moving point $q$; see Figure 13. We keep track of the perimeter of the weakly
simple polygon $Q_{q}$ bounded by the union of the interval $\partial
P[p_{1},q]$ and the shortest path $\pi(p_{1},q)$. Note that this perimeter is
monotonically increasing since the length of $\partial P[p_{1},q]$ increases
with unit speed (if $q$ moves with unit speed) while the length of
$\pi(p_{1},q)$ can decrease, but not with more than unit speed. We stop when
we reach a point $q=a_{i}$ where the perimeter of $Q_{q}$ is $1$ and any
further movement of $q$ would make the perimeter exceed $1$. We use the
shortest path tree to keep track of the length of the path $\pi(p_{1},q)$; the
region containing $q$ defines the last corner $c$ of $P$ on the path
$\pi(p_{1},q)$, and the length of $\pi(p_{1},q)$ can thus be computed as the
sum of the precomputed length of the path $\pi(p_{1},c)$ and the length of the
segment $cq$. In total, the point $a_{i}$ can be found in $O(n)$ time.

###  4.2 Constructing boundary pieces from the intervals

Define the interval $I_{i}=\partial P[a_{i-1},a_{i}]$ and let $\mathcal{I}$ be
the set of the intervals $I_{i}$. For the disk, square and straight diameter
partitions, we define $C_{i}$ to be the convex hull of $I_{i}$ and
$\mathcal{C}$ to be the set of these polygons $C_{i}$. We then iterate through
the intervals $I_{i}$ and construct a boundary piece $Q_{i}$ as follows; see
Figure 14. Consider the set

$\Sigma_{i}=\left(\left(C_{i}\cap
P\right)\setminus\bigcup_{j=1}^{i-1}Q_{j}\right)\cup I_{i}.$

One of the connected components $R$ of $\Sigma_{i}$ includes the interval
$I_{i}$. We define our piece as the closure of this region, i.e.,
$Q_{i}=\overline{R}$. In other words, we create the piece $Q_{i}$ by “blowing
up” the interval $I_{i}$ towards the interior of $P$ and stop when we hit the
boundary of $P$, a previously constructed piece, or the boundary of $C_{i}$.
Clearly, since the interval $I_{i}$ is of bounded size, so is $Q_{i}$. Note
that $Q_{i}$ is a weakly simple but not necessarily a simple polygon: For
instance, $Q_{i}$ can be contained in the boundary $\partial P$, which happens
when $I_{i}$ is a concave interval on $\partial P$.

Figure 14: Constructing the piece $Q_{i}$ in a disk partition from the convex
hull $C_{i}$.

This construction has the consequence that all intervals on the boundaries of
the pieces which are neither shared with $\partial P$ nor with another piece,
are contained in the boundaries of the at most $2\,{\textsc{opt}}$ convex
polygons $\mathcal{C}$ of bounded size, by Lemma 4. As we will see in Section
5.1, this makes it possible to give a bound on the number of interior pieces
we are going to construct.

To compute the pieces, we consider the overlay of $P$ with $\mathcal{C}$. We
then use a simple flood fill algorithm from each interval $I_{i}$, marking the
faces as belonging to the piece $Q_{i}$ until we reach the boundary of $P$,
the boundary of a previously constructed piece or the boundary $\partial
C_{i}$ of the convex hull of $I_{i}$.

Figure 15: Constructing the piece $Q_{i}$ in a geodesic diameter partition.

For the geodesic diameter and the perimeter variant, we cannot use the same
approach of “blowing up” the pieces until we reach the convex hull, since this
can cause the geodesic diameter or perimeter to become arbitrarily large.
Instead, we define the boundary piece $Q_{i}$ as the polygon enclosed by the
union of the interval $I_{i}$ and the shortest path $\pi(a_{i-1},a_{i})$ in
$P$ between the endpoints of $I_{i}$; see Figure 15. We have chosen the
interval $I_{i}$ specifically such that the resulting piece $Q_{i}$ is of
bounded size. Note that using this construction, our resulting pieces
$\mathcal{Q}_{\partial}$ are indeed pairwise interior-disjoint.

We say that an interval $I_{i}$ and the corresponding boundary piece $Q_{i}$
are _trivial_ whenever $I_{i}$ does not contain a corner of $P$. In that case,
$I_{i}$ is just a line segment and $I_{i}=Q_{i}$. In the case of square, disk
and straight diameter partitions, we likewise say that the convex hull
$C_{i}\in\mathcal{C}$ is _trivial_ if the corresponding interval $I_{i}$ is
trivial.

######  Lemma 5.

The boundary pieces can be constructed within the time complexities stated in
Theorem 2.

###### Proof.

Let us first consider square, disk, and straight diameter partitions. Recall
that when constructing a new piece, we are given a point $a_{i-1}$ on
$\partial P$ and want to find the point $a_{i}$ such that the interval
$I_{i}=\partial P[a_{i-1},a_{i}]$ is the maximum interval starting at
$a_{i-1}$ that can be covered by a single piece. If $I_{i}$ is trivial, we use
$O(1)$ time to find $a_{i}$. We thus use $O({\textsc{opt}})$ time on intervals
of this type in total. Otherwise, we use $O(s)$ time for aligned square
partitions or $O(s\log s)$ time for rotated square, disk and straight diameter
partitions, where $s$ is the number of corners of $P$ that were not already
covered by other pieces. In total, we therefore use $O(n+{\textsc{opt}})$ and
$O(n\log n+{\textsc{opt}})$ time, respectively, to find the intervals.

We now consider the time used to blow up the intervals. Here we only have work
to do for the non-trivial intervals. Let
$\mathcal{C}^{\prime}\subset\mathcal{C}$ denote the set of non-trivial
polygons. We need to compute the overlay $\mathcal{L}$ of $P$ and
$\mathcal{C}^{\prime}$, and we want to show that $\mathcal{L}$ has complexity
$O(n^{2})$. Constructing the actual pieces using a flood fill algorithm then
also takes $O(n^{2})$ time.

Since each corner of $P$ is in at most two non-trivial intervals in
$\mathcal{I}$, the cardinality of $\mathcal{C}^{\prime}$ is at most $2n$.
Furthermore, each polygon $C_{i}$ has at most two corners which are not
corners of $P$, namely the endpoints of the interval $I_{i}$. We get that the
total number of corners of polygons in $\mathcal{C}^{\prime}$ is $O(n)$. We
can then use a standard overlay algorithm to construct $\mathcal{L}$ in
$O(n^{2})$ time [10, Ch. 2].

Let us now consider the time used to find the intervals $I_{i}$ for geodesic
diameter and perimeter partitions. We can again handle each trivial interval
in $O(1)$ time, so all trivial intervals take $O({\textsc{opt}})$ time in
total. Each non-trivial interval takes $O(n)$ time for perimeter partitions
and $O(n\log n)$ time for geodesic diameter partitions, so the total time for
all non-trivial intervals is $O(n^{2})$ and $O(n^{2}\log n)$, respectively. We
construct the actual pieces while finding the intervals, so the total time
used is $O(n^{2}\log n+{\textsc{opt}})$ and $O(n^{2}+{\textsc{opt}})$,
respectively. ∎

##  5 Computing the interior pieces

After constructing the boundary pieces as described in Section 4, we place a
regular square grid on top of $P$, as shown in Figure 18. We choose the size
of the grid according to the type of partition we are constructing, which is
to be specified in later sections for the particular types of partitions. We
define $\mathcal{S}$ to be the set of the squares that intersect $P$. We
create interior pieces from the regions in the squares that are not contained
in boundary pieces.

Figure 16: Three consecutive boundary pieces $Q_{i-1},Q_{i},Q_{i+1}$ of a disk
partition.

In order to bound the number of interior pieces, we need to introduce the
notion of an _interior boundary interval_ , as follows. Let
$\mathcal{Q}_{\partial}=\\{Q_{1},\ldots,Q_{k}\\}$ be the boundary pieces in
the counterclockwise order in which they were constructed by the greedy
algorithm in Section 4. For each $i\in\\{1,\ldots,k\\}$, the shared boundary
of $Q_{i}$ and $Q_{i+1}$ is an interval $\partial Q_{i}[a_{i},b_{i}]=\partial
Q_{i+1}[b_{i},a_{i}]$, where indices are taken modulo $k$; see Figure 16.
Here, $a_{i}$ is a point on $\partial P$, while $b_{i}$ need not be. Each
piece $Q_{i}$ was chosen in a greedy way so as to maximize the interval
$\partial Q_{i}[a_{i-1},a_{i}]\subset\partial P$ that $\partial Q_{i}$ covers
of $\partial P$. In other words, the exterior of $P$ is to the right of this
interval (when traversing $\partial Q_{i}$ in counterclockwise direction),
while the interval $\partial Q_{i}(b_{i},b_{i-1})$ has the interior of $P$ to
the right (except where it occasionally meets the interval $\partial
P(a_{i},a_{i-1})$ that constitute the rest of $\partial P$ that the piece
$Q_{i}$ could not cover). We define an _interior boundary interval_ of $Q_{i}$
to be a maximal interval in $\partial Q_{i}[b_{i},b_{i-1}]$ which is interior-
disjoint from all other boundary pieces.

######  Lemma 6.

There are at most $6\,{\textsc{opt}}-9$ interior boundary intervals.

Figure 17: The graph $G$ from the proof of Lemma 6. The polygons are the
boundary pieces. There are four interior boundary intervals on the boundary of
the piece $Q$, shown in fat. The figure is for illustration only; the pieces
produced by our algorithms would not look like these.

###### Proof.

Consider the undirected graph $G$ with vertices $\mathcal{Q}_{\partial}$ where
we add an edge between two pieces $Q_{i}$ and $Q_{j}$ if $\partial
Q_{i}\cap\partial Q_{j}\neq\emptyset$; see Figure 17. Note that $G$ is an
outerplanar graph where the outer face is bounded by a Hamiltonian cycle $C$
consisting of the edges $Q_{i}Q_{i+1}$ corresponding to the boundary pieces in
cyclic order. If there were no other edges in $G$, there would be exactly
$|\mathcal{Q}_{\partial}|$ interior boundary intervals, namely the intervals
$\partial Q_{i}[b_{i},b_{i-1}]$. Each extra edge of $G$ between pieces $Q_{i}$
and $Q_{j}$ can cause the creation of two extra interior boundary intervals,
one on each of $\partial Q_{i}$ and $\partial Q_{j}$. Note that $G$ has at
most $|\mathcal{Q}_{\partial}|-3$ of these extra edges, since that number of
edges will cause the cycle $C$ to be triangulated. Hence, there are at most
$|\mathcal{Q}_{\partial}|+2(|\mathcal{Q}_{\partial}|-3)=3|\mathcal{Q}_{\partial}|-6$
interior boundary intervals. Recall that $|\mathcal{Q}_{\partial}|\leq
2\,{\textsc{opt}}-1$ due to Lemma 4. We therefore get that there are at most
$6\,{\textsc{opt}}-9$ interior boundary intervals. ∎

###  5.1 Disk, square and straight diameter partitions

We choose the edge length of the grid squares $\mathcal{S}$ to be maximum so
that each square satisfies the size constraint, i.e., the edge length of each
square should be $\sqrt{2}$, $1/\sqrt{2}$ and $1$ for disk, straight diameter
and square partitions, respectively.

Consider a square $S\in\mathcal{S}$. We define a _field_ to be the closure of
a connected component of $(S\cap P)\setminus\bigcup\mathcal{Q}_{\partial}$. We
use each field as an interior piece. That is, if no boundary piece overlaps
the square $S$, then $S$ itself is used as a piece. Otherwise, $S$ may be
broken into several interior pieces by the intersecting boundary pieces. For
disk, square and straight diameter partitions, we can now bound the number of
interior pieces as stated by the following lemma.

######  Lemma 7.

The number of interior pieces are bounded as follows.

  * •

Aligned square partitions: $11\,{\textsc{opt}}$.

  * •

Rotated square partitions: $19\,{\textsc{opt}}$.

  * •

Disk and straight diameter partitions: $(18+\pi/2)\,{\textsc{opt}}$.

###### Proof.

We say that an interior piece $Q$ is _complete_ if it is a full square in
$\mathcal{S}$, and otherwise it is _incomplete_ ; see Figure 18. We first
bound the number of complete pieces as follows. For disk partitions, the
complete pieces have area $2$, so we get that the number of complete pieces is
at most $\operatorname{area}P/2$. For straight diameter partitions, each
complete piece has area $1/2$, so there are at most $2\operatorname{area}P$
complete pieces. For square partitions, each complete piece has area $1$, so
there are at most $\operatorname{area}P$ complete pieces.

Figure 18: The figure shows the three types of interior pieces. The blue
polygons are the boundary pieces. The square $Q_{1}$ is a complete interior
piece, $Q_{2}$ and $Q_{3}$ are edge pieces, and $Q_{4}$ is a chip piece. We
use the intersection point $a$ to account for $Q_{2}$ while $a^{\prime}$
accounts for $Q_{3}$ The figure is for illustration only; the pieces produced
by our algorithms would not look like these (see Figure 4 for an authentic
example).

In disk, straight diameter and square partitions, we have
${\textsc{opt}}\geq\operatorname{area}P/\pi$, ${\textsc{opt}}\geq
4\operatorname{area}P/\pi$ and ${\textsc{opt}}\geq\operatorname{area}P$,
respectively. We therefore get that the number of complete pieces is at most
$\pi\,{\textsc{opt}}/2$ for disk and straight diameter partitions and at most
opt for both kinds of square partitions.

We now turn our attention to the incomplete pieces. We distinguish between two
types of incomplete pieces, as follows. If an interval of the boundary of a
square $S\in\mathcal{S}$ appears on the boundary of an incomplete piece $Q$,
we say that $Q$ is an _edge piece_ , and otherwise, it is a _chip piece_. For
the ease of presentation, we make the following general position assumptions:
(i) no polygon in $\mathcal{C}$ has a left-, right-, top- or bottom-most point
on the boundary of a square in $\mathcal{S}$, and (ii) no square in
$\mathcal{S}$ has a corner on the boundary of a polygon in $\mathcal{C}$. This
can be obtained either by symbolic perturbation [26] or by choosing the grid
defining the squares $\mathcal{S}$ carefully. The lemma is also true without
these assumptions, but with the assumptions, we can skip some tedious special
cases.

Consider an edge piece $Q$ in a square $S$ and let $I$ be a maximal interval
in $\partial Q\cap\partial S$. Let $a$ be the end of $I$ in counterclockwise
order around $\partial Q$. Then $a$ is an intersection point in $\partial
C\cap\partial S$ for a convex polygon $C\in\mathcal{C}$. In this way, we can
account for each edge piece by such an endpoint. Note that although the point
$a$ is also be on the boundary of an edge piece $Q^{\prime}$ in a neighbouring
square $S^{\prime}$ of $S$, we will not use $a$ to account for $Q^{\prime}$,
since $a$ will be the beginning and not the end of a maximal interval in
$\partial Q^{\prime}\cap\partial S^{\prime}$.

Let us first consider rotated square, disk and straight diameter partitions.
Here, a polygon $C\in\mathcal{C}$ can intersect at most two vertical lines and
at most two horizontal lines in the grid that defines the squares
$\mathcal{S}$, so there are at most eight intersection points; see Figure 19.
Using that $|\mathcal{Q}_{\partial}|<2\,{\textsc{opt}}$ by Lemma 4, we get
that there are less than $16\,{\textsc{opt}}$ intersection points between the
boundaries of polygons in $\mathcal{C}$ and the boundaries of the squares
$\mathcal{S}$. We conclude that there are less than $16\,{\textsc{opt}}$ edge
pieces in rotated square, disk and straight diameter partitions.

Figure 19: The figure shows the grid we use for disk partitions. The convex
polygon $C$ can be contained in a unit disk, and its boundary has eight
intersection points with the lines defining the grid, which is the maximum.

In aligned square partitions, each square $S\in\mathcal{S}$ is an axis-aligned
unit square, and each polygon $C\in\mathcal{C}$ is contained in an axis-
aligned unit square. Therefore, $C$ intersects at most one vertical and one
horizontal line of the square grid, so there are at most four intersection
points. We therefore get less than $8\,{\textsc{opt}}$ edge pieces in this
case.

The boundary of each chip piece $Q$ is a union of three or more interior
boundary intervals, and each of these intervals is a concave interval on
$\partial Q$. By Lemma 6 we then get that there are less than
$6\,{\textsc{opt}}/3=2\,{\textsc{opt}}$ chip pieces for all types of
partitions.

In total, we get less than $(18+\pi/2)\,{\textsc{opt}}$ interior pieces for
disk and straight diameter partitions, less than $11\,{\textsc{opt}}$ interior
pieces for aligned square partitions, and less than $19\,{\textsc{opt}}$
interior pieces for rotated square partitions. ∎

We can now conclude our work on these types of partitions by giving the
following proof.

###### Proof of Theorem 2 for square, disk and straight diameter partitions..

The approximation ratios follow from Lemmas 4 and 7, so here we focus on
describing algorithms with the claimed running times for the estimation and
construction problems. For the estimation problem, we first compute the
cardinality $x_{\partial}$ of our boundary partition $\mathcal{Q}_{\partial}$
using the stated running times for estimation, where we “jump over” the
trivial intervals to avoid an additive term of opt in the time complexity.
That is, suppose that our starting point $a_{i-1}$ is on an edge $e$ of $P$
and let $p$ be the end of $e$ so that the segment $a_{i-1}p\subset e$ remains
to be covered by boundary pieces. By first computing the length of $a_{i-1}p$,
we can in $O(1)$ time compute how many trivial intervals our algorithm will
construct on $e$ until we get to a non-trivial one, which is the first
containing $p$. For aligned square partitions, we know after $x_{\partial}$
has been computed that our constructed partition of all of $P$ would have at
most $13x_{\partial}/2$ pieces, and we can return that number. For rotated
square partitions, we similarly return $21x_{\partial}/2$, and for disk and
straight diameter partitions, $(10+\pi/4)x_{\partial}$. The running times are
explained in the proof of Lemma 5.

For the construction of the interior pieces, we compute the overlay
$\mathcal{L}$ of all interior boundary intervals and the squares
$\mathcal{S}$. Note that there are $O({\textsc{opt}})$ squares since each
piece in an optimal partition can intersect at most $O(1)$ squares in
$\mathcal{S}$. The total complexity of the interior boundary intervals (not
counting intersections with the squares $\mathcal{S}$) is
$O(n+{\textsc{opt}})$, since each corner is a corner of $P$ or an endpoint of
an interval, and there are $O({\textsc{opt}})$ intervals by Lemma 6. The
interior boundary intervals of a single convex polygon $C_{i}$ have $O(1)$
intersection points with the boundaries of the squares $\mathcal{S}$.
Therefore, the complexity of $\mathcal{L}$ is $O(n+{\textsc{opt}})$.

Using a standard overlay algorithm [10, Ch. 2], we would get a running time of
$O((n+{\textsc{opt}})\log(n+{\textsc{opt}}))$, but in this special case where
$\mathcal{S}$ are just squares from a regular grid, we can use an improved
version with running time $O((n+{\textsc{opt}})\log n)$: The idea is that we
do not need to handle the edges of $\mathcal{S}$ in the same way as the edges
of the interior boundary intervals. We use a horizontal sweepline $\ell$
starting above $P$ and going down. We use _ibi edge_ as an abbreviation of
“interior boundary interval edge.” There are four types of events, defined by
the $y$-coordinates of the following objects: (i) the top endpoint of an ibi
edge, (ii) the bottom endpoint of an ibi edge, (iii) a horizontal grid line
$h$, and (iv) the intersection point between an ibi edge and a vertical grid
line. We store the ibi edges currently intersected by $\ell$ in a status data
structure $\mathcal{T}$, which is a balanced binary search tree sorted by the
$x$-coordinates of the intersections between the sweepline $\ell$ and the
edges. For each vertical grid line $k$, we also store a pointer $a_{k}$ to the
vertex of $\mathcal{L}$ on $k$ that is immediately above the sweepline $\ell$
(this may be a gridpoint or an intersection point between an ibi edge and
$k$). For each ibi edge $e$ in $\mathcal{T}$, we likewise store a pointer
$b_{e}$ to the vertex of $\mathcal{L}$ on $e$ that is immediately above
$\ell$, which may be the top endpoint of $e$ or an intersection between $e$
and a grid line. The events are handled as follows.

  * (i)

We add the top endpoint $q$ of the new edge $e$ to $\mathcal{L}$ and set
$b_{e}$ to point on $q$. We add $e$ to $\mathcal{T}$. We also check if $e$
intersects one of the neighbouring vertical grid lines, and if so, we add the
corresponding event of type (iv) to the event queue.

  * (ii)

We add the bottom endpoint $q$ of the edge $e$ to $\mathcal{L}$ and construct
an edge from $q$ to the preceding vertex $b_{e}$. We then remove $e$ from
$\mathcal{T}$.

  * (iii)

We run through the entire tree $\mathcal{T}$ in order of $x$-coordinates and
construct the bottom part of the row of squares in $\mathcal{S}$ bounded from
below by the horizontal line $h$. This involves finding the intersections
between the ibi edges in $\mathcal{T}$ and $h$ and constructing the segments
from these intersection points to the preceding vertices on the edges above
$\ell$. We update all the pointers $a_{k}$ to point to the new grid points on
$h$ and we update the pointers $b_{e}$ to point at the intersection points
between the ibi edges and $h$.

  * (iv)

When we reach the intersection point $q$ of an ibi edge $e$ with a vertical
grid line $k$, we add $q$ to $\mathcal{L}$ and construct the edges from $q$ to
the preceding vertices $a_{k}$ and $b_{e}$. We update $a_{k}$ and $b_{e}$ to
point to $q$ and also check if $e$ intersects a neighbour of $k$ below $\ell$,
in which case we add the corresponding event of type (iv) to the event queue.

Events of types (i), (ii) and (iv) take $O(\log n)$ time to handle, and since
there are $O(n+{\textsc{opt}})$ of them, they take $O((n+{\textsc{opt}})\log
n)$ time in total. In events of type (iii), we use constant time for each edge
we construct of the overlay $\mathcal{L}$, so since $\mathcal{L}$ has
complexity $O(n+{\textsc{opt}})$, we use that much time on events of type
(iii) in total. After computing $\mathcal{L}$, we just need to detect which
faces are fields. This can be done by a flood fill algorithm, starting from
each interior boundary interval $I\subset\partial C_{i}$ and traversing the
faces towards the exterior of the polygon $C_{i}$.∎

###  5.2 Geodesic diameter and perimeter partitions

For geodesic diameter and perimeter partitions, we again use a square grid
$\mathcal{S}$, where the edge length of each square is a constant $\gamma>0$
to be chosen later. Recall that a _field_ in a square $S\in\mathcal{S}$ is the
closure of a connected component of $(S\cap
P)\setminus\bigcup\mathcal{Q}_{\partial}$, and that $\mathcal{I}$ is the
intervals on $\partial P$ that are used to define the boundary pieces
$\mathcal{Q}_{\partial}$.

We say that a field $F$ is _trivial_ if no non-trivial interval from
$\mathcal{I}$ appears on the boundary of $F$; see Figure 20. Trivial intervals
can appear on the boundary of a trivial field $F$, but these intervals must be
contained in edges of $P$ that pass all the way through the square $S$
containing $F$. In particular, a trivial field is a convex polygon contained
in $S$. Hence, a trivial field satisfies the size constraint, and we will
therefore use it directly as a piece.

Figure 20: A polygon $P$ with a perimeter partition. The blue pieces are
boundary pieces. The dots mark the endpoints of the intervals $\mathcal{I}$
covered by the boundary pieces. The the green regions are the non-trivial
fields and yellow regions are the trivial fields. The figure is for
illustration only, and our algorithm would use a grid of much smaller squares.
Color codes: 1 blue, 2 green, 3 yellow.

Consider a non-trivial field $F$ in a square $S$; see Figure 21 (left). We
need to be careful when defining the interior pieces for geodesic diameter and
perimeter partitions: We cannot directly use $F$ as a piece (as we did in
Section 5.1), since $F$ can have arbitrarily large geodesic diameter or
perimeter. Instead, we split $F$ into _subfields_ , as described in the
following.

We first split the interior boundary intervals into subintervals, which we
call _fragments_. Each fragment can have length at most $\delta$ for some
constant $\delta>0$ depending on the type of partition. We split each interior
boundary interval into a minimum number of fragments by traversing the
interval and repeatedly splitting whenever we have traversed a prefix of
length $\delta$.

Let us observe that the interior boundary intervals, and hence also the
fragments, are convex intervals on the boundaries of the boundary pieces (just
as in disk, square and straight diameter partitions): Recall that each
boundary piece $Q_{i}$ is bounded by a maximal interval $\partial
P[a_{i-1},a_{i}]$ and the shortest path $\pi=\pi_{P}(a_{i-1},a_{i})$ in $P$
between the endpoints $a_{i-1}$ and $a_{i}$. Consider an interior corner $v$
of $\pi$ which is concave with respect to $Q_{i}$. Such a corner $v$ is on the
shared boundaries between $Q_{i}$ and another boundary piece $Q_{j}$, so $v$
is not in the interior of an interior boundary interval of $Q_{i}$, and it
follows that all interior boundary intervals are convex intervals. Let us
remark that despite this fact, the situation is still more complicated than
for disk, square and straight diameter partitions, as a single interior
boundary interval for geodesic diameter and perimeter partitions can be a
spiral that makes an arbitrary number of revolutions and thus, for instance,
enters and leaves the same square in $\mathcal{S}$ an arbitrary number of
times.

Figure 21: The figure shows how we split a field $F$ in a square $S$ into
subfields and assign them to the fragments. The boundary pieces are blue, the
fat blue curves are the fragments, and the blue points are the endpoints of
the fragments (restricted to $S$). The boundary of $P$ is sketched in black
(not to scale; it should be much more complicated to result in this many
boundary pieces in a single square). To the right is shown how the field $F$
is split into subfields by shortest paths to the point $p$. The subfields
$G_{1}$ and $G_{2}$ are edge subfields, and $G_{3}$ is a fragment subfield.
Here, $G_{1}$ is assigned to the fragment $f_{1}$ and $G_{2}$ and $G_{3}$ are
assigned to $f_{2}$.

To define the subfields in a field $F$, we choose an arbitrary fixed point $p$
in $F$ (for instance, a corner of $F$). For each point $c$ of $\partial F$
which is either a corner of $\partial S$ or a shared endpoint of two fragments
bounding $F$, we cut $F$ along the geodesic shortest path $\pi_{F}(c,p)$ in
$F$ from $c$ to $p$. These paths partition $F$ into _subfields_. There exist
two types of subfields: A subfield $G$ is an _edge subfield_ if a segment $s$
on an edge of $S$ appears on the boundary of $G$. Otherwise, $G$ is a
_fragment subfield_ , and here an interval $f^{\prime}$ on a fragment $f$
bounds $G$ (the full fragment $f$ may also intersect other squares in
$\mathcal{S}$, which is why only an interval on $f$ appears on the boundary of
$G$ in general).

Consider an edge subfield $G$ and let $a$ and $b$ be the endpoints of the
segment $s\subset\partial S$; see Figure 22 (left). Let $\pi_{a}=\pi_{F}(a,p)$
and $\pi_{b}=\pi_{F}(b,p)$ be the shortest paths in $F$ from $a$ and $b$ to
$p$, respectively, and let $q$ be the first common point of $\pi_{a}$ and
$\pi_{b}$. Then the boundary of $G$ consists of $s$ and the prefixes of
$\pi_{a}$ and $\pi_{b}$ until the common point $q$. An analogous description
holds for a fragment subfield $G$, where we define $a$ and $b$ as the
endpoints of the interval $f^{\prime}$ of a fragment bounding $G$.

We assign a fragment subfield $G$ to the fragment $f$ bounding $G$; see Figure
22 (right). For an edge subfield $G$ bounded by a segment $s\subset\partial
S$, we consider the next fragment $f$ following $s$ on $\partial F$ in
counterclockwise order and then assign $G$ to $f$. Note that since a fragment
can intersect more than one square, a piece is not necessarily contained in a
single square, but it will be contained in the union of at most four squares
since a fragment intersects at most four squares.

Using appropriate values of $\gamma$ and $\delta$, we can now bound the number
of pieces as stated in Lemmas 8 and 9. A key insight in the proofs is that
since the boundary of each subfield consists of three concave intervals in a
square of size $\gamma\times\gamma$, the geodesic diameter and perimeter of
each subfield is $O(\gamma)$.

Figure 22: Left: An edge subfield bounded by a segment $s\subset\partial S$
and the prefixes of the shortest paths $\pi_{a}$ and $\pi_{b}$ until their
first common point $q$. Right: Three subfields assigned to one fragment $f$,
so the union $G_{1}\cup G_{2}\cup G_{3}$ will constitute one piece. Here,
$G_{1}$ and $G_{3}$ are fragment subfields and $G_{2}$ is an edge subfield.

######  Lemma 8.

Choosing $\gamma=0.127$ and $\delta=0.133$, the method described above results
in less than $70\,{\textsc{opt}}$ interior boundary pieces of geodesic
diameter at most $1$.

###### Proof.

We first consider the complete interior pieces, i.e., the squares from
$\mathcal{S}$ that are also used as pieces. Our algorithm creates at most
$\operatorname{area}P/\gamma^{2}$ such pieces. A disk of diameter $1$ has the
largest area of all shapes with geodesic diameter at most $1$, so we have
${\textsc{opt}}\geq 4\operatorname{area}P/\pi$, and the number of complete
pieces is thus at most
$\operatorname{area}P/\gamma^{2}\leq\frac{\pi\,{\textsc{opt}}}{4\gamma^{2}}$.

We make the analysis as if we were splitting all remaining fields into
subfields, although the algorithm will actually only split the non-trivial
fields; this just gives an upper bound on the resulting number of pieces. Note
that it holds for both edge and fragment subfields that a subfield $G$ is
bounded by three concave intervals (for edge subfields, one of these concave
intervals is just a segment on the boundary of $S$). Hence, every subfield $G$
is contained in a triangle $T$, whose corners $a,b,c$ are the endpoints of the
three concave intervals. The concave interval from $a$ to $b$ has length less
than $\|ac\|+\|cb\|$, and the length of the other two intervals can be bounded
in a similar way. We obtain that the geodesic diameter of $G$ is less than the
perimeter of $T$. It is easy to verify that a triangle in the square $S$ with
maximum perimeter is spanned by three corners of $S$, so the perimeter of $T$
is at most $(2+\sqrt{2})\gamma$, which is also a bound on the geodesic
diameter of each subfield $G$.

Consider now two points $u$ and $v$ in the piece assigned to a fragment $f$.
Then $u$ and $v$ are contained in subfields $G_{u}$ and $G_{v}$, respectively,
and we get a path from $u$ to $v$ by first walking in $G_{u}$ to $f$ and then
along $f$ to $G_{v}$, from which we go to $v$. Since the geodesic diameter of
each subfield is at most $(2+\sqrt{2})\gamma$ and $f$ has length $\delta$,
this path has length at most $2(2+\sqrt{2})\gamma+\delta$. To bound the
geodesic diameter, we therefore require that $2(2+\sqrt{2})\gamma+\delta\leq
1$. Recall that the fragments are contained in $2\,{\textsc{opt}}$ shortest
paths of length at most $1$ by Lemma 4, so we split the interior boundary
itervals at most $2\,{\textsc{opt}}/\delta$ times in order to create the
fragments. We start with at most $6\,{\textsc{opt}}$ interior boundary
partitions by Lemma 6. We conclude that we create at most
$6\,{\textsc{opt}}+2\,{\textsc{opt}}/\delta$ fragments.

In total, we create at most
$(\frac{\pi}{4\gamma^{2}}+6+2/\delta)\,{\textsc{opt}}$ interior pieces. Under
the restriction that $2(2+\sqrt{2})\gamma+\delta\leq 1$, this is minimized for
$\gamma\approx 0.127$ and $\delta=1-2(2+\sqrt{2})\gamma\approx 0.133$, in
which case the number of piece is bounded by a bit less than
$70\,{\textsc{opt}}$. ∎

######  Lemma 9.

Choosing $\gamma=0.00490$ and $\delta=0.00243$, the described method results
in less than $3726\,{\textsc{opt}}$ interior boundary pieces of perimeter at
most $1$.

Figure 23: The figure shows how a fragment $f$ can partition four squares into
regions $S_{1},\ldots,S_{10}$ when constructing a perimeter partition. The
figure is not to scale ($f$ is too long here).

###### Proof.

Note that a disk of radius $\frac{1}{2\pi}$ has the largest area of any shape
of perimeter $1$. The complete interior pieces in our partition have area
$\gamma^{2}$, so there are at most $\frac{{\textsc{opt}}}{4\gamma^{2}\pi}$
complete pieces.

We now turn our attention to the number of pieces we create from incomplete
fields. As in the proof of Lemma 8, assume that we split all fields which are
not full squares into subfields, which gives an upper bound on the number of
pieces. We require that $\delta\leq\gamma$ so that a fragment can intersect at
most four different squares in $\mathcal{S}$. Consider a fragment $f$ and let
$\mathcal{S}^{\prime}\subset\mathcal{S}$ be the set of up to four squares
intersected by $f$. The fragment $f$ partitions the squares
$\mathcal{S}^{\prime}$ into regions $S_{1},\ldots,S_{m}$; see Figure 23. Each
region $S_{i}$ is bounded by some intervals on $f$ and some intervals on the
boundary of a square $S\in\mathcal{S}^{\prime}$. The regions $S_{i}$ are, in
general, not contained in $P$, but we can use them to bound the perimeter of
the subfield that constitute the pieces of our partition. Note that for a
square $S\in\mathcal{S}$, each interval $f^{\prime}$ in $f\cap S$ appears
twice on the boundaries of regions $S_{i}$ in $S$: either there are different
regions on the two sides of $f^{\prime}$, or the two sides of $f^{\prime}$
contributes to the perimeter of the same region. We therefore get

$\sum_{i=1}^{m}\operatorname{perimeter}S_{i}\leq 2\delta+16\gamma.$

Each subfield from $S\in\mathcal{S}^{\prime}$ that we assign to $f$ is
contained in one of these regions $S_{i}$. As in the proof of Lemma 8, we note
that a subfield $G$ in $S_{i}$ is bounded by three concave intervals and thus
contained in a triangle $T$. It follows that $\operatorname{perimeter}G\leq
2\operatorname{perimeter}T\leq 2\operatorname{perimeter}S_{i}$, where the
latter inequality follows as the corners of $T$ are in $S_{i}$. Note that at
most six subfields in $S_{i}$ are assigned to $f$: there can be one fragment
subfield and at most five edge subfields (for one edge of $S$, there can be
two edge subfields and for the others at most one). The total perimeter of
subfields in $S_{i}$ assigned to $f$ is therefore at most
$12\operatorname{perimeter}S_{i}$. We then get that the total perimeter of
subfields that are assigned to $f$, and thus the perimeter of the resulting
interior piece, is at most

$\sum_{i=1}^{m}12\operatorname{perimeter}S_{i}\leq
12(2\delta+16\gamma)=24\delta+192\gamma.$

To get pieces of bounded perimeter, we hence require that
$24\delta+192\gamma\leq 1$. Consider an interval $I_{i}=\partial
P[a_{i-1},a_{i}]$ and the shortest path $\pi=\pi(a_{i-1},a_{i})$. We note that
since $Q_{i}$ has perimeter at most $1$, the length of $\pi$ is at most $1/2$.
Similarly as in the proof of Lemma 8, we can then bound the number of
fragments by $(6+1/\delta)\,{\textsc{opt}}$, and the total number of interior
pieces (complete and incomplete) is at most
$(\frac{1}{4\gamma^{2}\pi}+6+1/\delta)\,{\textsc{opt}}$. We obtain the minimum
under the constraint that $24\delta+192\gamma\leq 1$ when $\gamma\approx
0.00490$ and $\delta=1/24-8\gamma\approx 0.00243$, in which case we get less
than $3726\,{\textsc{opt}}$ interior pieces. ∎

We can now conclude our work on geodesic diameter and perimeter partitions by
giving the following proof.

###### Proof of Theorem 2 for geodesic diameter and perimeter partitions..

The approximation ratios follow from Lemmas 4, 8 and 9 and the analysis of the
running times of solving the estimation problems is analogous to that for the
other types of partitions described in Section 5.1, so here we focus on the
time required to solve the construction problems.

As in the proof for the other types of partitions, we construct the interior
pieces by first computing the overlay $\mathcal{L}$ of the squares
$\mathcal{S}$ and the interior boundary intervals, and we can again conclude
that $\mathcal{L}$ has complexity $O(n+{\textsc{opt}})$ and can be constructed
in $O((n+{\textsc{opt}})\log n)$ time. We can then identify the trivial and
non-trivial fields in time $O(n+{\textsc{opt}})$ by traversing the overlay
$\mathcal{L}$. The trivial fields are used as interior pieces, and it remains
to partition the non-trivial fields into subfields.

To get a bound on the time needed to split the non-trivial fields, we show
that the total complexity of all non-trivial fields is $O(n)$. We define an
interior boundary interval $I\subset\partial Q$ to be _non-trivial_ if $Q$ is
a non-trivial piece. Note that the corners of the non-trivial interior
boundary intervals from a boundary piece $Q_{i}\in\mathcal{Q}_{\partial}$ are
corners of $P$ except possibly the endpoints $a_{i-1}$ and $a_{i}$ of the
interval $I_{i}$ defining $Q_{i}$. Each corner $c$ of $P$ appears on at most
four interior boundary intervals, namely one starting and one ending at $c$
and one starting and one ending on another piece on whose boundary $c$ forms a
concave corner. We therefore get that the total complexity of all non-trivial
interior boundary intervals is $O(n)$.

Figure 24: A field $F$ with segments of the four types 1–4.

Consider a non-trivial field $F$ in a square $S$ and an edge $s\subset\partial
F$ of $F$. We claim that $s$ must have one of the following types; see Figure
24.

  1. 1.

$s$ overlaps with an edge of a non-trivial interior boundary interval.

  2. 2.

$s\subset\partial S$.

  3. 3.

$s$ is contained in a trivial interval in $\mathcal{I}$ and is incident to an
edge of type 1.

  4. 4.

$s$ is contained in a trivial interval in $\mathcal{I}$ and is incident to two
edges of type 2.

To see that the list is exhaustive, note that if an edge $s$ of $F$ is
contained in a trivial interval, it cannot be incident to another such edge,
since their common endpoint would then have to be a corner of $P$, so the
intervals would not be trivial. We now observe that there can be at most
$O(1)$ edges of types 2–4 for each edge of type 1: Consider a maximal interval
$s_{1}\cup\ldots\cup s_{m}$ of edges of $F$ of types 2–4. Then $s_{1}$ and
$s_{m}$ have type 3 while the rest have types 2 and 4. Each edge of type 4
cuts off a corner from $S$, so there can be at most four of them. We cannot
have more than five edges of type 2 in a row, because otherwise we would have
traversed $\partial S$ completely. Hence, we have $m=O(1)$, and we can use the
edge of type 1 after $s_{m}$ to account for the edges $s_{1},\ldots,s_{m}$.

Each edge of a non-trivial interior boundary interval can intersect at most
$O(1)$ squares in $\mathcal{S}$, since the squares have constant edge length
$\gamma>0$, so each such edge accounts for $O(1)$ edges of non-trivial fields
in total. Since the non-trivial interior boundary intervals have total
complexity $O(n)$, we conclude that the total number of edges of type 1 is
$O(n)$. Then there are $O(n)$ edges all in all, so the complexity of the non-
trivial fields is also $O(n)$.

Since the total length if the non-trivial boundary intervals is $O(n)$ and we
split them into fragments of length $\delta>0$, there are likewise $O(n)$
fragment endpoints on the boundaries of the non-trivial fields. In a non-
trivial field $F$ with $n^{\prime}$ corners, we can compute the shortest path
tree from the special point $p$ in $O(n^{\prime})$ time [30] and then
construct the subfields in $F$ in the same time. We can therefore construct
all subfields in $O(n)$ time. ∎

### Acknowledgements

We thank Sándor Fekete, André Nusser and Hanwen Zhang for useful discussions
on topics related to this paper.

## References

  * [1] Mikkel Abrahamsen  “Covering Polygons is Even Harder”  In _62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2021)_ , 2021, pp. 375–386  DOI: 10.1109/FOCS52979.2021.00045
  * [2] Mikkel Abrahamsen, Anna Adamaszek and Tillmann Miltzow  “The Art Gallery Problem is $\exists$$\mathbb{R}$-complete”  In _J. ACM_ 69.1, 2022, pp. 4:1–4:70  DOI: 10.1145/3486220
  * [3] David Adjiashvili and David Peleg  “Equal-area locus-based convex polygon decomposition”  In _Theor. Comput. Sci._ 411.14-15, 2010, pp. 1648–1667  DOI: 10.1016/j.tcs.2010.01.012
  * [4] Hugo A. Akitaya, Greg Aloupis, Jeff Erickson and Csaba D. Tóth  “Recognizing Weakly Simple Polygons”  In _Discret. Comput. Geom._ 58.4, 2017, pp. 785–821  DOI: 10.1007/s00454-017-9918-3
  * [5] Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk and Csaba D. Tóth  “Cutting Polygons into Small Pieces with Chords: Laser-Based Localization”  In _28th Annual European Symposium on Algorithms (ESA 2020)_ , 2020, pp. 7:1–7:23  DOI: 10.4230/LIPIcs.ESA.2020.7
  * [6] Bogdan Armaselu and Ovidiu Daescu  “Algorithms for fair partitioning of convex polygons”  In _Theor. Comput. Sci._ 607, 2015, pp. 351–362  DOI: 10.1016/j.tcs.2015.08.003
  * [7] Hannah Bast and Susan Hert  “The Area Partitioning Problem”  In _12th Canadian Conference on Computational Geometry (CCCG 2000)_ , 2000  URL: http://www.cccg.ca/proceedings/2000/6.ps.gz
  * [8] Aaron T. Becker, Sándor P. Fekete, Alexander Kröller, SeoungKyou Lee, James McLurkin and Christiane Schmidt  “Triangulating unknown environments using robot swarms”  In _Symposium on Computational Geometry (SoCG 2013)_ , 2013, pp. 345–346  DOI: 10.1145/2462356.2462360
  * [9] Sergey Bereg, Binay Bhattacharya, Sandip Das, Tsunehiko Kameda, Priya Ranjan Sinha Mahapatra and Zhao Song  “Optimizing squares covering a set of points”  In _Theor. Comput. Sci._ 729, 2018, pp. 68–83  DOI: 10.1016/j.tcs.2015.11.029
  * [10] Mark Berg, Otfried Cheong, Marc J. Kreveld and Mark H. Overmars  “Computational geometry: algorithms and applications, 3rd Edition”  Springer, 2008  URL: https://www.worldcat.org/oclc/227584184
  * [11] A. Bezdek and K. Bezdek  “A Solution of Conway’s Fried Potato Problem”  In _Bulletin of the London Mathematical Society_ 27.5, 1995, pp. 492–496  DOI: 10.1112/blms/27.5.492
  * [12] A. Bezdek and K. Bezdek  “Conway’s fried potato problem revisited”  In _Arch. Math._ 66.6 Birkhäuser-Verlag, 1996, pp. 522–528  DOI: 10.1007/BF01268872
  * [13] Pavle V.M. Blagojević and Günter M. Ziegler  “Convex equipartitions via equivariant obstruction theory”  In _Isr. J. Math._ 200 Springer, 2014, pp. 49–77  DOI: 10.1007/s11856-014-1006-6
  * [14] Karol Borsuk  “Drei Sätze über die $n$-dimensionale euklidische Sphäre”  In _Fundamenta Mathematicae_ 20.1, 1933, pp. 177–190  DOI: 10.4064/fm-20-1-177-190
  * [15] Maike Buchin and Leonie Selbach  “Decomposing Polygons into Fat Components”  In _33rd Canadian Conference on Computational Geometry (CCCG 2021)_ , 2021, pp. 175–184
  * [16] Antonio Cañete, Isabel Fernández and Alberto Márquez  “Conway’s fried potato problem: a (quadratic) algorithm leading to an optimal division for convex polygons”  In _Discrete Mathematics Days (DMD 2022)_ , 2022, pp. 71–76
  * [17] John Gunnar Carlsson, Benjamin Armbruster and Yinyu Ye  “Finding equitable convex partitions of points in a polygon efficiently”  In _ACM Trans. Algorithms_ 6.4, 2010, pp. 72:1–72:19  DOI: 10.1145/1824777.1824792
  * [18] Hsien-Chih Chang, Jeff Erickson and Chao Xu  “Detecting Weakly Simple Polygons”  In _Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)_ , 2015, pp. 1655–1670  DOI: 10.1137/1.9781611973730.110
  * [19] Bernard Chazelle  “Approximation and decomposition of shapes”  In _Algorithmic and Geometric Aspects of Robotics_ 1, Advances in Robotics, 1987, pp. 145–185
  * [20] Bernard Chazelle  “Triangulating a Simple Polygon in Linear Time”  In _Discret. Comput. Geom._ 6, 1991, pp. 485–524  DOI: 10.1007/BF02574703
  * [21] Bernard Chazelle and Leonidas Palios  “Decomposition algorithms in geometry”  In _Algebraic Geometry and its applications_ , 1994, pp. 419–447  DOI: 10.1007/978-1-4612-2628-4˙27
  * [22] Xun Chen and Mingyong Chen  “Skeleton partition models for 3D printing”  In _Second International Conference on Medical Imaging and Additive Manufacturing (ICMIAM 2022)_ , 2022  DOI: 10.1117/12.2636369
  * [23] Hallard T. Croft, Kenneth J. Falconer and Richard K. Guy  “Unsolved Problems in Geometry”, Problem Books in Mathematics: Unsolved Problems in Intuitive Mathematics  Springer New York, 1991  DOI: 10.1007/978-1-4612-0963-8
  * [24] Mirela Damian and Sriram V. Pemmaraju  “Computing Optimal Diameter-Bounded Polygon Partitions”  In _Algorithmica_ 40.1, 2004, pp. 1–14  DOI: 10.1007/s00453-004-1092-3
  * [25] Herbert Edelsbrunner, David G. Kirkpatrick and Raimund Seidel  “On the shape of a set of points in the plane”  In _IEEE Trans. Inf. Theory_ 29.4, 1983, pp. 551–558  DOI: 10.1109/TIT.1983.1056714
  * [26] Herbert Edelsbrunner and Ernst Peter Mücke  “Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms”  In _ACM Trans. Graph._ 9.1, 1990, pp. 66–104  DOI: 10.1145/77635.77639
  * [27] Sándor P. Fekete, Tom Kamphans, Alexander Kröller, Joseph S. B. Mitchell and Christiane Schmidt  “Exploring and Triangulating a Region by a Swarm of Robots”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX-RANDOM 2011)_ , 2011, pp. 206–217  DOI: 10.1007/978-3-642-22935-0“˙18
  * [28] Erich Friedman  “Erich’s Packing Center” Accessed: 2022-10-17  URL: https://erich-friedman.github.io/packing/index.html
  * [29] Roser Guàrdia and Ferran Hurtado  “On the equipartition of plane convex bodies and convex polygons”  In _J. Geom._ 83 Springer, 2005, pp. 32–45  DOI: 10.1007/s00022-005-0006-0
  * [30] Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir and Robert Endre Tarjan  “Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons”  In _Algorithmica_ 2, 1987, pp. 209–233  DOI: 10.1007/BF01840360
  * [31] Aladár Heppes and Hans Melissen  “Covering a Rectangle With Equal Circles”  In _Period. Math. Hungar._ 34, 1997, pp. 65–81  DOI: 10.1023/A:1004224507766
  * [32] John Hershberger and Subhash Suri  “Matrix Searching with the Shortest-Path Metric”  In _SIAM J. Comput._ 26.6, 1997, pp. 1612–1634  DOI: 10.1137/S0097539793253577
  * [33] Susan Hert and Vladimir J. Lumelsky  “Polygon Area Decomposition for Multiple-Robot Workspace Division”  In _Int. J. Comput. Geom. Appl._ 8.4, 1998, pp. 437–466  DOI: 10.1142/S0218195998000230
  * [34] Janusz Januszewski  “A Note on Covering a Square of Side Length $2+\epsilon$ with Unit Squares”  In _Am. Math. Mon._ 116.2, 2009, pp. 174–178  URL: http://www.jstor.org/stable/27642695
  * [35] Thomas Jenrich and Andries E. Brouwer  “A 64-Dimensional Counterexample to Borsuk’s Conjecture”  In _Electron. J. Comb._ 21.4, 2014, pp. 4  DOI: 10.37236/4069
  * [36] Xiaotong Jiang, Xiaosheng Cheng, Qingjin Peng, Luming Liang, Ning Dai, Mingqiang Wei and Cheng Cheng  “Models partition for 3D printing objects using skeleton”  In _Rapid Prototyping Journal_ 23, 2017, pp. 54–64  DOI: 10.1108/RPJ-07-2015-0091
  * [37] Jeff Kahn and Gil Kalai  “A counterexample to Borsuk’s conjecture”  In _Bulletin of the American Mathematical Society_ 29.1, 1993, pp. 60–62  DOI: 10.1090/S0273-0979-1993-00398-7
  * [38] Roman Karasev, Alfredo Hubard and Boris Aronov  “Convex equipartitions: the spicy chicken theorem”  In _Geom. Dedicata_ 170 Springer, 2014, pp. 263–279  DOI: 10.1007/s10711-013-9879-5
  * [39] J. Mark Keil  “Polygon decomposition”  In _Handbook of computational geometry_ , 1999, pp. 491–518  DOI: 10.1016/B978-044482537-7/50012-7
  * [40] J. Mark Keil and Jörg-R. Sack  “Minimum Decompositions of Polygonal Objects”  In _Computational Geometry_ 2, Machine Intelligence and Pattern Recognition, 1985, pp. 197–216  DOI: 10.1016/B978-0-444-87806-9.50012-8
  * [41] Der-Tsai Lee and Franco P. Preparata  “Euclidean shortest paths in the presence of rectilinear barriers”  In _Networks_ 14.3, 1984, pp. 393–410  DOI: 10.1002/net.3230140304
  * [42] Linjie Luo, Ilya Baran, Szymon Rusinkiewicz and Wojciech Matusik  “Chopper: Partitioning models into 3D-printable parts”  In _ACM Trans. Graph._ 31.6, 2012, pp. 129:1–129:9  DOI: 10.1145/2366145.2366148
  * [43] Nimrod Megiddo  “Linear-Time Algorithms for Linear Programming in $\mathbb{R}^{3}$ and Related Problems”  In _SIAM J. Comput._ 12.4, 1983, pp. 759–776  DOI: 10.1137/0212052
  * [44] Hans Melissen  “Loosest circle coverings of an equilateral triangle”  In _Mathematics Magazine_ 70.2, 1997, pp. 118–124  DOI: 10.1080/0025570X.1997.11996514
  * [45] Avraham A. Melkman  “On-Line Construction of the Convex Hull of a Simple Polyline”  In _Inf. Process. Lett._ 25.1, 1987, pp. 11–12  DOI: 10.1016/0020-0190(87)90086-X
  * [46] R. Nandakumar and N. Ramana Rao  “Fair partitions of polygons: An elementary introduction”  In _Proc. Math. Sci._ 122 Springer, 2012, pp. 459–467  DOI: 10.1007/s12044-012-0076-5
  * [47] Joseph O’Rourke  “Art Gallery Theorems and Algorithms”  Oxford University Press, 1987
  * [48] Joseph O’Rourke, Subash Suri and Csaba D. Tóth  “Polygons”  In _Handbook of discrete and computational geometry_ , 2018, pp. 787–810  DOI: 10.1201/9781315119601
  * [49] Igor Pak and Jed Yang  “Tiling simply connected regions with rectangles”  In _J. Comb. Theory, Ser. A_ 120.7, 2013, pp. 1804–1816  DOI: https://doi.org/10.1016/j.jcta.2013.06.008
  * [50] Franco P. Preparata and Michael Ian Shamos  “Computational Geometry: An Introduction”, 1985  DOI: 10.1007/978-1-4612-1098-6
  * [51] Thomas C. Shermer  “Recent results in art galleries”  In _Proceedings of the IEEE_ 80.9, 1992, pp. 1384–1399  DOI: 10.1109/5.163407
  * [52] Alexander Soifer  “Covering a square of side $n+\varepsilon$ with unit squares”  In _J. Comb. Theory, Ser. A_ 113.2, 2006, pp. 380–383  DOI: 10.1016/j.jcta.2005.08.005
  * [53] Godfried T. Toussaint  “Solving geometric problems with the rotating calipers”  In _Mediterranean Electrotechnical Conference (MELECON 1983)_ , 1983
  * [54] Haitao Wang  “An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons”  In _Discret. Comput. Geom._ , 2022, pp. 1–29  DOI: 10.1007/s00454-022-00424-6
  * [55] Chris Worman  “Decomposing Polygons Into Diameter Bounded Components”  In _Canadian Conference on Computational Geometry (CCCG 2003)_ , 2003, pp. 103–106  URL: http://www.cccg.ca/proceedings/2003/9.pdf