Kai JinJohn Q. Open and Joan R. Acces 2 2017 2016 December 24–27, 2016 Little
Whinging, United Kingdom 42

# Maximal Area Triangles in a Convex Polygon

Kai Jin  Department of Computer Science, University of Hong Kong
<EMAIL_ADDRESS>
###### Abstract.

The widely known linear time algorithm for computing the maximum area triangle
in a convex polygon was found incorrect recently by Keikha et. al. [18]. We
present an alternative algorithm in this paper. Comparing to the only
previously known correct solution, ours is much simpler and more efficient.
More importantly, our new approach is powerful in solving related problems.

###### Key words and phrases:

Maximum-area Triangles, Discrete Convex Geometry, Geometric Optimization,
Computational Geometry, Convex Polygon

###### 1991 Mathematics Subject Classification:

I.3.5 Computational Geometry and Object Modeling

##  1\. Introduction

In [18], the widely known linear time algorithm for computing the maximum area
triangle in a given convex polygon $P$ (given in [11]) was found incorrect. An
alternative algorithm given in [5] is also wrong for the same reason. Also,
another algorithm (see [28]) not mentioned in [18] – perhaps because published
by an informal journal – is also wrong. Whether this problem can be solved in
linear time was proposed as an open problem in [18], and is of significance
because follow-up results in computational geometry (e.g. polygon collision
detection) may depend on finding the maximum area triangle as a preprocessing
step.

To study this problem, [18] introduced the 3-stable triangles, i.e. those
triangles whose corners lie at $P$’s vertices and which cannot be improved to
a larger one by adjusting the position of one corner. They proved that there
are $O(n)$ such triangles since they are pairwise interleaving (see Definition
1.1 below), where $n$ is the number of vertices in $P$. But it was left as an
open problem whether we can compute all the 3-stable triangles in $O(n)$ time.

However, via personal communication, the authors of [18] later pointed us to
an algorithm of Chandran and Mount [7], which correctly computes a superset of
the 3-stable triangles in linear time. This algorithm is a typical and clever
application of the well-known rotating-caliper technique [30]. It in fact
computes the maximum triangles in $P$ and the minimum triangle enclosing $P$
simultaneously (see more details in Subsection 1.1). Moreover, Chandran and
Mount showed in detail how to convert their algorithm into a parallel version.

In this paper, by applying a new technique for solving extremal polygon
inclusion problems which we call _Rotate-and-Kill_ , we present a different
linear time algorithm for computing the 3-stable triangles. This algorithm
(Alg-J) has advantages over the previous algorithm (Alg-CM) in almost every
aspect, except for the sole aspect from parallel computation.

Conciseness.:

Comparing the description of Alg-J (mainly in Algorithm 2) with that of Alg-CM
(mainly in pages 9–10 of [7]), the new algorithm is conceptually simpler. The
latter contains complicated subroutines for handling three different cases in
each iteration.

Easier proof.:

Correspondingly, our proof is much shorter and easier to understand. Our proof
is based on few prerequisite results – only the aforementioned pairwise
interleaving property proved in [18], whereas the proof of Alg-CM applies
nontrivial intermediate results of [19, 20, 26]. In fact, [7] has not given a
rigourous proof for its correctness.

Easier implementation.:

Alg-CM has not been implemented before our work. In order to justify the
superiority of our algorithm which was doubted by previous reviewers, we
implement both algorithms by _C++ programs_ (uploaded to [14]). Alg-J is 4
times shorter in the code length. In this place, we point out that an
implementation of Alg-CM requires much more attentions because many
degenerated cases are not discussed in [7]. For example, in Figure 5 of their
paper, $c$ could be coincided with $A$ or $B$, and then angles
$\theta_{a}=\angle axa^{\prime},\theta_{b}=\angle bxb^{\prime}$ could be
undefined; and in Figure 6 of their paper, $x$ may not lie in the ray
originating from $a$ towards $a^{\prime}$, which makes the definition of
$\theta_{b}$ problematic.

Efficiency.:

Our experiments (demonstrated in Figure 7) indicate that Alg-J is
approximately 30 times faster, which matches our expectation. Although both
run in $O(n)$ time, Alg-J has a smaller constant behind the asymptotic
complexity, and it only executes basic operations $+,-,\times,/$, whereas Alg-
CM seems unable to avoid trigonometric functions.

Robust.:

The _C++ program_ for Alg-J easily solves the large data cases where
$n=10^{7}$, whereas the _C++ program_ for Alg-CM fails even if $n=1000$ due to
accuracy problems of floating point operations. This shows the fact that Alg-J
is much more robust.

More importantly, the Rotate-and-Kill technique developed in this paper
(summarized in Subsection 1.3) is powerful in that it also solves other
polygon inclusion or circumscribing problems. For one example, the following
dual problem only admits $O(n\log n)$ time solutions in literature ([3, 29])
but can be solved in linear time by our new approach: Given $n$ half-planes
which constitute a convex polygon, find three of them whose intersecting area
is minimum. This is reported in a subsequent paper [15]. For another example,
in the second part of this paper (Appendix B), we use the new technique to
compute all the generally 3-stable triangles, i.e. those triangles whose
corners lie in $P$’s boundary (rather than $P$’s vertices) and whose area
cannot be improved through adjusting one corner (which include all the
3-stable triangles). This further leads to a new linear time solution for
computing the minimum area triangle enclosing $P$. Thus the algorithm in this
paper and the one in [7] can both compute the maximum triangle in $P$ and the
minimum triangle enclosing $P$ simultaneously. These examples suggest that
more efficient algorithms may exist for other related problems potentially, as
discussed in Subsection 1.1 below, and we hope that this paper has brought
incentives for revisiting these problems. Note that, as elucidated in [15],
some extra efforts seem necessary in applying our technique to any specific
problem.

###  1.1. Previous known algorithm given in [7] and other related work

We now briefly introduce Chandran and Mount’s method. They first define the
_$P$ -stable_ triangles (outside $P$). All sides of a $P$-stable triangle must
be touched by $P$. In particular, two of them must have their midpoints
touched by $P$; these two are called the _legs_ whereas the remaining one is
called the _base_. Moreover, one of the following holds. (1) The base is
flushed with $P$ (namely, it contains an edge of $P$). (2) one of the legs is
flushed with an edge of $P$ and has as its midpoint a vertex of this edge.
Note that if (1) holds, it is said _$P$ -anchored_. The $P$-anchored triangles
are in fact introduced in [20], where it is proved that they contain all the
local minimums of enclosing triangles of $P$. It is then proved in [26] that
all the $P$-anchored triangles are “interspersing” – if we move the base to
the next edge, the midpoints of two legs will both move in clockwise. Then, by
using the rotating-caliper technique [30] together with some clever
algorithmic tricks, [26] enumerates all the $P$-anchored triangles in linear
time and thus find the minimum enclosing triangles. The algorithm is somewhat
involved and description is only highlighted, so details on implementation is
given in [27].

Later, by using some “more involved” (as said in the paper) observations and
techniques, [7] managed to enumerate all the $P$-stable triangles in linear
time. Their algorithm is actually a terrific example of the rotating-caliper
technique. Moreover, it was proved that by enumerating all the $P$-stable
triangles, one can easily obtain all local maximums of triangles enclosed in
$P$. To sum up, the known algorithm in [7] indeed computes all the maximum
area triangles enclosed in $P$ and all the minimum area triangles enclosing
$P$ simultaneously.

The problems of searching for extremal figures with special properties inside
or outside a polygon were initiated in [11, 5, 8], and have since been studied
extensively. The minimum area triangle enclosing a convex polygon can be found
in $O(n\log^{2}n)$ time [20] or even in $O(n)$ time [26]. The minimum
perimeter triangle enclosing a convex polygon is solved in $O(n)$ time [4].
The maximum perimeter enclosed triangle can be solved in $O(n\log n)$ time
[5]. It is interesting to know whether this can be optimized to linear time.
At the same time when this paper was written, [17] presented an alternative
linear time algorithm for computing the maximum area triangles (which looks
more complicated than ours).

Moreover, [5, 2, 3, 8, 1, 25] studied extremal area / perimeter $k$-gon inside
or outside a convex polygon. The maximum $k$-gon can be computed in $O(n\log
n)$ time when $k$ is a constant and it is interesting to know whether this can
be optimized to linear time (at least for $k=4$). Furthermore, [32, 31] asked
and solved the extremal polytope problems in three dimensional space. Besides,
[23] considered maximum triangles inside a simple polygon.

Instead of $k$-gon, people care about extremal figures that admit more
geometric properties, such as equilateral triangle and squares, rectangles and
parallelograms, disks and ellipses. In particular, the largest-area
parallelogram is studied by the same author of this paper in [16, 13], who
gave a nontrivial algorithm for computing all locally maximal parallelograms
in a convex polygon in $O(n\log^{2}n)$ time. See [13] for more introductions
in this area.

De Pano, Ke and O’Rourke [10] pointed out that finding extremal polygons
inside a given polygon is usually more difficult than finding extremal
polygons outside a given polygon. The latter problems can usually be solved by
the rotating-caliper technique.

To be more complete, some properties of figures inscribed or circumscribed in
convex polygons or curves can be found in [6, 12, 9, 22, 24, 21] and the
references within.

###  1.2. Preliminary

Let $v_{1},\ldots,v_{n}$ be a clockwise enumeration of the vertices of $P$.
Assume that no three vertices lie in the same line. Let $e_{1},\ldots,e_{n}$
denote the $n$ edges of $P$, so that $e_{i}$ is the directed line segment
$\overrightarrow{v_{i}v_{i+1}}$. Denote the boundary of $P$ by $\partial P$.
For convenience, when $A$ denotes a vertex of $P$, we use notation $A-1$ and
$A+1$ to denote the clockwise previous and next vertex of $A$ respectively.
Given two distinct points $A,B$, let $\overleftrightarrow{AB}$ denote the line
connecting them.

For any triangle that forms by points in $\partial P$, we list its corners in
clockwise order; when $\triangle ABC$ is written, we always assume $A,B,C$ lie
in clockwise order.

