Incremental Algorithm and Local Search for Minimum Non-Obtuse Triangulations

We introduce our incremental algorithm. It was mostly used for instances of type ortho. For a type ortho instance $I=(V,R,E)$, $R$ is an orthogonal polygon (any edge is vertical or horizontal), $V$ is the vertex set of $R$, and $E=\mathrm{\varnothing }$. Define $x(p)$ and $y(p)$ as the $x$- and $y$-coordinate of a point $p\in {ℝ}^2$, respectively. Let $X=\{x(p)\mid p\in V\}$ and $Y=\{y(p)\mid p\in V\}$, and let $S_G=\{p\in R\mid x(p)\in X,y(p)\in Y\}$ be the grid points of $I$. The set $S_G\setminus V$ is an obvious feasible solution of $I$. However, its size can be $\mathrm{\Omega }({|V|}^2)$. In the following, we show how to find a moderately-sized feasible solution $S\subset S_G$.

Starting with $S=\mathrm{\varnothing }$, we compute $\text{DT}(V\cup S,R,E)$ in each step. If it is non-obtuse, $S$ is a feasible solution, and we are done. Otherwise, we pick a random obtuse triangle in $\text{DT}(V\cup S,R,E)$. Let $p$ be its obtuse vertex. The angle interval defined by $p$ contains at least one of the four axis-aligned directions from $p$: $+x$, $+y$, $-x$ and $-y$. Without loss of generality, assume that it contains the $+y$-direction as in Figure 2, and let $\overrightarrow{r}$ be the ray emanating from $p$ and going towards the $+y$-direction. Let $q$ be a point moving from $p$ along $\overrightarrow{r}$. During the movement of $q$, if $y(q)=y(v)$ for a vertex $v$ of the triangle containing $q$ and $q\ne p$, it stops, and we add $q$ to $S$. It is easy to see that $q$ always stops before moving out of $R$. We repeat the procedure until $S$ becomes feasible.

Table 1 shows that the above algorithm uses no more Steiner points than the size of $V$, for type ortho instances.

We can apply the algorithm to some instances of type point-set and simple-polygon by invoking MakeNonObtuseBoundary procedure whenever we add a new Steiner point. MakeNonObtuseBoundary finds an obtuse triangle from $\text{DT}(V\cup S,R,E)$ having its hypotenuse on the boundary of $R$, and adds the projection from the opposite vertex onto the hypotenuse to $S$. It repeats until there is no such obtuse triangle. See Figure 3.

We introduce our local search algorithm. Starting from $S:=\mathrm{\varnothing }$, the algorithm runs insertion steps and deletion steps alternatingly to update $S$.

Unlike the incremental algorithm in Section 2.1, our local search algorithm may place non-grid Steiner points in the insertion step. We first observe the following. Let $I=(V,R,E)$ be an instance. Consider a feasible solution $S$ of $I$. Fix a point $s\in S$, and let $T(s)$ be the set of triangles in $\text{DT}(V\cup S,R,E)$ with $s$ as a vertex. Since all triangles in $T(s)$ are non-obtuse, their union is a convex polygon $P$. The interior of $P$ does not contain any constraint edge if and only if $s$ does not lie on any constraint edge. See Figure 4(a, b). If $s$ lies on some $e\in E$, then $P\cap e$ is an edge connecting two vertices of $P$, and $P$ does not contain any other constraint edge. See Figure 4(c). Based on the observation, we consider the following.

Fix an edge $\overline{pq}$ of $P$ and consider the triangle $\mathrm{△}spq$ for a point $s\in P$. We have $\mathrm{\angle }spq\le \pi /2$ and $\mathrm{\angle }sqp\le \pi /2$ if and only if $s$ lies in the strip $L$ perpendicular to $\overline{pq}$, with each bounding line going through $p$ and $q$, respectively. We have $\mathrm{\angle }psq\le \pi /2$ if and only if $s$ lies outside the disk $D$ having $\overline{pq}$ as its diameter. See Figure 5(a). Summing up, $\mathrm{△}spq$ is non-obtuse if and only if $s$ lies in $ℛ(\overline{pq}):=L\setminus D$, and $s\in P$ is a solution of Problem 2 if and only if it lies in the intersection of $ℛ(\overline{pq})$’s for every edge $\overline{pq}$ of $P$. See Figure 5(b). A similar subprocedure was previously introduced by Erten and Üngör [8], and it was also used in the team Naughty NOTers’ approach [1], named as polygonCenter. If a diagonal $e$ is given additionally as in the problem statement, we check if such intersection of $ℛ(\overline{pq})$’s intersects $e$. We solve its generalized version, Problem 3, defined as follows, because there may be no solution for Problem 2. Let $V_P$ be the set of vertices of $P$, and let $E_P≔\{e\cap P\mid e\in E\}$.

To solve Problem 3, we need to define the following sets.

• $\mathrm{■}$

  $𝒟$: the set of circles, each having an edge of $P$ as its diameter.

• $\mathrm{■}$

  $ℒ$: the set of lines, each perpendicular to an edge of $P$ and going through one of its endpoints.

• $\mathrm{■}$

  $𝒞$: the set of circumcircles of the triangles in $\text{DT}(V_P,P,E_P)$.

Consider the arrangement $𝒜$ of $𝒟\cup ℒ\cup 𝒞\cup E_P$ in $P$. For each cell of $𝒜$, the number of obtuse triangles is the same. Thus we aim to find a vertex $v$ of $𝒜$ minimizing the number of obtuse triangles in $\text{DT}(V_P\cup \{v\},P,E_P)$.

Since we are using exact arithmetic, it consumes too much time and space to exactly compute vertices of $𝒜$. So instead, we approximate each point with another point at close range with simpler coordinates. For each vertex of $𝒜$ that does not lie on any constraint edge, we approximate both its $x$- and $y$-coordinate using quantized values represented as $i\cdot q$ for some integer $i$ and a fixed parameter $q\in \mathbb{Q}$. For each vertex of $𝒜$ lying on a constraint edge, we approximate only one of its coordinates with the quantized values, to ensure that the approximated point also lies on the constraint edge. We start with $q=1$ and make it smaller whenever the algorithm gets stuck. From the approximated points, we choose one minimizing the number of obtuse triangles. If there are multiple such points, we choose a point at random. Let AddPoint($P$) be the corresponding subprocedure.

In the insertion step, we first compute $\text{DT}(V\cup S,R,E)$. If it is non-obtuse, we are done. Otherwise, we pick an obtuse triangle $t$ in $\text{DT}(V\cup S,R,E)$ at random. Then we compute a maximal convex polygon $P$ which is the union of some triangles in $\text{DT}(V\cup S,R,E)$ containing $t$. This is done by maintaining a convex polygon $P$, starting from $P=t$ and adding triangles incident to $P$ until there is no triangle $t^{\prime }$ such that $P\cup t^{\prime }$ is convex. Finally, we add a point to $S$ obtained from AddPoint($P$). During each insertion step, we repeat the above several times.

In the deletion step, we randomly choose a Steiner point $p$, and remove every Steiner point (including $p$ itself) within distance $r\cdot d$ where $r$ is a parameter that increases as time goes by, and $d$ is the distance between $p$ and its closest Steiner point.

We store the current solution as the best solution whenever the number of obtuse triangles decreases, or the number of Steiner points decreases while the number of obtuse triangles remains the same. In each iteration, we start from the best solution and apply the insertion and the deletion steps alternatingly. Figure 6(a) illustrates a deletion step, and Figure 6(b) illustrates a non-obtuse solution obtained by running an insertion step afterwards.