Consider any triangle $\triangle ABC$ in which all corners lie in $\partial
P$. Note that corner $A$ lies on the right of $\overrightarrow{BC}$. We say
$A$ is _stable_ if it has the largest distance to $\overleftrightarrow{BC}$
among all points of $P$ that lie on the right of $\overrightarrow{BC}$.
Similarly, corner $B$ is _stable_ if it has the largest distance to
$\overleftrightarrow{CA}$ among all points of $P$ that lie on the right of
$\overrightarrow{CA}$. Corner $C$ is _stable_ if it has the largest distance
to $\overleftrightarrow{AB}$ among all points of $P$ that lie on the right of
$\overrightarrow{AB}$. The triangle $\triangle ABC$ is said _3-stable_ , if
all its corners are stable and lie on the vertices of $P$.

######  Definition 1.1 ([5, 18]).

Let $[A\circlearrowright B]$ denote the portion of $\partial P$ starting from
point $A$ and clockwise to $B$. Assume $\triangle A_{1}A_{2}A_{3},\triangle
B_{1}B_{2}B_{3}$ have all their corners lying on $P$’s boundary. They are
_interleaving_ if there exists at least one corner of $B$ lying in
$[A_{i}\circlearrowright A_{i+1}]$ for each $i\in\\{1,2,3\\}$ and there exists
at least one corner of $A$ lying in $[B_{i}\circlearrowright B_{i+1}]$ for
each $i\in\\{1,2,3\\}$.

######  Lemma 1.2 ([18]).

Any two 3-stable triangles in a convex polygon are interleaving.

######  Corollary 1.3 ([18]).

There are $O(n)$ 3-stable triangles.

###  1.3. Technique overview

We start by computing one 3-stable triangle using an ordinary method (see
Section 2); denote the resulting 3-stable triangle by $\triangle
v_{r}v_{s}v_{t}$. By Lemma 1.2, each 3-stable triangle interleaves $\triangle
v_{r}v_{s}v_{t}$, and hence has an edge $BC$ such that
$B\in\\{v_{s},\ldots,v_{t}\\}$ whereas $C\in\\{v_{t},\ldots,v_{r}\\}$.

We then compute all the 3-stable triangles in a process called Rotate-and-
Kill. Initially, set two pointers $(B,C)=(v_{s},v_{t})$. In each iteration, we
first compute $A$ so that $A$ has the largest distance to
$\overleftrightarrow{BC}$ among vertices of $P$ on the right of
$\overrightarrow{BC}$. This only costs amortized $O(1)$ time because the slope
of $BC$ keeps decreasing and so $A$ goes only in clockwise direction. Next,
check whether $\triangle ABC$ is 3-stable and report it if so, and go to the
next iteration by either killing $B$ (i.e. moving pointer $B$ to its next
vertex) or killing $C$ (i.e. moving pointer $C$ to its next vertex). The
criterion for killing $B$ or $C$ obeys two important rules: $B$ is killed only
when (1) its related pairs $(B,{C+1}),(B,{C+2}),...,(B,v_{r})$ cannot form an
edge of any 3-stable triangle; and $C$ is killed only when (2) its related
pairs $(B+1,C),(B+2,C),...(v_{t},C)$ cannot form an edge of any 3-stable
triangle. In this way, noticing that $(v_{t},v_{r})$ forms an edge of the
3-stable triangle $\triangle v_{s}v_{t}v_{r}$, we make sure that $(B,C)$
eventually reaches $(v_{t},v_{r})$ and that all the 3-stable triangles are
going to be reported before that moment.

The core of our technique lies in designing an efficient criterion for
killing. We may attempt either of the following criterions at first: 1.
Determine (1) directly and kill $B$ when (1) holds and $C$ otherwise. 2.
Determine (2) directly and kill $C$ when (2) holds and $B$ otherwise. Notice
that at least one of (1) and (2) holds in every iteration of $(B,C)$ (this is
an easy corollary of Lemma 1.2; see the details in Observation 3.1 and its
proof below), so both criterions satisfy the aforementioned rules. However,
determining (1) or (2) directly would cost $O(n)$ time by trivial methods or
$O(\log n)$ time by binary searches. For a linear running time of the Rotate-
and-Kill process, we must find a better criterion that can be computed in
$O(1)$ time. Such a criterion is presented in Section 3.1, which is
surprisingly simple.

We see the Rotate-and-Kill technique is distinct from the rotating-caliper
technique [30]. Instead, it can be regarded as a corrective version of Dobkin
and Snyder’s technique [11].

##  2\. Compute one 3-stable triangle

In this section, we show how to compute one 3-stable triangle.111Not only one
previous reviewers mistakenly claimed that our algorithm given in this section
is the same as the algorithm given in [11]. In fact, Step 2 of our algorithm
is the same as the kernel step of the previous algorithm (by coincidence), but
Step 1 will set the initial value differently – we will start from
$(B_{0},C_{0})$ so that $A_{0}B_{0}C_{0}$ is the largest triangle rooted at
$A_{0}$ but their algorithm starts from $(B^{\prime},C^{\prime})$ where
$(B^{\prime},C^{\prime})$ is the first pair of 2-stable corners with respect
to $A_{0}$. So the two algorithms are different.

We say a triangle is _rooted_ at a vertex if one of its corner lies on that
vertex.

Step 1. Choose $A$ to be an arbitrary vertex of $P$; say $A=v_{1}$. Find $B,C$
so that $ABC$ is the largest triangle rooted at $A$. This can be done in
$O(n)$ time. We can enumerate a vertex $B$ and maintain $C_{B}$ in amortized
$O(1)$ time so that $C_{B}$ is the vertex with the largest distance to
$\overleftrightarrow{AB}$ among all vertices on the right of
$\overrightarrow{AB}$. Then, select $B$ so that $ABC_{B}$ is maximum.

Since $ABC$ is the largest triangle rooted at $A$, corners $B,C$ are stable.
Moreover, if corner $A$ is also stable, $\triangle ABC$ is 3-stable and we can
go to the next section.

Now, assume that $A$ is not stable. Moreover, assume that $A+1$ is further
than $A$ in the distance to $\overleftrightarrow{BC}$. Otherwise $A-1$ is
further than $A$ and it is symmetric.

Step 2. This step is presented in Algorithm 1.

1 $A\leftarrow A+1$;

2 repeat

3 while  _( $(B+1)>B$ in the distance to $\overleftrightarrow{AC}$)_ do

4 $B\leftarrow B+1$;

5 end while

6 while  _( $(C+1)>C$ in the distance to $\overleftrightarrow{AB}$)_ do

7 $C\leftarrow C+1$;

8 end while

9

10until  _$(B+1)\leq B$ (to $\overleftrightarrow{AC}$) and $(C+1)\leq C$ (to
$\overleftrightarrow{AB}$)_;

Algorithm 1 Algorithm for Step 2

To distinguish, we denote the value of the three pointers $(A,B,C)$ at the end
phase of this algorithm by $(A_{1},B_{1},C_{1})$; and the value at the
beginning phase by $(A_{0},B_{0},C_{0})$.

Figure 1. Illustration of Step 2 and Step 3

######  Observation 2.1.

  1. (1)

Corners $B_{1},C_{1}$ are stable in $\triangle A_{1}B_{1}C_{1}$.

  2. (2)

$Area(\triangle A_{1}B_{1}C_{1})>Area(\triangle A_{0}B_{1}C_{1})$.

######  Proof 2.2.

1\. It reduces to prove the following arguments.

  1. (1)

$B_{1}$ is at least as far as $B_{1}-1$ in the distance to
$\overleftrightarrow{A_{1}C_{1}}$.

  2. (2)

$B_{1}$ is at least as far as $B_{1}+1$ in the distance to
$\overleftrightarrow{A_{1}C_{1}}$.

  3. (3)

$C_{1}$ is at least as far as $C_{1}-1$ in the distance to
$\overleftrightarrow{A_{1}B_{1}}$.

  4. (4)

$C_{1}$ is at least as far as $C_{1}+1$ in the distance to
$\overleftrightarrow{A_{1}B_{1}}$.

Due to the termination condition of the algorithm, (2) and (4) hold. In the
following we point out two facts that hold throughout the algorithm, which
respectively imply (1) and (3).

  1. (i)

$B$ is at least as far as $B-1$ in the distance to $\overleftrightarrow{AC}$.

  2. (ii)

$C$ is at least as far as $C-1$ in the distance to $\overleftrightarrow{AB}$.

These facts hold at the beginning, because $B_{0},C_{0}$ are stable in
$A_{0}B_{0}C_{0}$. When $A,B$ or $C$ are increased by 1 (at Line 1,4,7), these
facts still hold as illustrated in Figure 1 (b),(c),(d).

2\. See Figure 1 (a). By the assumption right above “Step 2”, $A_{1}=A_{0}+1$
is further than $A_{0}$ in the distance to $\overleftrightarrow{B_{0}C_{0}}$.
Comparing the slopes of $\overleftrightarrow{B_{1}C_{1}}$ and
$\overleftrightarrow{B_{0}C_{0}}$, it implies that $A_{1}$ is further than
$A_{0}$ in the distance to $\overleftrightarrow{B_{1}C_{1}}$, which is another
way of saying Claim 2.

Step 3. So far, we obtain another triangle $\triangle A_{1}B_{1}C_{1}$ where
$B_{1},C_{1}$ are stable (according to Observation 2.1.1). If $A_{1}$ is also
stable, $\triangle A_{1}B_{1}C_{1}$ is 3-stable and we proceed to next
section. Now, consider the case where $A_{1}$ is not stable. Since $A_{1}$ is
not stable, applying Observation 2.1.2, vertex $A_{1}+1$, rather than
$A_{1}-1$, must be further than $A_{1}$ in the distance to
$\overleftrightarrow{B_{1}C_{1}}$. We call Algorithm 1 once again with initial
value $(A_{1},B_{1},C_{1})$ and terminal value $(A_{2},B_{2},C_{2})$, and
repeat such a process until $\triangle A_{i}B_{i}C_{i}$ is 3-stable for some
integer $i$.

##### Correctness and running time.

At every change of $A,B,C$ in Algorithm 1, the area of $\triangle ABC$
increases. So the above algorithm terminates eventually. Because pointers
$A,B,C$ can only move in the clockwise direction and pointer $A$ cannot return
to $A_{0}$ (otherwise we obtain a triangle rooted at $A_{0}$ with a larger
area than $A_{0}B_{0}C_{0}$, which contradicts the assumption of
$A_{0}B_{0}C_{0}$), and because $A,B,C$ always lie in clockwise order, the
total number of changes of $A,B,C$ is bounded by $O(n)$ and hence the
algorithm runs in $O(n)$ time.

##  3\. Compute all the 3-stable triangles

In this section, we assume $\triangle v_{r}v_{s}v_{t}$ is 3-stable and we
compute all 3-stable triangles by a Rotate-and-Kill process as mentioned in
Subsection 1.3. We start by an observation.

A vertex pair $(v_{j},v_{k})$ is _dead_ if it cannot form an edge of any
3-stable triangle; precisely, if there is no vertex $v_{i}$ such that
$\triangle v_{i}v_{j}v_{k}$ is 3-stable and $v_{i},v_{j},v_{k}$ lie in
clockwise order.

######  Observation 3.1.

Assume $B\in\\{v_{s},\ldots,v_{t}\\}$, $C\in\\{v_{t},\ldots,v_{r}\\}$, and
$B\neq C$. Then,

  1. (1)

$(B,C+1),(B,C+2),\ldots,(B,v_{r})$ are all dead; or

  2. (2)

$(B+1,C),(B+2,C),\ldots,(v_{t},C)$ are all dead.

######  Proof 3.2.

Suppose that (1) and (2) are both false. Without loss of generality, assume
that $(B,C^{\prime})$ and $(B^{\prime},C)$ are not dead, where
$C^{\prime}\in\\{C+1,\ldots,v_{r}\\}$ and
$B^{\prime}\in\\{B+1,\ldots,v_{t}\\}$. This implies that there exist
$A_{1},A_{2}$ so that $\triangle A_{1}BC^{\prime}$ and $\triangle
A_{2}B^{\prime}C$ are 3-stable. Because $C^{\prime}\in\\{C+1,\ldots,v_{r}\\}$
whereas $B^{\prime}\in\\{B+1,\ldots,v_{t}\\}$, triangle $\triangle
A_{1}BC^{\prime}$ does not interleave $\triangle A_{2}B^{\prime}C$. So at
least one of them is not 3-stable due to Lemma 1.2. Contradictory.

Figure 2. Definition of the area $Q_{j,k}$.

######  Definition 3.3.

Assume $v_{j},v_{k}$ are distinct vertices of $P$. See Figure 2.

Let $r_{1}$ (respectively, $r_{2}$) denote the ray originating from $v_{j}$
with the same direction as $e_{k-1}$ (respectively, $e_{k}$). Let
$r^{\prime}_{1}$ (respectively, $r^{\prime}_{2}$) denote the ray originating
from $v_{k}$ with the opposite direction to $e_{j-1}$ (respectively, $e_{j}$).
(Here, recall that each edge is a directed line segment; specifically, the
direction of $e_{i}$ is from $v_{i}$ to $v_{i+1}$.) These four rays
$r_{1},r_{2},r^{\prime}_{1},r^{\prime}_{2}$ together define a region, denoted
by $Q_{j,k}$. The intersecting point between $r_{1},r^{\prime}_{1}$ is denoted
by $H_{j,k}$. The intersecting point between $r_{2},r^{\prime}_{2}$ is denoted
by $I_{j,k}$. The intersecting point between $r_{1},r^{\prime}_{2}$ is denoted
by $J_{j,k}$. The intersecting point between $r_{2},r^{\prime}_{1}$ is denoted
by $K_{j,k}$.

Note: When $I_{j,k}$ (or $H_{j,k},J_{j,k},K_{j,k}$) is undefined in the above
(when the corresponding two rays do not intersect), we define $I_{j,k}=\infty$
(or $H_{j,k}=\infty,J_{j,k}=\infty,K_{j,k}=\infty$, respectively) and assume
that it has an infinite distance to $\overline{v_{j}v_{k}}$. We consider that
the region $Q_{j,k}$ contains its boundary. We consider that polygon $P$ also
contains its boundary.

Roughly speaking, $Q_{j,k}$ indicates the potential region of a corner of a
3-stable triangle when the other two corners are fixed in $v_{j}$ and $v_{k}$.
This is made precisely as follows.

######  Observation 3.4.

Suppose $v_{j},v_{k}$ are stable in $\triangle v_{i}v_{j}v_{k}$. Then, $v_{i}$
lies in $Q_{j,k}$.
(Recall that whenever we write $\triangle v_{i}v_{j}v_{k}$, we assume that
$v_{i},v_{j},v_{k}$ lie in clockwise order.)

######  Proof 3.5.

See Figure 2. Because $v_{j}$ is stable, $v_{i}$ can only lie in the sector
area bounded by $r^{\prime}_{1}$ and $r^{\prime}_{2}$. Because $v_{k}$ is
stable, $v_{i}$ can only lie in the sector area bounded by $r_{1}$ and
$r_{2}$. Together, $v_{i}$ lies in the intersection of these two sector areas,
which is defined as $Q_{j,k}$.

######  Definition 3.6.

We regard vertex pair $(v_{j},v_{k})$ _illegal_ if $v_{k+1}$ is closer than
$v_{k}$ in the distance to $\overleftrightarrow{v_{j}v_{j+1}}$ (as shown in
Figure 3.a) and regard $(v_{j},v_{k})$ _legal_ otherwise (see Figure 3.b).

Note: For each vertex $v_{j}$ of $P$, the sequence of vertex pairs
$(v_{j},v_{j+1}),(v_{j},v_{j+2}),\ldots,(v_{j},v_{j-1})$ starts with several
legal pairs and then is followed by several illegal pairs. In particular,
$(v_{j},v_{j+1})$ is legal and $(v_{j},v_{j-1})$ is illegal. (All subscripts
taken modulo $n$.)

Figure 3. Illustration of the notion of “legal pair”.

######  Observation 3.7 (Sufficient conditions for determining that
$(v_{j},v_{k})$ is dead).

  1. (1)

If $Q_{j,k}$ does not intersect $P$, then $(v_{j},v_{k})$ is dead.

  2. (2)

When $(v_{j},v_{k})$ is illegal, $Q_{j,k}$ does not intersect $P$ and hence is
dead.

  3. (3)

If there exists some point $A$ in $P$ which lies on the right of
$\overrightarrow{v_{j}v_{k}}$ and is further than $K_{j,k}$ in the distance to
$\overleftrightarrow{v_{j}v_{k}}$, then we can determine that $(v_{j},v_{k})$
is dead.

######  Proof 3.8.

1\. Suppose to the opposite $(v_{j},v_{k})$ is not dead, then there exists
$v_{i}$ such that $\triangle v_{i}v_{j}v_{k}$ is 3-stable. By Observation 3.4,
$Q_{j,k}$ contains $v_{i}$ and hence intersects $P$.

2\. Recall the two rays $r^{\prime}_{1},r^{\prime}_{2}$ in Definition 3.3.
When $(v_{j},v_{k})$ is illegal, the area bounded by
$r^{\prime}_{1},r^{\prime}_{2}$ (except apex $v_{k}$) lies outside $P$ (see
Figure 3 (c)). So, the subregion $Q_{j,k}$ of this area cannot intersect $P$
on any position other than $v_{k}$. Moreover, since $(v_{j},v_{j+1})$ is
always legal, we know $k\neq j+1$ when $(v_{j},v_{k})$ is illegal, and thus
$v_{k}$ does not lie in $Q_{j,k}$ (see Figure 2). Together, $Q_{j,k}$ has no
intersection with $P$, hence $(v_{j},v_{k})$ is dead according to Claim 1.

3\. Suppose to the opposite that $(v_{j},v_{k})$ is not dead but $\triangle
v_{i}v_{j}v_{k}$ is 3-stable for some vertex $v_{i}$. By Observation 3.4,
$v_{i}$ is contained in $Q_{j,k}$. Further applying the definition of
$Q_{j,k}$ (see Figure 2 (a)), this means $v_{i}$ is not further than $K_{j,k}$
in the distance to $\overleftrightarrow{v_{j}v_{k}}$. Therefore, $A$ is
further than $v_{i}$ in the distance to $\overleftrightarrow{v_{j}v_{k}}$,
thus $v_{i}$ is not stable in $\triangle v_{i}v_{j}v_{k}$. Contradictory.

###  3.1. Rotate-and-Kill process

Recall the Rotate-and-Kill process briefly discussed in Section 1.3. We
present its details below in Algorithm 2 and demonstrate it by a concrete
example in Figure 4. Its running time is already analyzed in Section 1.3 and
its correctness is assured by the next lemma.

Input: $r,s,t$ such that $\triangle v_{r}v_{s}v_{t}$ is 3-stable.

1 $(A,B,C)\leftarrow(v_{r},v_{s},v_{t})$;

2 repeat

3 while  _$(A+1) >A$ in the distance to $\overleftrightarrow{BC}$ _ do

4 $A\leftarrow A+1$;

5 end while

6 Output $ABC$ if it is 3-stable; Output $(A+1)BC$ if it is 3-stable;

7 if  _$A >I_{B,C}$ in the distance to $\overleftrightarrow{BC}$_ then

8 $C\leftarrow C+1$;

9 else

10 $B\leftarrow B+1$;

11 end if

12

13until  _$(B,C)=(v_{t},v_{r})$_ ;

Algorithm 2 The Rotate-and-Kill process

Figure 4. Example of the Rotate-and-Kill process.

######  Lemma 3.9.

  1. (1)

When vertex $B$ is about to be killed in Algorithm 2 (that means we are about
to run Line 2), $(B,C+1),(B,C+2),\ldots,(B,v_{r})$ are dead.

  2. (2)

When vertex $C$ is about to be killed in Algorithm 2 (that means we are about
to run Line 2), $(B+1,C),(B+2,C),\ldots,(v_{t},C)$ are dead.

  3. (3)

Throughout the “repeat” statement, $B\in\\{v_{s},\ldots,v_{t}\\}$,
$C\in\\{v_{t},\ldots,v_{r}\\}$, and $B\neq C$. Moreover, the “repeat”
statement will terminate successfully at $(B,C)=(v_{t},v_{r})$.

  4. (4)

Altogether, every 3-stable triangle will be computed by Algorithm 2.

######  Proof 3.10.

3\. For ease of understanding, we first prove Claim 3, assuming that Claim 1,2
are correct. Notice that $(v_{t},v_{r})$ forms an edge of a 3-stable triangle
(that is $\triangle v_{r}v_{s}v_{t}$). Therefore, Claim 1 and 2 imply that $B$
would not be killed when $(B=v_{t},C<v_{r})$, and $C$ would not be killed when
$(B<v_{t},C=v_{r})$. So $(B,C)$ eventually become $(v_{t},v_{r})$, at which
moment the algorithm terminates, and we have $B\in\\{v_{s},\ldots,v_{t}\\}$
and $C\in\\{v_{t},\ldots,v_{r}\\}$ throughout.

In addition, we argue that $B\neq C$ throughout. Suppose $B=C$ in some
iteration. It must be $B=C=v_{t}$. This means that we have killed $B$ at the
previous iteration $(B,C)=(v_{t-1},v_{t})$. But this is impossible by the
following analysis. When $(B,C)=(v_{t-1},v_{t})$, we know $C=B+1$, and hence
$I_{B,C}=B$, which further implies that “$A>I_{B,C}$ in the distance to
$\overleftrightarrow{BC}$”. So we would enter Line 2 and kill $C$ rather than
enter Line 2 and kill $B$ at that iteration.

1\. Assume we are at Line 2, and so $A\leq I_{B,C}$ in the distance to
$\overleftrightarrow{BC}$. Further assume that _$C$ is closer than $C+1$ in
the distance to $\overleftrightarrow{B(B+1)}$_, as shown in Figure 5.
Otherwise, $(B,C+1),...,(B,v_{r})$ are all illegal and hence are dead (by
Observation 3.7).

Let $l$ denote the unique line at $I_{B,C}$ that is parallel to
$\overleftrightarrow{BC}$. Let $C^{*}$ denote the last vertex in the sequence
$C+1,\ldots,v_{r}$ so that $(B,C^{*})$ is legal. We first state two facts.

  1. a.

Polygon $P$ lies in the (closed) half-plane delimited by $l$ and containing
$BC$.

  2. b.

$Q_{B,C+1},\ldots,Q_{B,C^{*}}$ lie in the (open) half-plane delimited by $l$
and not containing $BC$.

Figure 5. Illustration for the correctness on Line 2.

Combining Fact a and b, no region in $\\{Q_{B,C+1},\ldots,Q_{B,C^{*}}\\}$
intersects $P$. So $(B,C+1),\ldots,(B,C^{*})$ are dead according to
Observation 3.7.1. Moreover, $\\{(B,C^{*}+1),\ldots,(B,v_{r})\\}$ are dead
because of illegal (by Observation 3.7.2). Together, Claim 1 holds.

_Proof of a_. By the assumption, we know $A\leq I_{B,C}$ in the distance to
$\overleftrightarrow{BC}$. Moreover, $A$ has the largest distance among all
vertices of $P$ that lie on the right of $\overrightarrow{BC}$ (this is is
guaranteed by the “while-do” sentence in Algorithm 2). Together, we get claim
a.

_Proof of b_. Here, we define a region $R_{j,k}$ for each legal pair
$(v_{j},v_{k})$ so that $k\neq j+1$. Recall $H_{j,k},I_{j,k},J_{j,k}$ in
Definition 3.3. See Figure 2 (a) and (b). The unique quadrant bounded by
$\overrightarrow{J_{j,k}I_{j,k}},\overrightarrow{J_{j,k}H_{j,k}}$ and
containing $Q_{j,k}$ is defined as $R_{j,k}$. Observe Figure 5 (b), we have

$R_{B,C+1}\supseteq R_{B,C+2}\supseteq\ldots\supseteq R_{B,C^{*}}.$

It implies that $Q_{B,C+1},Q_{B,C+2},\ldots,Q_{B,C^{*}}$ lie in $R_{B,C+1}$.
Now, it reduces to show that $R_{B,C+1}$ lies entirely in the (open) half-
plane delimited by $l$ and not containing $BC$ (see Figure 5 (a)). This holds
because apex $J_{B,C+1}$ of $R_{B,C+1}$ lies in that half-plane, which is
because $\overrightarrow{I_{B,C}J_{B,C+1}}$ is a translate of
$\overrightarrow{C(C+1)}$ and $C$ is closer than $C+1$ to
$\overleftrightarrow{B(B+1)}$.

2\. Assume we are at Line 2, and so $A>I_{B,C}$ in the distance to
$\overleftrightarrow{BC}$. Since $A>I_{B,C}$, we have $I_{B,C}\neq\infty$, so
_$C$ is closer than $C+1$ in the distance to $\overleftrightarrow{BB+1}$_, as
shown in Figure 6.

Let $D$ denote the intersection between $\overleftrightarrow{C(C+1)}$ and $l$.
Let $d_{B,C}(X)$ denote the distance from $X$ to $\overleftrightarrow{BC}$ for
any vertex pair $(B,C)$. See Figure 6 (a). We claim two inequalities:

  1. I

$d_{B+1,C}(D)<d_{B+1,C}(A)$.

  2. II

$d_{B+1,C}(K_{B+1,C})=d_{B+1,C}(D)$.

Figure 6. Illustration for the correctness on Line 2.

Together, $d_{B+1,C}(A)>d_{B+1,C}(K_{B+1,C})$, thus $(B+1,C)$ is dead by
Observation 3.7.3.

_Proof of I_. Since $A>I_{B,C}$ in the distance to $\overleftrightarrow{BC}$,
it lies in the (open) half-plane delimited by $l$ and not containing $BC$.
Moreover, since $P$ is convex, $A$ lies in the (closed) half-plane delimited
by $\overleftrightarrow{CC+1}$ and containing $P$. Together, we obtain (I).

_Proof of II_. Obviously, both segment $(B+1)K_{B+1,C}$ and $CD$ are
translates of $BI_{B,C}$. So, $(B+1)K_{B+1,C}DC$ is a parallelogram. This
implies (II).

Next, we argue that $(B+2,C)$ is dead. This reduces to prove the following:

  1. (III)

$d_{B+2,C}(A)>d_{B+2,C}(K_{B+2,C})$.

(III) is implied by the above inequality $d_{B+1,C}(A)>d_{B+1,C}(K_{B+1,C})$.
This is simply illustrated in Figure 6 (b). The proof is similar to the proofs
of (I) and (II) and is omitted.

Furthermore, by induction, $(B+1,C),(B+2,C),\ldots(v_{t},C)$ are all dead.

4\. Assume triangle $T$ is 3-stable. Since $T$ and $\triangle v_{r}v_{s}v_{t}$
are both 3-stable, they interleave by Lemma 1.2. Without loss of generality,
we can assume that $T=\triangle v_{i}v_{j}v_{k}$ where $v_{i},v_{j},v_{k}$
respectively lies in $\\{v_{r},\ldots,v_{s}\\}$, $\\{v_{s},\ldots,v_{t}\\}$,
$\\{v_{t},\ldots,v_{r}\\}$. Since $\triangle v_{i}v_{j}v_{k}$ is 3-stable, the
vertex pair $(v_{j},v_{k})$ is not dead. Applying Claim 1, 2 and 3 altogether,
this means we will enter an iteration in which $(B,C)=(v_{j},v_{k})$. Let
$A^{*}$ denote the value of $A$ after the first “while-do” statement (which
updates $A$ to be the vertex with the largest distance to
$\overleftrightarrow{BC}$) in this iteration. Because $v_{i}$ is stable in
$T$, we know $v_{i}$ has the largest distance to
$\overleftrightarrow{v_{j}v_{k}}=\overleftrightarrow{BC}$, which implies that
$v_{i}\in\\{A^{*},A^{*}+1\\}$. Therefore, $\triangle v_{i}v_{j}v_{k}$ will be
outputted at Line 2.

##### Experiments.

The implementations of our algorithm and the algorithm of [7] are given in a
zip file at [14]. The experiment results are demonstrated in Appendix A.

##### Extension.

We introduce generally 3-stable triangles and design a linear time algorithm
for computing them in Appendix B. This further algorithms leads to a linear
time algorithm for computing the minimum area enclosing triangle as shown in
Appendix B.5.

#### Acknowledgement

The author thank Professor Zhiyi Huang for discussion. We also thank the
authors of [18] for giving us the opportunity to revisit such an interesting
and classic problem.

## References

  * [1] A. Aggarwal, J. S. Chang, and C. K. Yap.  Minimum area circumscribing polygons.  The Visual Computer, 1(2):112–117, Aug 1985.  doi:10.1007/BF01898354.
  * [2] A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber.  Geometric applications of a matrix-searching algorithm.  Algorithmica, 2(1-4):195–208, 1987.
  * [3] A. Aggarwal, B. Schieber, and T. Tokuyama.  Finding a minimum-weight $k$-link path in graphs with the concave monge property and applications.  Discrete & Computational Geometry, 12(1):263–280, 1994.
  * [4] B. Bhattacharya and A. Mukhopadhyay.  On the Minimum Perimeter Triangle Enclosing a Convex Polygon, pages 84–96.  Springer Berlin Heidelberg, 2003.  doi:10.1007/978-3-540-44400-8_9.
  * [5] J. E. Boyce, D. P. Dobkin, R. L. (Scot) Drysdale, III, and L. J. Guibas.  Finding extremal polygons.  In 14th Symposium on Theory of Computing, pages 282–289, 1982.
  * [6] P. Brab, G. Rote, and K. J. Swanepoel.  Triangles of extremal area or perimeter in a finite planar point set.  Discrete & Computational Geometry, 26:51–58, 2001.  doi:10.1007/s00454-001-0010-6.
  * [7] S. Chandran and D. M. Mount.  A paraellel algorithm for enclosed and enclosing triangles.  International Journal of Computational Geometry & Applications, 02(02):191–214, 1992.  doi:10.1142/S0218195992000123.
  * [8] J. S. Chang and C. K. Yap.  A polynomial solution for potato-peeling and other polygon inclusion and enclosure problems.  In 25th Symposium on Foundations of Computer Science, pages 408–416, Oct 1984.  doi:10.1109/SFCS.1984.715942.
  * [9] M. M. Day.  Polygons circumscribed about closed convex curves.  Transactions of the American Mathematical Society, 62(2):315–319, 1947.
  * [10] N. A. De Pano, Y. Ke, and J. O’Rourke.  Finding largest inscribed equilateral triangles and squares.  In 25th Allerton Conference on Communication, Control, and Computing, pages 869–878, 1987.
  * [11] D. P. Dobkin and L. Snyder.  On a general method for maximizing and minimizing among certain geometric problems.  In 20th Symposium on Foundations of Computer Science, pages 9–17, Oct 1979.  doi:10.1109/SFCS.1979.28.
  * [12] A. Dumitrescu, M. Sharir, and C. D. Tóth.  Extremal problems on triangle areas in two and three dimensions.  Journal of Combinatorial Theory, Series A, 116(7):1177 – 1198, 2009\.  doi:https://doi.org/10.1016/j.jcta.2009.03.008.
  * [13] K. Jin.  Maximal parallelograms in convex polygons - a novel geometric structure.  CoRR, abs/1512.03897, 2015.  URL: http://arxiv.org/abs/1512.03897.
  * [14] K. Jin.  Implementations by c++ programs.  https://drive.google.com/open?id=1jnaqwhTgN4EB6kXXIXqqX1VNl-9Ct6M1, 2017\.  [Online; accessed 22-April-2017].
  * [15] K. Jin and Z. Huang.  Minimum area all-flush triangles circumscribing a convex polygon.  CoRR, abs/1712.05081, 2017.
  * [16] K. Jin and K. Matulef.  Finding the maximum area parallelogram in a convex polygon.  In 23rd Canadian Conference on Computational Geometry, 2011.
  * [17] Y. Kallus.  A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon.  CoRR, abs/1706.03049, 2017.
  * [18] V. Keikha, M. Löffler, J. Urhausen, and I. v. d. Hoog.  Maximum-area triangle in a convex polygon, revisited.  CoRR, abs/1705.11035, 2017.
  * [19] V. Klee.  Facet centroids and volume minimization.  Studia Scientiarum Mathematicarum Hungarica, 21:143–147, 1986.
  * [20] V. Klee and M. C. Laskowski.  Finding the smallest triangles containing a given convex polygon.  Journal of Algorithms, 6(3):359 – 375, 1985.  doi:https://doi.org/10.1016/0196-6774(85)90005-7.
  * [21] M. Lassak.  Approximation of convex bodies by inscribed simplices of maximum volume.  Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry, 52(2):389, May 2011.  doi:10.1007/s13366-011-0026-x.
  * [22] M. Levi.  Minimal perimeter triangles.  The American Mathematical Monthly, 109(10):890–899, 2002.
  * [23] E. A. Melissaratos and D. L. Souvaine.  Shortest paths help solve geometric optimization problems in planar regions.  SIAM Journal on Computing, 21(4):601–638, 1992.  doi:10.1137/0221038.
  * [24] A. Miernowski, W. Mozgawa, and W. Rzymowski.  Minimal area n-simplex circumscribing a strictly convex body in $r^{n}$.  Journal of Geometry, 87(1):99–105, Nov 2007.  doi:10.1007/s00022-006-1905-4.
  * [25] J. S. B. Mitchell and V. Polishchuk.  Minimum-perimeter enclosures.  Information Processing Letters, 107(3):120–124, 2008.  doi:https://doi.org/10.1016/j.ipl.2008.02.007.
  * [26] J. O’Rourke, A. Aggarwal, S. Maddila, and M. Baldwin.  An optimal algorithm for finding minimal enclosing triangles.  Journal of Algorithms, 7(2):258 – 269, 1986.  doi:http://dx.doi.org/10.1016/0196-6774(86)90007-6.
  * [27] O. Pârvu and D. Gilbert.  Implementation of linear minimum area enclosing triangle algorithm.  Computational and Applied Mathematics, 35(2):423–438, Jul 2016\.  doi:10.1007/s40314-014-0198-8.
  * [28] A. K. Pujari and A. Nataraj.  Linear algorithm to find the largest intriangles of a planar convex polygon.  Kybernetes, 25(5):53–59, 1996.  doi:10.1108/03684929610124122.
  * [29] B. Schieber.  Computing a minimum-weight $k$-link path in graphs with the concave monge property.  In 6th Symposium on Discrete Algorithms, pages 405–411. Society for Industrial and Applied Mathematics, 1995.
  * [30] G. Toussaint.  Solving geometric problems with the rotating calipers.  In IEEE MELECON’83, pages 10–02, 1983.
  * [31] F. Vivien and N. Wicker.  Minimal enclosing parallelepiped in 3d.  Computational Geometry, 29(3):177 – 190, 2004.  doi:https://doi.org/10.1016/j.comgeo.2004.01.009.
  * [32] Y. Zhou and S. Suri.  Algorithms for a minimum volume enclosing simplex in three dimensions.  SIAM Journal on Computing, 31(5):1339–1357, 2002.  doi:10.1137/S0097539799363992.

##  Appendix A Experiments: Alg-J is approximately 30 times faster than Alg-CM

Figure 7. Experiment results. In each paragraph, the first two lines show
results of calling Alg-J.exe and Alg-CM.exe produced by VC++ compiler for
release-mode, and the last two lines show results of calling Alg-J.exe and
Alg-CM.exe produced by VC++ compiler for debug-mode.

Note: 1\. For Alg-CM, we only calculate the running time of the main procedure
after the initialization of computing the initial value of $A,B,C$. In
contrast, for Alg-J, the initialization of computing the initial value of
$r,s,t$ is included. Even in this unfair competition, Alg-CM is approximately
30 times slower. The reader may download and run our codes in [14].

2\. Because Alg-CM is not robust and fails easily for data cases where
$n>1000$, we can only compare it with Alg-J for data cases where $n\approx
500$. Since $n$ is too small in such data cases, both algorithms would run in
an unobservable short time. Therefore, we repeat both algorithms for 10000
times and calculate the total running time for each data case. Note that the
input and output procedure are not calculated into the total running time.

##  Appendix B Compute all the generally 3-stable triangles

In this section, we introduce and compute generally 3-stable triangles.

We call each vertex or edge a _unit_ of $P$. We regard that the edges do _not_
contain their endpoints. Therefore, each point in $\partial P$ belongs to a
unique unit.

Recall that $\triangle ABC$ is 3-stable if its three corners $A,B,C$ are
stable in $\triangle ABC$ and lie on some vertices of $P$. In the following we
define a superset called _generally 3-stable triangles_. Basically, it only
removes the requirement of lying on the vertices. However, there could be
infinite many of such triangles and we select representatives from each
equivalent class.

Figure 8. Illustration for generally 3-stable triangles.

######  Definition B.1 (Generally 3-stable triangles).

Assume that there is a triangle whose corners are stable and lie in
$e_{i},v_{j},v_{k}$ respectively (in clockwise order). It is clear that
$\overline{v_{j}v_{k}}$ is parallel to $e_{i}$ as shown in Figure 8 (a),
otherwise the corner in $e_{i}$ is not stable. Let the intersecting segment of
$e_{i}$ and $Q_{j,k}$ be denoted by $\overline{X_{1}X_{2}}$. Applying
Observation 3.4, for each point $A$ in $e_{i}$, the corners of $\triangle
Av_{j}v_{k}$ are stable if and only if $A$ lies in $\overline{X_{1}X_{2}}$.
Moreover, the areas of $\triangle Av_{j}v_{k}$ are all the same for any
$A\in\overline{X_{1}X_{2}}$, so these triangles constitute an equivalent
class. We call $\triangle X_{1}v_{j}v_{k}$ or $\triangle X_{2}v_{j}v_{k}$ (or
both) the representative(s) of this class.

Assume all the corners in $\triangle ABC$ lie in $\partial P$ and are stable
in this triangle. We state that $\triangle ABC$ is _generally 3-stable_ if:
the number of vertex-type corners in $\\{A,B,C\\}$ is not 2, or the number is
2 but $\triangle ABC$ is the representative in its equivalent class.

Note: The number of vertex-type corners in a generally 3-stable triangle may
be 0 to 3. See Figure 8 for examples. In addition, the 3-stable triangles must
be generally 3-stable; they are exactly those generally 3-stable triangles
with 3 vertex-type corners.

###  B.1. Basic observations of the generally 3-stable triangles

######  Observation B.2.

If some generally 3-stable triangle has its corners lying in unit
$u_{1},u_{2},u_{3}$, then $u_{1},u_{2},u_{3}$ are different to each other.
This essentially means that it cannot has two corners lying in the same edge
$e_{i}$. Moreover, it is also impossible that one corner lies in $e_{i}$ while
another lies in an endpoint of $e_{i}$. Otherwise the corner in $e_{i}$ cannot
be stable.

######  Observation B.3.

Assume $v_{i},e_{j},e_{k}$ are in clockwise order and there is a generally
3-stable triangle whose corners lie in $v_{i},e_{j},e_{k}$ respectively. Then
this triangle can be determined as follows. It must be $\triangle ABC$, where
$A=v_{i}$, $B$ is the unique point in $e_{j}$ such that $v_{i}B\parallel
e_{k}$, and $C$ is the unique point in $e_{k}$ such that $v_{i}C\parallel
e_{j}$. See Figure 8 (b). Trivial proof omitted.

######  Observation B.4.

Assume $e_{i},e_{j},e_{k}$ are in clockwise order and there is a generally
3-stable triangle whose corners lie in $e_{i},e_{j},e_{k}$ respectively. Then
this triangle can be determined as follows. Let $I_{1},I_{2},I_{3}$
respectively denote the intersection of $e_{i},e_{j}$, the intersection of
$e_{j},e_{k}$, and the intersection of $e_{k},e_{i}$. The triangle must be
$\triangle ABC$, where $A$ is the mid point of $I_{1},I_{3}$, $B$ is the mid
point of $I_{1},I_{2}$, and $C$ is the mid point of $I_{2},I_{3}$. See Figure
8 (c).

######  Proof B.5.

Since $A,B,C$ are stable, we get $AB\parallel e_{k},BC\parallel e_{i}$ and
$CA\parallel e_{j}$. So,
$|I_{3}A|:|AI_{1}|=|I_{2}B|:|BI_{1}|=|I_{2}C|:|CI_{3}|=|I_{1}A|:|AI_{3}|$.
Therefore, $|I_{1}A|=|AI_{3}|$, thus $A$ is the mid point of $I_{1},I_{3}$.
Symmetrically, $B,C$ are the mid points of $I_{1},I_{2}$ and $I_{2},I_{3}$.

######  Lemma B.6.

Any two generally 3-stable triangles in a convex polygon are interleaving.

Figure 9. Any two generally 3-stable triangles must be interleaving. The right
two pictures show some instances where the two triangles $\triangle
A_{1}B_{1}C_{1},\triangle A_{2}B_{2}C_{2}$ are interleaving.

######  Proof B.7.

Suppose $\triangle A_{1}B_{1}C_{1},\triangle A_{2}B_{2}C_{2}$ are generally
3-stable and they do not interleave. There are only four essentially different
cases: (as shown in Figure 9 (a),(b),(c),(d))

  1. Case a.

$A_{2}$ is between $A_{1}$ and $B_{1}$, meanwhile $B_{2},C_{2}$ are between
$B_{1}$ and $C_{1}$.
Since $C_{1}$ is stable in $\triangle A_{1}B_{1}C_{1}$, it has the largest
distance to $\overleftrightarrow{A_{1}B_{1}}$ among all points of $P$ on the
right of $\overrightarrow{A_{1}B_{1}}$. It implies $C_{1}>C_{2}$ in the
distance to $\overleftrightarrow{A_{2}B_{2}}$, by comparing the slope of
$A_{1}B_{1}$ and $A_{2}B_{2}$. Therefore, $C_{2}$ is not stable in $\triangle
A_{2}B_{2}C_{2}$, which is contradictory.

  2. Case b.

$A_{2}$ is between $A_{1}$ and $B_{1}$, meanwhile $B_{2}=B_{1}$, meanwhile
$C_{2}$ is between $B_{1}$ and $C_{1}$.
The proof of this case is the same as the proof of Case a.

  3. Case c.

$A_{2},C_{2}$ are between $A_{1}$ and $B_{1}$ meanwhile $B_{2}=B_{1}$.
Since $A_{1}$ is stable in $\triangle A_{1}B_{1}C_{1}$, it has the largest
distance to $\overleftrightarrow{B_{1}C_{1}}$ among all points of $P$ on the
right of $\overrightarrow{B_{1}C_{1}}$. It implies $A_{1}>C_{2}$ in the
distance to $\overleftrightarrow{A_{2}B_{2}}$, by comparing the slope of
$B_{1}C_{1}$ and $A_{2}B_{2}$. Therefore, $C_{2}$ is not stable in $\triangle
A_{2}B_{2}C_{2}$, which is contradictory.

  4. Case d.

$A_{2},B_{2},C_{2}$ are all between $A_{1}$ and $B_{1}$, meanwhile
$A_{1},C_{2},A_{2},B_{2},B_{1}$ lie in clockwise order.
The proof of this case is the same as the proof of Case c.

Note: here, the vertices between $A,B$ means the ones in set
$\\{A+1,\ldots,B-1\\}$.

###  B.2. The concept of G-dead and the conditions to determine G-dead

We say unit pair $(u_{1},u_{2})$ is _G-dead_ if there is no generally 3-stable
triangle $\triangle ABC$ such that $B\in u_{1}$ and $C\in u_{2}$. (To be
clear, recall that all edge of $P$ are endpoint-exclusive; if a corner lies in
an endpoint of unit $e_{i}$, we do not think that it lies in $e_{i}$.)

Note: G-dead is different from and stronger than dead for $(v_{j},v_{k})$. It
clearly implies dead but the reverse is false. For example, in Figure 8 (a),
$(v_{j},v_{k})$ is dead but not G-dead.

The unit pairs $(e_{j},e_{k}),(v_{j},e_{k}),(e_{j},v_{k}),(v_{j},v_{k})$ are
_illegal_ when $v_{k+1}$ is closer than $v_{k}$ in the distance to
$\overleftrightarrow{v_{j}v_{j+1}}$ (as shown in Figure 10), and are _legal_
otherwise. (See also Definition 3.6.)

Figure 10. illegal unit pairs.

Note: For each edge $e_{j}$ of $P$, the sequence of edge pairs
$(e_{j},e_{j+1}),(e_{j},e_{j+2}),\ldots,(e_{j},e_{j-1})$ starts with several
legal pairs and then is followed by several illegal pairs. In particular,
$(e_{j},e_{j+1})$ is legal and $(e_{j},e_{j-1})$ is illegal. (All subscripts
taken modulo $n$.)

######  Definition B.8.

For each edge pair $(e_{j},e_{k})$, we define $Q(e_{j},e_{k})$ as the
intersecting area of the following two strip regions. The first one is defined
by two lines parallel to $e_{k}$ which are at $v_{j},v_{j+1}$ respectively.
The second one is by two lines parallel to $e_{j}$ which are at
$v_{k},v_{k+1}$ respectively. See Figure 11. We regard that $Q(e_{j},e_{k})$
does not contain its boundaries.

Note: According to the definition, $Q(e_{j},e_{k})$ is empty when $e_{j}$ is
parallel to $e_{k}$.

Figure 11. Illustration of the definition of $Q(e_{j},e_{k})$.

Roughly, $Q(e_{j},e_{k})$ indicates the region of a corner of the generally
3-stable triangle when the other two corners are fixed in $e_{j},e_{k}$. This
is made clear in the following observation.

######  Observation B.9.

When $B,C$ are stable in $\triangle ABC$ and $B\in e_{j},C\in e_{k}$, then
$A\in Q(e_{j},e_{k})$.

######  Proof B.10.

Since $B$ is stable and lies in $e_{j}$, we know $AC\parallel e_{j}$. Since
$C$ is stable and lies in $e_{k}$, we know $AB\parallel e_{k}$. Together, it
follows that $A\in Q(e_{j},e_{k})$.

######  Observation B.11 (Sufficient conditions for determining that some edge
pair is G-dead).

  1. (1)

If $Q(e_{j},e_{k})$ does not intersect $P$, $(e_{j},e_{k})$ is G-dead.

  2. (2)

If an edge pair $(e_{j},e_{k})$ is illegal, it is G-dead.

  3. (3)

Assume that $J_{j,k}\neq\infty$ and that there exists some point $A$ in $P$
which lies on the right of $\overrightarrow{v_{j}v_{k}}$ such that $A\geq
J_{j,k}$ in the distance to $\overleftrightarrow{v_{j}v_{k}}$, then
$(e_{j},e_{k-1})$ is G-dead.

  4. (4)

If there exists some point $A$ in $P$ which lies on the right of
$\overrightarrow{v_{j}v_{k}}$ and is further than $K_{j,k}$ in the distance to
$\overleftrightarrow{v_{j}v_{k}}$, then we can determine that $(v_{j},v_{k})$
is G-dead.

Figure 12. Ill. of Observation B.11.3.

######  Proof B.12.

1\. This immediately follows from Observation B.9.

2\. Suppose to the opposite that $(e_{j},e_{k})$ is not G-dead. There exists a
generally 3-stable $\triangle ABC$ (where $A,B,C$ lie in clockwise order) such
that $B\in e_{j}$ and $C\in e_{k}$. Applying Observation B.9, $A\in
Q(e_{j},e_{k})\cap\partial P$. Further since $(e_{j},e_{k})$ is illegal (see
Figure 11 (b)), objects $A,e_{j},e_{k}$ (and so the points $A,B,C$) lie in
counterclockwise order in $\partial P$. Contradictory!

3\. We prove it by contradiction. Suppose to the opposite that it is not
G-dead but there exists a generally 3-stable $\triangle A^{*}BC$ such that
$B\in e_{j}$ and $C\in e_{k-1}$. We claim that $A>A^{*}$ in the distance to
$\overleftrightarrow{BC}$, and so $A^{*}$ is not stable in $\triangle
A^{*}BC$. See Figure 12. Make a parallel line of $\overline{BC}$ at $A^{*}$
and assume it intersects the extended lines of $e_{j},e_{k-1}$ at
$X_{A^{*}},Y_{A^{*}}$. Make a parallel line of $\overline{v_{j}v_{k}}$ at
$J_{j,k}$ and assume it intersects the two extended lines at $X_{J},Y_{J}$.
Assume the two extended lines intersect at $O$. The above claim simply follows
from the following arguments: (1) $A$ lies in the shadow area defined by
$\overline{X_{J}Y_{J}}$ and the extended lines of $e_{j},e_{k-1}$. (This is
because $A\geq J_{j,k}$.) (2) $|OX_{A^{*}}|<|OX_{J}|$ and
$|OY_{A^{*}}|<|OY_{J}|$. (This is because
$|OX_{A^{*}}|=2|OB|<2|Ov_{j}|=|OX_{J}|$ and
$|OY_{A^{*}}|=2|OC|<2|Ov_{k}|=|OY_{J}|$.)

4\. Recall Observation 3.7.3, where we show that $(v_{j},v_{k})$ is dead under
this assumption. In fact, the proof of Observation 3.7.3 can be easily adapted
to show the stronger result that $(v_{j},v_{k})$ is G-dead, because the proof
does not apply the fact that “$v_{i}$ is a vertex”.

###  B.3. Generalized Rotate-and-Kill process

Assume that $\triangle v_{r}v_{s}v_{t}$ is 3-stable and $r,s,t$ are computed.
Denote

$\mathcal{U}(r,s,t)=\\{(u_{1},u_{2})\mid
u_{1}\in\\{v_{s},e_{s},\ldots,e_{t-1},v_{t}\\}\text{ and
}u_{2}\in\\{v_{t},e_{t},\ldots,e_{r-1},v_{r}\\}\\}.$ (1)

In the next, a generalized Rotate-and-Kill process will be described which
visits some elements in $\mathcal{U}(r,s,t)$. Be aware that this process only
serves as a preprocessing step and we will design another specialized step for
computing the generally 3-stable triangles in the next subsection (which
applies the information processed here). On the contrary, these two steps are
not separated in the original Rotate-and-Kill process (see Algorithm 2).

Before describing this process, we first declare some properties it should
possess.

  * (/)

_Notice that the pairs in $\mathcal{U}(r,s,t)$ can be arranged into a two
dimensional table. The process proceeds in a way which corresponds to a
monotonic path from the top-left cell $(v_{s},v_{t})$ to the bottom-right cell
$(v_{t},v_{r})$ in the table. Hence only $O(n)$ elements are visited. _

  * (*)

_All the vertex pairs and edge pairs in $\mathcal{U}(r,s,t)$ which are not
G-dead will be visited_.

We present the generalized Rotate-and-Kill process right below; see Algorithm
3. The idea is similar to the original Rotate-and-Kill process. However, here
we will deal with a unit pair $(u_{1},u_{2})$ in each iteration, rather than a
vertex pair $(B,C)$.

The sentence $u++$ means an action that sets pointer $u$ to its clockwise next
unit.

The terminal endpoint ($\mathsf{TermEnd}$) of a unit is defined as:

$\mathsf{TermEnd}(e_{i}):=v_{i+1}\hbox{ and }\mathsf{TermEnd}(v_{i})=v_{i}.$

Input: $r,s,t$ such that $v_{r},v_{s},v_{t}$ is 3-stable.

1 $(u_{1},u_{2})\leftarrow(v_{s},v_{t})$; $A\leftarrow v_{r}$;

2 repeat

3 Let $v_{j}=\mathsf{TermEnd}(u_{1})$ (so $u_{1}=v_{j}$ or $u_{1}=e_{j-1}$);

4 Let $v_{k}=\mathsf{TermEnd}(u_{2})$ (so $u_{2}=v_{k}$ or $u_{2}=e_{k-1}$);

5 while  _$(A+1) >A$ in the distance to $\overleftrightarrow{v_{j}v_{k}}$_ do

6 $A\leftarrow A+1$;

7 end while

8 switch  _$(u_{1},u_{2})$_ do

9 case  _$(v_{j},v_{k})$_ do

10 $u_{1}++$ if $A\leq I_{j,k}$ in the distance to
$\overleftrightarrow{v_{j}v_{k}}$ and otherwise $u_{2}++$;

11 end case

12 case  _$(e_{j-1},e_{k-1})$_ do

13 $u_{1}++$ if $A\leq H_{j,k}$ in the distance to
$\overleftrightarrow{v_{j}v_{k}}$ and otherwise $u_{2}++$;

14 end case

15 case  _$(v_{j},e_{k-1})$_ do

16 $u_{1}++$ if $A<J_{j,k}$ in the distance to
$\overleftrightarrow{v_{j}v_{k}}$ and otherwise $u_{2}++$;

17 end case

18 case  _$(e_{j-1},v_{k})$_ do

19 $u_{1}++$ if $A\leq K_{j,k}$ in the distance to
$\overleftrightarrow{v_{j}v_{k}}$ and otherwise $u_{2}++$;

20 end case

21

22 end switch

23

24until  _$(u_{1},u_{2})=(v_{t},v_{r})$_ ;

Algorithm 3 The generalized Rotate-and-Kill process

Note. In the vertex-edge case “$(u_{1},u_{2})=(v_{j},e_{k-1})$” the condition
is “$<$”, whereas in the other three cases it is “$\leq$”. This is not a typo
although it looks like one for the readers.

Figure 13. Example of the generalized Rotate-and-Kill process.

Observing this algorithm, (/) holds because $u_{1},u_{2}$ move only in
clockwise order.

The following lemma immediately implies (*).

######  Lemma B.13.

Recall that all unit pairs in set $\mathcal{U}(r,s,t)$ can be arranged into a
two dimensional table in such a way that the rows from top to bottom
correspond to $v_{s},e_{s},\ldots,v_{t}$ while the columns from left to right
correspond to $v_{t},e_{t},\ldots,v_{r}$.

  1. (1)

In Algorithm 3, when $u_{1}$ is to be killed, the vertex pairs and edge pairs
on the right of the current row are all G-dead. When $u_{2}$ is to be killed,
the vertex pairs and edge pairs on the bottom of the current column are all
G-dead.

  2. (2)

Throughout the “repeat” statement, $(u_{1},u_{2})\in\mathcal{U}(r,s,t)$, and
$(u_{1},u_{2})\neq(v_{t},v_{t})$ and $(u_{1},u_{2})\neq(e_{t-1},v_{t})$.
Moreover, it terminates successfully at $(u_{1},u_{2})=(v_{t},v_{r})$.

Lemma B.13.2 can be proved the same as Lemma 3.9.3. We prove Lemma B.13.1
below.

######  Proof B.14 (Proof of Lemma B.13.1).

We should prove the following arguments.

  1. VV1.

When $(u_{1},u_{2})=(v_{j},v_{k})$ and $A\leq I_{j,k}$,
$(v_{j},v_{k^{\prime}})$ is G-dead for $k^{\prime}\in[k+1,r]$.

  2. VV2.

When $(u_{1},u_{2})=(v_{j},v_{k})$ and $A>I_{j,k}$, $(v_{j^{\prime}},v_{k})$
is G-dead for $j^{\prime}\in[j+1,t]$.

  3. EE1.

When $(u_{1},u_{2})=(e_{j-1},e_{k-1})$ and $A\leq H_{j,k}$,
$(e_{j-1},e_{k^{\prime}})$ is G-dead for $k^{\prime}\in[k,r-1]$.

  4. EE2.

When $(u_{1},u_{2})=(e_{j-1},e_{k-1})$ and $A>H_{j,k}$,
$(e_{j^{\prime}},e_{k-1})$ is G-dead for $j^{\prime}\in[j,t-1]$.

  5. VE1.

When $(u_{1},u_{2})=(v_{j},e_{k-1})$ and $A<J_{j,k}$, $(v_{j},v_{k^{\prime}})$
is G-dead for $k^{\prime}\in[k,r]$.

  6. VE2.

When $(u_{1},u_{2})=(v_{j},e_{k-1})$ and $A\geq J_{j,k}$,
$(e_{j^{\prime}},e_{k-1})$ is G-dead for $j^{\prime}\in[j,t-1]$.

  7. EV1.

When $(u_{1},u_{2})=(e_{j-1},v_{k})$ and $A\leq K_{j,k}$,
$(e_{j-1},e_{k^{\prime}})$ is G-dead for $k^{\prime}\in[k,r-1]$.

  8. EV2.

When $(u_{1},u_{2})=(e_{j-1},v_{k})$ and $A>K_{j,k}$, $(v_{j^{\prime}},v_{k})$
is G-dead for $j^{\prime}\in[j,t]$.

The proofs of Lemma 3.9.1 and 3.9.2 can be simply borrowed to prove VV1 and
VV2. (In the previous proof, we only claim some dead vertex pairs, yet it is
easy to see that they are also G-dead.) We now prove the other six arguments
by some similar techniques.

_Proof of EE1._ Assume $A\leq H_{j,k}$, we shall prove that
$(e_{j-1},e_{k^{\prime}})$ is G-dead for $k^{\prime}\in[k,r-1]$. Assume that
$(e_{j-1},e_{k-1})$ is legal and $e_{j-1}\nparallel e_{k-1}$. Otherwise
$(e_{j-1},e_{k}),\ldots,(e_{j-1},e_{r-1})$ are all illegal and thus G-dead
(due to Observation B.11.2). We argue that $(e_{j-1},e_{k})$ is G-dead even if
it is legal. See Figure 14 (a). Clearly, $Q(e_{j-1},e_{k})$ lies above the
line $l$ at $H_{j,k}$ that is parallel to $\overline{v_{j}v_{k}}$. However,
since $A\leq H_{j,k}$ (in the distance to $\overleftrightarrow{v_{j}v_{k}}$),
$P$ lies below line $l$. Therefore, $Q(e_{j-1},e_{k})$ does not intersect $P$.
Further applying Observation B.11.1, $(e_{j-1},e_{k})$ is G-dead. The same
argument holds for any pair $(e_{j-1},e_{k^{\prime}})$ where
$k^{\prime}\in[k,r-1]$, so EE1 holds.

_Proof of EE2._ Here $A>H_{j,k}$, so $H_{j,k}\neq\infty$. So
$(e_{j-1},e_{k-1})$ is legal and $e_{j-1}\nparallel e_{k-1}$. See Figure 14
(b). Since $A>H_{j,k}$, clearly $A\geq J_{j,k}$ in the distance to
$\overleftrightarrow{v_{j}v_{k}}$. Applying Observation B.11.3,
$(e_{j},e_{k-1})$ is G-dead. Moreover, since $A\geq J_{j,k}$ in the distance
to $\overleftrightarrow{v_{j}v_{k}}$, we can easily obtain that $A\geq
J_{j+1,k}$ in the distance to $\overleftrightarrow{v_{j+1}v_{k}}$. (The proof
is trivial and is simply illustrated in Figure 14 (c).) According to $A\geq
J_{j+1,k}$ and by using Observation B.11.3, $(e_{j+1},e_{k-1})$ is G-dead. By
induction, $(e_{j^{\prime}},e_{k-1})$ is G-dead for $j^{\prime}\in[j,t-1]$, so
EE2 holds.

_Proof of VE1._ Assume $A<J_{j,k}$, we shall prove that
$(v_{j},v_{k^{\prime}})$ is G-dead for $k^{\prime}\in[k,r]$. Assume
$(e_{j},e_{k-1})$ is legal and $e_{j}\nparallel e_{k-1}$. Otherwise,
$(v_{j},v_{k}),\ldots,(v_{j},v_{r})$ are all illegal and hence G-dead. We now
argue that $(v_{j},v_{k})$ is G-dead even if it is legal. See Figure 14 (d).
Let $l$ denote the parallel line of $\overline{v_{j}v_{k}}$ at $J_{j,k}$. It
separates $Q_{j,k}$ from $P$ because $A<J_{j,k}$. Therefore, $Q_{j,k}\cap
P=\varnothing$, which implies that $(v_{j},v_{k})$ is G-dead. Similarly, every
vertex pair $(v_{j},v_{k^{\prime}})$ where $k^{\prime}\in[k,r]$ is G-dead. So
VE1 holds.

Figure 14. Illustration of the proof of EE1, EE2, VE1, VE2, EV1, and EV2.

_Proof of VE2._ Here $A\geq J_{j,k}$, so $J_{j,k}\neq\infty$. So
$(e_{j},e_{k-1})$ is legal and $e_{j}\nparallel e_{k-1}$. See Figure 14 (e).
By the same inductive analysis as the EE2 case, $(e_{j^{\prime}},e_{k-1})$ is
G-dead for $j^{\prime}\in[j,t-1]$, i.e. VE2 holds.

_Proof of EV1, EV2._ Similarly as before, we can assume that $(e_{j-1},e_{k})$
is legal and $e_{j-1}\nparallel e_{k}$. When $A\leq K_{j,k}$, we can see
$(e_{j-1},e_{k})$ is G-dead because $Q(e_{j-1},e_{k})\cap P=\varnothing$
(because $Q(e_{j-1},e_{k})$ and $P$ are separated by the line $l$ at $K_{j,k}$
that is parallel to $\overline{v_{j}v_{k}}$). See Figure 14 (f). Moreover, for
the same reason, $(e_{j-1},e_{k^{\prime}})$ is G-dead for
$k^{\prime}\in[k,r-1]$, i.e. EV1 holds.

Next, assume that $A>K_{j,k}$. By Observation B.11.4, $(v_{j},v_{k})$ is
G-dead . We then claim that $(v_{j+1},v_{k})$ is also G-dead. This reduces to
prove that $A>K_{j+1,k}$ in the distance to
$\overleftrightarrow{v_{j+1}v_{k}}$, which follows from the fact that
$A>K_{j,k}$ in the distance to $\overleftrightarrow{v_{j}v_{k}}$ (see Figure
14 (f) for an illustration). By induction, $(v_{j^{\prime}},v_{k})$ is G-dead
for $j^{\prime}\in[j,t]$, i.e. EV2 holds.

###  B.4. Final step for computing all generally 3-stable triangles

######  Lemma B.15.

If $(u_{1},u_{2})$ is not G-dead, then it belongs to
$\mathcal{U}(r,s,t)\cup\mathcal{U}(s,t,r)\cup\mathcal{U}(t,r,s)$.

######  Proof B.16.

Let $[X\circlearrowright Y]$ indicates the portion of $\partial P$ starting
from $X$ and clockwise to $Y$.

Since $(u_{1},u_{2})$ is not G-dead, there exists a generally 3-stable
$\triangle ABC$ such that $B\in u_{1}$ and $C\in u_{2}$. Notice that
$\triangle v_{r}v_{s}v_{t}$ is 3-stable, and so generally 3-stable. By Lemma
B.6, $\triangle ABC$ interleaves $\triangle v_{r}v_{s}v_{t}$. Thus we have
three possibilities regarding the positions of $B,C$.
$B\in[v_{s}\circlearrowright v_{t}]$ and $C\in[v_{t}\circlearrowright v_{r}]$,
or $B\in[v_{t}\circlearrowright v_{r}]$ and $C\in[v_{r}\circlearrowright
v_{s}]$, or $B\in[v_{r}\circlearrowright v_{s}]$ and
$C\in[v_{s}\circlearrowright v_{t}]$. Correspondingly, $(u_{1},u_{2})$ belongs
to $\mathcal{U}(r,s,t)$, $\mathcal{U}(s,t,r)$, or $\mathcal{U}(t,r,s)$.

Before presenting the final step of our algorithm for computing the generally
3-stable triangles, we first introduce some key notations and state some
observations.

A unit pair is called _visited_ if it will be visited when we call Algorithm 3
with parameters $(r,s,t)$ or $(s,t,r)$ or $(t,r,s)$. The set of all such pairs
is denoted by $\mathsf{VisitPairs}$.

Denote by $A_{j,k}$ and $A^{*}_{j,k}$ the vertex with the largest distance to
$\overleftrightarrow{v_{j}v_{k}}$ on the right of
$\overrightarrow{v_{j}v_{k}}$. When two vertices have the same distance to
$\overleftrightarrow{v_{j}v_{k}}$, we choose the clockwise first one to be
$A_{j,k}$ and the next one to be $A^{*}_{j,k}$. (In most cases,
$A_{j,k}=A^{*}_{j,k}$.)

######  Observation B.17.

  1. (1)

We can compute $\mathsf{VisitPairs}$ in $O(n)$ time by calling the generalized
Rotate-and-Kill process three times with parameters $(r,s,t)$, $(s,t,r)$, and
$(t,r,s)$.

  2. (2)

A generally 3-stable triangle has two corners both lying on vertices or both
lying on edges.

  3. (3)

Consider edge pair $(e_{j},e_{k})\in\mathsf{VisitPairs}$. Assume that there is
a generally 3-stable $\triangle ABC$ such that $B\in e_{j},C\in e_{k}$. Then,
point $A$ lies in $[A_{j,k}\circlearrowright A^{*}_{j+1,k+1}]$.

  4. (4)

We can compute $A_{j,k}$ and $A^{*}_{j,k}$ for all vertex pairs
$(v_{j},v_{k})\in\mathsf{VisitPairs}$ in $O(n)$ time.

  5. (5)

We can compute $A_{j,k}$ and $A^{*}_{j+1,k+1}$ for all edge pairs
$(e_{j},e_{k})\in\mathsf{VisitPairs}$ in $O(n)$ time.

######  Proof B.18.

1 is according to (/) and Lemma B.15. 2 is trivial. 4 and 5 are because that
all visited unit pairs form a monotonic path in the table, as stated in (/).

We prove 3 by contradiction. Consider an opposite case where $A$ lies between
$v_{k+1}$ and $A_{j,k}$, as shown in Figure 15 (a). Another opposite case
where $A$ lies between $A^{*}_{j+1,k+1}$ and $v_{j}$ is symmetric. Note that
$A<A_{j,k}$ in the distance to $\overleftrightarrow{v_{j}v_{k}}$. By comparing
the slope of $\overline{v_{j}v_{k}}$ and $\overline{BC}$, we have $A<A_{j,k}$
in the distance to $\overleftrightarrow{BC}$, thus $A$ is not stable in
$\triangle ABC$.

Figure 15. (a) is an illustration of the proof of Observation B.17.3. (b)
draws an example to illustrate that Algorithm 4 could cost $\Omega(n^{2})$
time. In this example, $(e_{j},e_{k}),\ldots,(e_{j},e_{k^{\prime}})$ are
$\Omega(n)$ visited edge pairs. In addition,
$A_{j,k}=\ldots=A_{j,k^{\prime}}=v_{i}$ and
$A^{*}_{j+1,k+1}=\ldots=A^{*}_{j+1,k^{\prime}+1}=v_{i^{\prime}}$, and that
there are $\Omega(n)$ units in $[v_{i}\circlearrowright v_{i^{\prime}}]$. (c)
illustrates the batch technique discussed below.

We give the pseudo code of the final step in Algorithm 4. Note that the gadget
named $FindGenarlly3stable(u_{1},u_{2},u_{3})$ computes the generally 3-stable
triangle $\triangle ABC$ such that $A\in u_{1},B\in u_{2}$ and $C\in u_{3}$.
This gadget only takes $O(1)$ time: if there are at least two edges in
$u_{1},u_{2},u_{3}$, we can apply Observation B.3 and B.4. Otherwise it is
more trivial.

1 foreach  _vertex pair $(v_{j},v_{k})$ in $\mathsf{VisitPairs}$_ do

2 foreach  _unit $u$ in $[A_{j,k}\circlearrowright A^{*}_{j,k}]$_ do

3 $FindGenarlly3stable(u,v_{j},v_{k})$;

4 end foreach

5

6 end foreach

7foreach  _edge pair $(e_{j},e_{k})$ in $\mathsf{VisitPairs}$_ do

8 foreach  _unit $u$ in $[A_{j,k}\circlearrowright A^{*}_{j+1,k+1}]$_ do

9 $FindGenarlly3stable(u,e_{j},e_{k})$;

10 end foreach

11

12 end foreach

Algorithm 4 Compute generally 3-stable triangles

Let $\mathsf{AlivePairs}$ denote all vertex pairs and edge pairs that are not
G-dead. We know $\mathsf{AlivePairs}\subseteq\mathsf{VisitPairs}$ according to
(*). This further implies the correctness of Algorithm 4.

Algorithm 4 runs in $\Omega(n^{2})$ time in the worst case. An example is
given and analyzed in Figure 15 (b). In this example,
$(e_{j},e_{k}),\ldots,(e_{j},e_{k^{\prime}})$ are $\Omega(n)$ visited edge
pairs. In addition, $A_{j,k}=\ldots=A_{j,k^{\prime}}=v_{i}$ and
$A^{*}_{j+1,k+1}=\ldots=A^{*}_{j+1,k^{\prime}+1}=v_{i^{\prime}}$, and that
there are $\Omega(n)$ units in $[v_{i}\circlearrowright v_{i^{\prime}}]$.
Fortunately, we can optimize it to linear time by the following technique.

##### The batch technique.

An idea to optimize the algorithm is to restrict the enumerating units $(u)$
for $(e_{j},e_{k})$ and handle those enumerations for
$(e_{j},e_{k}),\ldots,(e_{j},e_{k^{\prime}})$ in a batch. To be more specific,
make parallel lines of $e_{j}$ at the endpoints of $e_{k}$. This defines a
stripe region (denoted by $S_{k}$) where $u$ must intersect so that
$(u,e_{j},e_{k})$ may accommodates a generally 3-stable triple (due to
Observation B.9). Notice that these stripe regions
$S_{k},\ldots,S_{k^{\prime}}$ do not overlap, therefore, by handling
$(e_{j},e_{k}),\ldots,(e_{j},e_{k^{\prime}})$ together, we can enumerate the
associated units for all of them in
$O(k^{\prime}-k+|A^{*}_{j+1,k^{\prime}+1}-A_{j,k}|+1)$ time, where
$|A^{*}_{j+1,k^{\prime}+1}-A_{j,k}|$ denotes the number of vertices in
$[A_{j,k}\circlearrowright A^{*}_{j+1,k^{\prime}+1}]$. Similarly, we handle
the visited edge pairs in a column (for example,
$(e_{j},e_{k}),\ldots,(e_{j^{\prime}},e_{k})$) in a batch, in
$O(j^{\prime}-j+|A^{*}_{j^{\prime}+1,k+1}-A_{j,k}|+1)$ time. The entire batch
method is illustrated in Figure 16.

Figure 16. Running time of handling edge pairs is
$O(\Sigma(|A_{i}-A_{i-1}|+1)+\Sigma(|A^{\prime}_{i}-A^{\prime}_{i-1}|+1)=O(n)$.

######  Theorem B.19.

The running time of the optimized Algorithm 4 is $O(n)$. Moreover, our entire
algorithm for computing all generally 3-stable triangles runs in $O(n)$ time.

###  B.5. Compute the smallest triangle enclosing $P$

In this subsection, we assume $T=\triangle abc$ is a local minimum among
triangles enclosing $P$.

Denote the midpoint of the three sides of $T$ (i.e., $ab,bc,ca$) by $C,A,B$.
We know that $A,B,C$ lies in $\partial P$ according to the following lemma (it
is rediscovered in many places).

######  Lemma B.20.

[19] The midpoint of each side of $T$ touches $P$.

Moreover, $A,B,C$ are clearly stable in $\triangle ABC$. Therefore, $\triangle
ABC$ is (roughly) generally 3-stable. (Note: in degenerate cases as shown in
Figure 8 (a), $ABC$ itself may not be generally 3-stable, but there is a
generally 3-stable triangle equivalent to $\triangle ABC$.)

It is easy to compute $a,b,c$ in $O(1)$ time from $A,B,C$. So finding the
local minimums among triangles enclosing $P$ reduces to computing the
generally 3-stable triangles in $P$.

######  Theorem B.21.

We can compute all local minimums of $P$’s enclosing triangles in $O(n)$ time.