NLP Formulation for Polygon Optimization Problems

Abstract

In this paper, we generalize the problems of finding simple polygons with minimum area, maximum perimeter, and maximum number of vertices, so that they contain a given set of points and their angles are bounded by $\alpha +\pi$ where $\alpha$ ($0\le \alpha \le \pi$) is a parameter. We also consider the maximum angle of each possible simple polygon crossing a given set of points, and derive an upper bound for the minimum of these angles. The correspondence between the problems of finding simple polygons with minimum area and maximum number of vertices is investigated from a theoretical perspective. We formulate these three generalized problems as nonlinear programming models, and then present a genetic algorithm to solve them. Finally, the computed solutions are evaluated on several datasets and the results are compared with those from the optimal approach.

1. Introduction

Polygons are one of the fundamental objects in the field of computational geometry. Simple polygonization is a way to construct all possible simple polygons on a set of points in the plane. Global optimization problems, such as optimal area and perimeter polygonization [1,2], are of major interest to researchers and arise in various application areas, such as image processing [3,4], pattern recognition [3,5,6], geographic information systems (GIS) [7], sensor networks [8,9], and so on.

Minimum- and maximum-perimeter polygonization problems are known as the traveling salesman problem (TSP) and the maximum traveling salesman problem (Max-TSP), respectively, which are NP-complete problems [1,10]. Fekete considered a set of points on the grid and showed that the problems of minimum area polygonization (MAP) and maximum area polygonization (MAXP) on that set of points are NP-complete [2]. Recently, it has been shown that computing an $\alpha$-concave hull (as a generalization of MAP) is still NP-hard [11].

To the best of our knowledge, little attention has been paid to the constraint on the internal angles of polygons in previous studies [12,13,14]. In this paper, we explore the optimum polygonization such that the internal angles of the polygons are bounded. Here, we define $\alpha$-MAP, $\alpha$-MPP, and $\alpha$-MNP as the problems of computing simple polygons containing a set of points in the plane with minimum area, maximum perimeter, and maximum number of vertex points, respectively, such that all internal angles of the polygons are less than or equal to $\pi +\alpha$. We consider $\alpha$-MAP, $\alpha$-MPP and $\alpha$-MNP as generalizations of computing the convex hull, and formulate them as nonlinear programming models.

For a set S of points in the plane and for $k\ge 2$, an algorithm for finding k convex polygons that covers S is presented in [15], such that the total area of the convex polygons is minimized. Also, for $k=2$, another algorithm is presented, to minimize the total perimeter of the convex polygons.

There are many NP-complete problems such as TSP [16], packing problems [17], convex shape decomposition [18], and the path planning problem [19] that can be formulated as integer programming problems. In [20], a nonlinear programming model is presented for the problem of cutting circles from rectangles with minimum area. In [21], the rectangular cartogram problem is formulated as a bilinear program. Raimund Seidel constructs convex hulls of n points in $R^d$ for $d>3$, using a linear programming algorithm [22].

There have been many studies on approximation and randomized algorithms for MAP [11,23,24], MAXP [23], TSP [25,26], and Max-TSP [27,28]. Here, we apply a genetic algorithm (GA) to solve $\alpha$-MAP, $\alpha$-MPP, and $\alpha$-MNP, and then compare the results with those from the optimal approach. A genetic algorithm is used to solve many problems such as TSP [29,30,31], packing of polygons [32], path planning [33,34], and pattern recognition [35].

$\chi$-shape [36], $\alpha$-shape [37], concave hull [7], simple-shape [38], RGG [39], and crust [40] are all bounding hulls of a set of points, same as the convex hull. $\alpha$-shape and concave hull are generalizations of the convex hull to cover a set of points, and can be used in the fields of space decomposition [41], sensor networks [42], bioinformatics [43], feature detection [44], GIS [45], dataset classification [46], shape reconstruction [47,48], and so on. We implement the concave hull algorithm [49], and then use the computed results to compare against those obtained from the GA.

The rest of the paper is as follows: In Section 2, we present some notation and definitions which are required throughout the paper. In Section 3, we first formulate the required functions and then introduce nonlinear programming models for $\alpha$-MAP, $\alpha$-MPP, and $\alpha$-MNP. In Section 4, our theoretical results are discussed. For a set S of points, an upper bound for $\theta$ is obtained, such that $\theta$ is the minimum of maximum angles of each simple polygon containing S. Also, the similarity of the two problems $\alpha$-MAP and $\alpha$-MNP is investigated on the grid points. Section 5 is devoted to a full evaluation of our experimental results obtained by implementing the GA and the brute-force algorithm. Section 6 concludes the paper, highlighting its main contribution.

2. Preliminaries

Let $S=\{s_1,s_2,\dots ,s_n\}$ be a set of points in the plane, and $CH$ be the convex hull of S. The vertices and edges of $CH$ are denoted by $V_{CH}=\{c_1,c_2,\dots ,c_m\}$ and $E_{CH}=\{e_1,e_2,\dots ,e_m\}$, respectively. Furthermore, let $IP=\{a_1,a_2,\dots ,a_r\}$ be the inner points of $CH$, such that $r=n-m$. A polygon P containing S is specified by a closed chain of vertices $P=(p_1,p_2,\dots ,p_l,p_1)$.

Table 1. Notations of symbols.

Notation	Description
S	A set of points in the plane
n	cardinality of S
$s_i$	ith point of S ($1\le i\le n$)
$CH$	convex hull of S
m	number of vertices of $CH$
$IP$	inner points of $CH$
P	a simple polygon containing S
$V_P$	vertices of P
$E_P$	edges of P
r	cardinality of $IP$
$c_j$	jth vertex of $CH$ ($1\le j\le m$)
$e_j$	jth edge of $CH$ ($1\le j\le m$)
P	a simple Polygon containing S
$\overline{s_i{s}_j}$	an edge of P with $s_i$ and $s_j$ as its end points ($1\le i,j\le n$, $i\ne j$)
$\wp \left(S\right)$	set of all simple polygons containing S
$Area\left(P\right)$	area of polygon P
$Perimeter\left(P\right)$	perimeter of polygon P
$Boundary\left(P\right)$	number of vertices of P
$\alpha$	an angle between 0 and $\pi$
MAP	problem of computing a simple polygon containing S with minimum area
MPP	problem of computing a simple polygon containing S with maximum perimeter
MNP	problem of computing a simple polygon containing S with maximum number of vertices
CHP	problem of computing convex hull of S
SPP	problem of computing a simple polygon crossing S
$\stackrel{⌢}{AB}$	the measure of arc $AB$

shows more notation that is used in the rest of the paper. The simple polygon P contains S iff $V_P\subseteq S$ and $\forall i\in \{1,2,\dots ,n\}$, $s_i\in P$. Moreover, P crosses a point x iff $x\in V_P$.

MAP is the problem of computing the simple polygon $M\in \wp \left(S\right)$, such that $\forall P\in \wp \left(S\right),Area\left(M\right)\le Area\left(P\right)$; MPP is the problem of computing the simple polygon $E\in \wp \left(S\right)$, such that $\forall P\in \wp \left(S\right),Perimeter\left(E\right)\ge Perimeter\left(P\right)$; and MNP is the problem of computing the simple polygon $C\in \wp \left(S\right)$, such that $\forall P\in \wp \left(S\right),Boundary\left(C\right)\ge Boundary\left(P\right)$. The following definitions introduce the problems of computing $\alpha$-MAP, $\alpha$-MPP, and $\alpha$-MNP.

Definition 1.

For $0\le \alpha \le \pi$, a simple polygon $P\in \wp \left(S\right)$ is an α-polygon if all internal angles of P are less than or equal to $\pi +\alpha$ [11].

Definition 2.

α-MAP, α-MPP and α-MNP are the problems of computing the α-polygon containing S with minimum area, maximum perimeter and maximum number of vertices, respectively.

In the case of $\alpha =\pi$, the $\alpha$-polygon, $\alpha$-MAP, $\alpha$-MPP, and $\alpha$-MNP will be converted into the simple polygon, MAP, MPP, and MNP, respectively. Also, in the case of $\alpha =0$, the $\alpha$-polygon will be converted into the convex polygon, and all of the $\alpha$-MAP, $\alpha$-MPP, and $\alpha$-MNP will be converted into CHP. We formulate these as binary nonlinear programming models:

Definition 3.

Let $\{c_1,c_2,\dots ,c_m\}$ be the vertices of $CH$, $e_j=\overline{c_j{c}_{j+1}}$ be the jth edge of $CH$ and P be a simple polygon containing S. The points $\{b_{1,j},b_{2,j},\dots ,b_{t,j}\}\in S$ are assigned to the edge $e_j$ if $(c_j,b_{1,j},b_{2,j},\dots ,b_{t,j},c_{j+1})$ is a chain in P.

Figure 1 shows that the polygon P assigns the points $\{b_{1,1},b_{2,1},b_{3,1}\}$ to the edge $e_1$, the point $\left\{b_{1,2}\right\}$ to the edge $e_2$, and so on. The inner points of P are unassigned. We assume that $c_j$ is assigned to $e_j$.

3. Modeling

In this section we present nonlinear programming models for $\alpha$-MAP, $\alpha$-MPP, and $\alpha$-MNP. We first introduce the indices, input data, and variables that are used in our models, and then formulate the required functions.

3.1. Indices

The following indices are utilized to formulate the problems $\alpha$-MAP, $\alpha$-MPP, and $\alpha$-MNP as binary nonlinear programming models:

• $i\in \{1,2,\dots ,n\}$ is an index counting the points of S. The point $s_{n+1}$ is identified by $s_1$, and the point $s_{n+2}$ is identified by $s_2$.
• $j\in \{1,2,\dots ,m\}$ is an index counting the edges in $E_{CH}$ and the vertices in $V_{CH}$. The edge $e_{m+1}$ is identified by $e_1$, and the vertex $c_{m+1}$ is identified by $c_1$.
• $k\in \{0,1,\dots ,r\}$ specifies the order of assigned points for an edge of convex hull. $b_{k,j}$ is the kth point which is assigned to $e_j$. Assume that $c_i$ is assigned to $e_i$ at the position 0.

3.2. Input Data

The input data is as follows:

• n is the number of points in S.
• $(x_i,y_i)\in {\mathbb{R}}^2$ is the coordinate of the point $s_i$.
• $\alpha \in [0,\pi ]$ is the constraint for angles.

3.3. Assumptions

• $x^{\left(j\right)}$ is the x-coordinate of $c_j$.
• $y^{\left(j\right)}$ is the y-coordinate of $c_j$.

3.4. Variables

In this model, we have $n\times m\times r$ variables, denoted by z, which is defined as follows: $Z_{i,j,k}$ is a binary variable such that $Z_{i,j,k}=1$ iff the point $s_i$ is assigned to $e_j$ at the position of k. In Figure 1, Assume that $b_{3,1}$ is the tenth point of S. Since $b_{3,1}$ is assigned to $e_1$ at the position of 3, we have $Z_{10,1,3}=1$.

3.5. Functions

The functions used in this model are listed below.

• $Area\left(P\right)$ is the area of the polygon P.
• $Perimeter\left(P\right)$ is the perimeter of the polygon P.
• $Boundary\left(P\right)$ is the number of vertices of the polygon P.
• $X\left(a\right)$ is the x-coordinate of the point a in the plane.
• $Y\left(a\right)$ is the y-coordinate of the point a in the plane.
• $X(j,k)$ is the x-coordinate of the kth points that is assigned to $e_j$.

  $$X(j,k)={\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k}·x_i$$

  (1)
• $Y(j,k)$ is the y-coordinate of the kth points that is assigned to $e_j$.

  $$Y(j,k)={\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k}·y_i$$

  (2)
• $Adjust(i_1,i_2)$: if $\exists e\in E_P$ such that $s_{i_1}$ and $s_{i_2}$ are endpoints of e, then $Adjust(i_1,i_2)=1$, otherwise, $Adjust(i_1,i_2)=0$.
• $Conflict(i_1,i_2,i_3,i_4)$: if two edges $\overline{s_{i_1}{s}_{i_2}}$ and $\overline{s_{i_3}{s}_{i_4}}$ cross each other, then $Conflict(i_1,i_2,i_3,i_4)=1$, otherwise, $Conflict(i_1,i_2,i_3,i_4)=0$.
• $Angle(i_1,i_2,i_3)$ is the clockwise angle between $\overline{s_{i_1}{s}_{i_2}}$ and $\overline{s_{i_2}{s}_{i_3}}$.

Figure 2 is an example of a polygon P containing the set $S=\{s_1,s_2,\dots ,s_{19}\}$. In this example, the points $\{s_5,s_6,s_{10}\}$ are assigned to $e_1$. Hence, we have $Z_{5,1,1}=Z_{6,1,2}=Z_{10,1,3}=1$. Also, since $s_1$ is assigned to $e_1$ at the position 0, $Z_{1,1,0}=1$. In the same way, for the other edges of $CH$, we have: $Z_{11,2,0}=Z_{15,2,1}=1$, $Z_{19,3,0}=1$, $Z_{18,4,0}=Z_{17,4,1}=Z_{16,4,2}=Z_{13,4,3}=1$, $Z_{12,5,0}=Z_{7,5,1}=1,Z_{2,6,0}=Z_{3,6,1}=Z_{4,6,2}=1$. In Figure 2, to compute $X(j,k)$ for $j=4$ and $k=2$ we have:

$$X(4,2)={\mathsf{\Sigma }}_{i=1}^{19}{Z}_{i,4,2}·x_i=0+\dots +0+x_{16}+0+0+0=x_{16}.$$

3.6. Models

Here, we present the nonlinear programming formulations for $\alpha$-MAP, $\alpha$-MPP, and $\alpha$-MNP. We first formulate the functions $Adjust$, $Conflict$ and $Angle$ as follows: The $Adjust$ function is used to determine if two points are adjacent to each other in the polygon, the $Conflict$ function is used to check if the polygon is simple and the $Angle$ function is used to compute the angle between two edges to verify the angular constraint.

Adjust function

The Adjust function is computed as follows:

$$Adjust(i_1,i_2)=\left\{\begin{array}{ccc}1\hfill & \exists k\in \{0,\dots ,r-1\},\exists j\in \{1,\dots ,m\}\mid \hfill & Z_{i_1,j,k}=Z_{i_2,j,k+1}=1\hfill \\ 1\hfill & \exists k\in \{0,\dots ,r-1\},\exists j\in \{1,\dots ,m\}\mid \hfill & Z_{i_2,j,k}=Z_{i_1,j,k+1}=1\hfill \\ 1\hfill & \exists k\in \{1,\dots ,r\},\exists j\in \{1,\dots ,m\}\mid \hfill & Z_{i_1,j,k}=Z_{i_2,j+1,0}=1,\hfill \\ & & \forall i\in \{1,\dots ,n\}{Z}_{i,j,k+1}=0\hfill \\ 1\hfill & \exists k\in \{1,\dots ,r\},\exists j\in \{1,\dots ,m\}\mid \hfill & Z_{i_2,j,k}=Z_{i_1,j+1,0}=1,\hfill \\ & & \forall i\in \{1,\dots ,n\}{Z}_{i,j,k+1}=0\hfill \\ 0\hfill & \mathrm{otherwise}\hfill & \end{array}\right.$$

(3)

As seen in Figure 2, $s_6$ is adjusted to $s_{10}$. Since $Z_{6,1,2}=Z_{10,1,3}=1$, we have $Adjust(6,10)=1$. Also, since $Z_{10,1,3}=Z_{11,2,0}=1$ and $\forall i\in \{1,\dots ,n\}{Z}_{i,1,4}=0$, we have $Adjust(10,11)=1$.

Conflict function

To compute the conflict function, consider the following expression:

$$\begin{array}{ccc}{E}_{i_1,i_2}\hfill & =\hfill & (X\left(s_{i_2}\right)-X\left(s_{i_1}\right),Y\left(s_{i_2}\right)-Y\left(s_{i_1}\right))\hfill \\ R_{i_1,i_2}\hfill & =\hfill & (-Y\left(E_{i_1,i_2}\right),X\left(E_{i_1,i_2}\right))\hfill \\ h(i_1,i_2,i_3,i_4)\hfill & =\hfill & (E_{i_3,i_1}.R_{i_1,i_2})/(E_{i_3,i_4}.R_{i_1,i_2})\hfill \\ & =\hfill & \frac{(X\left(E_{i_3,i_1}\right)·X\left(R_{i_1,i_2}\right)+Y\left(E_{i_3,i_1}\right)·Y\left(R_{i_1,i_2}\right))}{(X\left(E_{i_3,i_4}\right)·X\left(R_{i_1,i_2}\right)+Y\left(E_{i_3,i_4}\right)·Y\left(R_{i_1,i_2}\right))}.\hfill \end{array}$$

(4)

So, the function $Conflict(i_1,i_2,i_3,i_4)$ is computed as follows:

$$Conflict(i_1,i_2,i_3,i_4)=\left\{\begin{array}{ccc}& 0\le h(i_1,i_2,i_3,i_4)\le 1\hfill & and\hfill \\ 1\hfill & Adjust(i_1,i_2)=Adjust(i_3,i_4)=1\hfill & and\hfill \\ & Adjust(i_1,i_3)=Adjust(i_2,i_4)=0\hfill & \\ 0\hfill & \mathrm{otherwise}\hfill & \end{array}\right.$$

(5)

Based on the mentioned notation, P is simple if $\forall i_1,i_2,i_3,i_4\in \{1,2,\dots ,n\}$, such that $i_1\ne i_2\ne i_3\ne i_4$, $Adjust(i_1,i_2)=Adjust(i_3,i_4)=1$, and $Adjust(i_1,i_3)=Adjust(i_2,i_4)=0$, we have $Conflict(i_1,i_2,i_3,i_4)=0$.

Angle function

The polygon P is an $\alpha$-polygon iff $\forall i_1,i_2,i_3\in \{1,2,\dots ,n\}$ such that $i_1\ne i_2\ne i_3$, $Adjust(i_1,i_2)=Adjust(i_2,i_3)=1$ and $Adjust(i_1,i_3)=0$, we have $Angle(i_1,i_2,i_3)\le \pi +\alpha$. The angle between two line segments A and B can be computed as follows:

$$\theta =\arccos \frac{A.B}{\left(\right|A|·|B\left|\right)}.$$

(6)

Based on the mentioned notation, let

$$\begin{array}{c}{A}_{i_1,i_2}=(X\left(s_{i_2}\right)-X\left(s_{i_1}\right),Y\left(s_{i_2}\right)-Y\left(s_{i_1}\right)),\hfill \\ B_{i_2,i_3}=(X\left(s_{i_3}\right)-X\left(s_{i_2}\right),Y\left(s_{i_3}\right)-Y\left(s_{i_2}\right)).\hfill \end{array}$$

(7)

If $Adjust(i_1,i_2)=Adjust(i_2,i_3)=1$ and $Adjust(i_1,i_3)=0$, $Angle(i_1,i_2,i_3)$ is computed as follows, otherwise $Angle(i_1,i_2,i_3)=0$.

$$Angle(i_1,i_2,i_3)=\arccos \frac{X\left(A_{i_1,i_2}\right)·X\left(B_{i_2,i_3}\right)+Y\left(A_{i_1,i_2}\right)·Y\left(B_{i_2,i_3}\right)}{\sqrt{X{\left(A_{i_1,i_2}\right)}^2+Y{\left(A_{i_1,i_2}\right)}^2}·\sqrt{X{\left(B_{i_2,i_3}\right)}^2+Y{\left(B_{i_2,i_3}\right)}^2}}.$$

(8)

3.6.1. Modeling $\alpha$-MAP

$\alpha$-MAP is the problem of computing the $\alpha$-polygon with the minimum area on a set of points. Since $\wp \left(S\right)$ is the set of all simple polygons containing S, $\alpha$-MAP can be formulated as follows:

$$\begin{array}{cc}& {\displaystyle \underset{P\in \wp \left(S\right)}{\min }}Area\left(P\right)\hfill \\ \mathrm{such}\mathrm{that}\hfill & \\ & \mathrm{All}\mathrm{internal}\mathrm{angles}\mathrm{of}P\mathrm{are}\mathrm{less}\mathrm{than}\mathrm{or}\mathrm{equal}\mathrm{to}\pi +\alpha \hfill \end{array}$$

(9)

As seen in Figure 1, each polygon $P\in \wp \left(S\right)$ assigns the points of S to the edges of $CH$. Therefore, each simple polygon containing S is equivalent to an assignments of the points of S to the edges of $CH$, and each assignment is determined by an evaluation of $Z_{i,j,k}$ for all $i,j,k$. In the following, the area function is formulated as an objective function of the model.

Theorem 1.

Let $P\in \wp \left(S\right)$ be a simple polygon and Z be the corresponding assignment for P. The area of P is computed as follows:

$$\begin{array}{c}Area\left(P\right)={\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=1}^r\hfill \\ [[{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k}·x_i+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k}))·x^{(j+1)}+{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}·x_i]\times \hfill \\ [{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k}·y_i+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k}))·y^{(j+1)}-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}·y_i\left]\right].\hfill \end{array}$$

(10)

Proof. 

Based on the Shoelace formula (also known as the surveyor’s formula [50]), the area of a polygon $P=(p_1,p_2,\dots ,p_l,p_1)$ is:

$$Area\left(P\right)={\mathsf{\Sigma }}_{i=1}^l(X\left(p_{i+1}\right)+X\left(p_i\right))·(Y\left(p_{i+1}\right)-Y\left(p_i\right)).$$

(11)

As an example, assume that P is the polygon of Figure 2. So, $p_1=s_1$, $p_2=s_5$, $p_3=s_6$, $p_4=s_{10}$, and $p_5=s_{11}$. Let $T_i=(X\left(p_{i+1}\right)+X\left(p_i\right))·(Y\left(p_{i+1}\right)-Y\left(p_i\right))$, thus we have:

$$T_1=(X\left(p_2\right)+X\left(p_1\right))·(Y\left(p_2\right)-Y\left(p_1\right))=(X\left(s_5\right)+X\left(s_1\right))·(Y\left(s_5\right)-Y\left(s_1\right)).$$

(12)

Since the points $s_5$ and $s_1$ are assigned to $e_1$ at positions 1 and 0, respectively, we have:

$$T_1=(X(1,1)+X(1,0))·(Y(1,1)-Y(1,0)).$$

(13)

In the same way,

$$\begin{array}{c}{T}_2=(X\left(p_3\right)+X\left(p_2\right))·(Y\left(p_3\right)-Y\left(p_2\right))=(X(1,2)+X(1,1))·(Y(1,2)-Y(1,1)),\hfill \\ T_3=(X\left(p_4\right)+X\left(p_3\right))·(Y\left(p_4\right)-Y\left(p_3\right))=(X(1,3)+X(1,2))·(Y(1,3)-Y(1,2)),\hfill \\ T_4=(X\left(p_5\right)+X\left(p_4\right))·(Y\left(p_5\right)-Y\left(p_4\right))=(X(2,0)+X(1,3))·(Y(2,0)-Y(1,3)).\hfill \end{array}$$

(14)

Based on the above equations, we employ the below formula for $T_1$,$T_2$, and $T_3$ so that:

$$T_k=(X(1,k)+X(1,k-1))·(Y(1,k)-Y(1,k-1)).$$

(15)

Equation (15) cannot be used for $T_4$:

$$\left(X\right(1,4)+X(1,3\left)\right)·\left(Y\right(1,4)-Y(1,3\left)\right)\ne \left(X\right(2,0)+X(1,3\left)\right)·\left(Y\right(2,0)-Y(1,3\left)\right).$$

In other words, Equation (15) can be used while the points are assigned to the same edge. In Equation (14), for $T_4$, the point $p_5=s_{11}$ is assigned to $e_2$ while the point $p_4$ is assigned to $e_1$. Based on Equation (1), since $\forall i\in \{1,2,\dots ,n\},Z_{i,1,4}=0\Rightarrow X(1,4)={\mathsf{\Sigma }}_{i=1}^n{Z}_{i,1,4}=0\Rightarrow (1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,1,4})·x^{\left(2\right)}=x^{\left(2\right)}\Rightarrow (1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,1,4})·x^{\left(2\right)}=X\left(p_5\right)$. Hence, $(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,1,4})·x^{\left(2\right)}$ can be used to compute $X\left(p_5\right)$.

$$\begin{array}{cc}{T}_k=\hfill & (X(1,k)+(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,1,k})·x^{\left(2\right)}+X(1,k-1))\times \hfill \\ & (Y(1,k)+(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,1,k})·y^{\left(2\right)}-Y(1,k-1)).\hfill \end{array}$$

(16)

Based on Equation (16):

$$\begin{array}{cc}{T}_4=\hfill & (X(1,4)+(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,1,4})·x^{\left(2\right)}+X(1,3))\times \hfill \\ & (Y(1,4)+(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,1,4})·y^{\left(2\right)}-Y(1,3)),\hfill \\ T_4=\hfill & (0+(1-0)x^{\left(2\right)}+X(1,3))·(0+(1-0)y^{\left(2\right)}-Y(1,3)),\hfill \\ T_4=\hfill & \left(X\right(2,0)+X(1,3\left)\right)·\left(Y\right(2,0)-Y(1,3\left)\right).\hfill \end{array}$$

(17)

Since, based on Equation (1), X(1,k) is equal to 0 for all $k\ge 4$, we have:

$$\begin{array}{c}{T}_5=(0+(1-0)x^{\left(2\right)}+X(1,4))·(0+(1-0)y^{\left(2\right)}-Y(1,4)),\hfill \\ T_5=(0+X(2,0)+0)·(0+Y(2,0)-0).\hfill \end{array}$$

(18)

Hence, in order to avoid extra summation, we employ the following equation:

$$\begin{array}{cc}{T}_k=\hfill & [X(1,k)+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,1,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,1,k})·x^{\left(2\right)}+X(1,k-1)]\times \hfill \\ & [Y(1,k)+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,1,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,1,k})·y^{\left(2\right)}-Y(1,k-1)].\hfill \end{array}$$

(19)

From Equation (19), for all $k\ge 5$ we have:

$$T_k=(0+\left(0\right)·(1-0)·x^{\left(2\right)}+0)\times (0+\left(0\right)·(1-0)·y^{\left(2\right)}-0)=0.$$

(20)

Considering the points that are assigned to $e_j$, Equation (19) can be extended as follows:

$$\begin{array}{cc}{T}_{j,k}=\hfill & [X(j,k)+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k})·x^{(j+1)}+X(j,k-1)]\times \hfill \\ & [Y(j,k)+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k})·y^{(j+1)}-Y(j,k-1)].\hfill \end{array}$$

(21)

Based on Equation (11), the area of the polygon P is computed as follows:

$$\begin{array}{ccc}Area\left(P\right)\hfill & =\hfill & {\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=1}^r{T}_{j,k}={\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=1}^r\hfill \\ & & [[X(j,k)+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k})·x^{(j+1)}+X(j,k-1)]\times \hfill \\ & & [Y(j,k)+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k})·y^{(j+1)}-Y(j,k-1)]].\hfill \end{array}$$

(22)

From Equations (1), (2) and (22), we have:

$$\begin{array}{c}Area\left(P\right)={\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=1}^r\hfill \\ [[{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k}·x_i+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k})·x^{(j+1)}+{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}·x_i]\times \hfill \\ [{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k}·y_i+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k})·y^{(j+1)}-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}·y_i]].\hfill \end{array}$$

(23)

 □

Based on Theorem 1, Equation (9) is formulated as follows:

$$\begin{array}{ccc}& \min {\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=1}^r\hfill & \\ & [[{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k}·x_i+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k})·x^{(j+1)}+{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}·x_i]\times \hfill & \\ & [{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k}·y_i+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k})·y^{(j+1)}-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}·y_i]]\hfill & \\ \mathrm{such}\mathrm{that}\hfill & & \\ & Z_{i,j,k}\in \{0,1\}\forall i\in \{1,\dots ,n\},\forall j\in \{1,\dots ,m\},\forall k\in \{1,\dots ,r\},\hfill & \hfill \left(a\right)\\ & {\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=1}^r{Z}_{i,j,k}\le 1\forall i\in \{1,2,\dots ,n\},\hfill & \hfill \left(b\right)\\ & conflict(i_1,i_2,i_3,i_4)=0\forall i_1,i_2,i_3,i_4\in \{1,2,\dots ,n\}\mid i_1\ne i_2\ne i_3\ne i_4,\hfill & \hfill \left(c\right)\\ & angle(i_1,i_2,i_3)\le \pi +\alpha \forall i_1,i_2,i_3\in \{1,2,\dots ,n\}\mid i_1\ne i_2\ne i_3.\hfill & \hfill \left(d\right)\end{array}$$

(24)

In Equation (24), constraint (a) considers all assignments of the points while constraint (b) prevents assigning a point to more than one edge. The point $s_i$ is unassigned if ${\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=1}^r{Z}_{i,j,k}=0$, and assigned to one edge if ${\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=1}^r{Z}_{i,j,k}=1$. Also, constraint (b) prevents assigning a point to more than one position on an edge. In addition, constraint (c) guarantees that the constructed polygon is simple, while constraint (d) ensures that it is an $\alpha$-polygon.

When $\alpha =0$, the solution of Equation (24) is an assignment that constructs the convex hull of the points, and when $\alpha =\pi$ the solution of Equation (24) is an assignment that constructs M as the solution of MAP on the points. There is an algorithm to compute $CH$ in $O\left(n\log n\right)$ time [51], while MAP is NP-complete.

Figure 3 illustrates the solution of $\alpha$-MAP on a set of points for different values of $\alpha$.

3.6.2. Modeling $\alpha$-MPP

$\alpha$-MPP is the problem of computing the $\alpha$-polygon with the maximum perimeter on a set of points. Since $\wp \left(S\right)$ is the set of all simple polygons containing S, $\alpha$-MPP is computed as follows:

$$\begin{array}{cc}& {\displaystyle \underset{P\in \wp \left(S\right)}{\max }}Perimeter\left(P\right)\hfill \\ \mathrm{such}\mathrm{that}\hfill & \\ & \mathrm{All}\mathrm{internal}\mathrm{angles}\mathrm{of}P\mathrm{are}\mathrm{less}\mathrm{than}\mathrm{or}\mathrm{equal}\mathrm{to}\pi +\alpha \hfill \end{array}$$

(25)

Let $P=(p_1,p_2,\dots ,p_l,p_1)$ be a polygon containing S. The perimeter of P is the total length of its edges:

$$Perimeter\left(P\right)={\mathsf{\Sigma }}_{i=1}^l\sqrt{{(X\left(p_{i+1}\right)-X\left(p_i\right))}^2+{(Y\left(p_{i+1}\right)-Y\left(p_i\right))}^2}.$$

(26)

By using Z as the corresponding assignment for P, similar to Theorem 1, the perimeter of P is computed as follows:

$$\begin{array}{c}Perimeter\left(P\right)={\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=1}^r\hfill \\ \sqrt{\begin{array}{c}\hfill {(X(j,k)+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k})·x^{(j+1)}-X(j,k-1))}^2+\\ \hfill {(Y(j,k)+\left({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1}\right)·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k})·y^{(j+1)}-Y(j,k-1))}^2\end{array}}\hfill \end{array}$$

(27)

Based on Equations (25) and (27), we have the following formula for $\alpha$-MPP:

$$\begin{array}{ccc}& \max {\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=1}^r\hfill & \\ & \sqrt{\begin{array}{c}\hfill {(X(j,k)+({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1})·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k})·x^{(j+1)}-X(j,k-1))}^2+\\ \hfill {(Y(j,k)+({\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k-1})·(1-{\mathsf{\Sigma }}_{i=1}^n{Z}_{i,j,k})·y^{(j+1)}-Y(j,k-1))}^2\end{array}}\hfill & \\ \mathrm{such}\mathrm{that}\hfill & & \\ & Z_{i,j,k}\in \{0,1\}\forall i\in \{1,\dots ,n\},\forall j\in \{1,\dots ,m\},\forall k\in \{1,\dots ,r\},\hfill & \hfill (a)\\ & {\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=1}^r{Z}_{i,j,k}\le 1\forall i\in \{1,2,\dots ,n\},\hfill & \hfill (b)\\ & conflict(i_1,i_2,i_3,i_4)=0\forall i_1,i_2,i_3,i_4\in \{1,2,\dots ,n\}\mid i_1\ne i_2\ne i_3\ne i_4,\hfill & \hfill (c)\\ & angle(i_1,i_2,i_3)\le \pi +\alpha \forall i_1,i_2,i_3\in \{1,2,\dots ,n\}\mid i_1\ne i_2\ne i_3.\hfill & \hfill (d)\end{array}$$

(28)

When $\alpha =0$, the solution of Equation (28) is an assignment that constructs the convex hull of the points, and when $\alpha =\pi$ it is an assignment that constructs E as the solution of MPP, which is known as Max-TSP, on the points. There is an algorithm to compute $CH$ in $O\left(n\log n\right)$ time, while Max-TSP is a well-known NP-complete problem.

Figure 4 illustrates the solution of $\alpha$-MPP on a set of points for different values of $\alpha$.

3.6.3. Modeling $\alpha$-MNP

$\alpha$-MNP on a set of points is the problem of computing the $\alpha$-polygon with the maximum number of vertices. Since $\wp \left(S\right)$ is the set of all simple polygons containing S, $\alpha$-MNP is computed as follows:

$$\begin{array}{cc}& {\displaystyle \underset{P\in \wp \left(S\right)}{\max }}Boundary\left(P\right)\hfill \\ \mathrm{such}\mathrm{that}\hfill & \\ & \mathrm{All}\mathrm{internal}\mathrm{angles}\mathrm{of}P\mathrm{are}\mathrm{less}\mathrm{than}\mathrm{or}\mathrm{equal}\mathrm{to}\pi +\alpha \hfill \end{array}$$

(29)

As stated before, $Z_{i,j,k}$ is equal to 1 iff the point $s_i$ is assigned to the edge $e_j$ at the position k. Hence, the following equation specifies the number of vertex points for the constructed polygon P:

$$Boundary\left(P\right)={\mathsf{\Sigma }}_{i=1}^n{\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=0}^r{Z}_{i,j,k}.$$

(30)

Similar to $\alpha$-MAP and $\alpha$-MPP, $\alpha$-MNP is formulated as follows:

$$\begin{array}{ccc}& \max {\mathsf{\Sigma }}_{i=1}^n{\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=0}^r{Z}_{i,j,k}\hfill & \\ \mathrm{such}\mathrm{that}\hfill & & \\ & Z_{i,j,k}\in \{0,1\}\forall i\in \{1,\dots ,n\},\forall j\in \{1,\dots ,m\},\forall k\in \{1,\dots ,r\},\hfill & \hfill \left(a\right)\\ & {\mathsf{\Sigma }}_{j=1}^m{\mathsf{\Sigma }}_{k=1}^r{Z}_{i,j,k}\le 1\forall i\in \{1,2,\dots ,n\},\hfill & \hfill \left(b\right)\\ & conflict(i_1,i_2,i_3,i_4)=0\forall i_1,i_2,i_3,i_4\in \{1,2,\dots ,n\}\mid i_1\ne i_2\ne i_3\ne i_4,\hfill & \hfill \left(c\right)\\ & angle(i_1,i_2,i_3)\le \pi +\alpha \forall i_1,i_2,i_3\in \{1,2,\dots ,n\}\mid i_1\ne i_2\ne i_3.\hfill & \hfill \left(d\right)\end{array}$$

(31)

When $\alpha =0$, the solution of Equation (31) is an assignment that constructs the convex hull of the points, and when $\alpha =\pi$ the solution of Equation (31) is an assignment that constructs C as the solution of MNP on the points. C is a simple polygon that crosses all points. There are optimal algorithms to compute $CH$ and C in $O\left(n\log n\right)$ time.

Figure 5 illustrates the solution of $\alpha$-MNP on a set of points, for different values of $\alpha$.

4. Theoretical Results

In this section, we present our theoretical results. As stated before, $\alpha$-MNP will be converted into CHP and SPP when $\alpha =0$ and $\alpha =\pi$, respectively, which are solvable in polynomial time. When $\alpha =\pi$, the constructed polygon crosses all points. For each set S of points, the smallest value of $\alpha$ such that $\alpha$-MNP crosses S is computed in the next subsection.

4.1. Upper Bound for $\alpha$ in $\alpha$-MNP

For each polygon $P\in \wp \left(S\right)$, assume that ${\gamma }_P$ is the maximum angle of the polygon P. Let $\theta$ be the minimum value of ${\gamma }_P$ over all $P\in \wp \left(S\right)$ that crosses S. For all $\alpha \ge \theta -\pi$, there always exists an $\alpha$-polygon that crosses S. In other words, the polygon $P^{\prime }$ such that ${\gamma }_{P^{\prime }}=\theta$, satisfies $\alpha$-MNP for all $\alpha \ge \theta -\pi$. Here, we present an upper bound for $\theta$, on any set of points.

In Theorem 2, it is shown that $2\pi -\frac{2\pi }{2^{r-1}m}$ can be interpreted as an upper bound for $\theta$, and in Theorem 3 this bound is improved. In the following, we design an algorithm to construct a simple polygon containing S which satisfies these bounds. Let us first define the concept of a “sweep arc”, and then prove some lemmas.

Definition 4.

Let $e=\overline{AB}$ be an edge of polygon P. A sweep arc on the edge e is a minor arc $AB$ where $\stackrel{⌢}{AB}=0$ and expands to the major arc $AB$ where $\stackrel{⌢}{AB}=\pi$. The direction of expansion is to the inside of the polygon. Figure 6 depicts the sweep arc on the edge e.

Let $e_j$ be an edge of the polygon P. We denote the major segment with length of $\beta$ that corresponds to $e_j$ by $M_j^{\beta }$.

Lemma 1.

Let x be a point inside the convex polygon P, $E=\{e_1,e_2,\dots ,e_m\}$ be the edges of P and $\beta =2\pi -\frac{4\pi }{m}$. Then $\exists j\in \{1,2,\dots ,m\}$, such that $x\in M_j^{\beta }$.

Proof. 

Let ${\beta }_j$ be the angle subtended by $e_j$ at the point x and ${\beta }_M$ be the maximum angle. Let e be the edge that corresponds to ${\beta }_M$. Since ${\mathsf{\Sigma }}_{j=1}^m{\beta }_j=2\pi$, we have ${\beta }_M\ge \frac{2\pi }{m}$ and the corresponding arc of ${\beta }_M$ is more than $\frac{4\pi }{m}$. Hence, the measure of the sweep arc on the edge e at x is less than $2\pi -\frac{4\pi }{m}$, (see Figure 7). □

Lemma 2.

Let P be a convex polygon, $\{e_1,e_2,\dots ,e_m\}$ be the edges of P and ${\beta }_{max}=2\pi -\frac{4\pi }{m}$. The entirety of P is covered by all major segments with length of ${\beta }_{max}$ that correspond to the edges of P, i.e., $P\subset {\cup }_{j=1}^m{M}_j^{{\beta }_{max}}$ (see Figure 8).

Proof. 

To prove the lemma by reductio ad absurdum, suppose that there exists a point x inside the polygon P and outside of all the major segments. Since the measures of all major segments are equal to $2\pi -\frac{4\pi }{m}$, there is no edge e such that the sweep arc on e touches x at the measure $\beta \le 2\pi -\frac{4\pi }{m}$, i.e., $\forall j\in \{1,2,\dots ,m\}$, $x\notin M_j^{{\beta }_{max}}$. This contradicts Lemma 1. □

Remark 1.

Suppose that the convex hull of S has $n-1$ edges; that is, one point is inside the convex hull. Based on Lemma 2, $2\pi -\frac{2\pi }{n-1}$ is an upper bound for θ over all simple polygons containing S. It is noteworthy that this bound is tight. The tightness is achieved when the inner point is at the center of a regular n-gons, as illustrated in Figure 9.

In the following, we generalize the upper bound for any set S of points, and then present an algorithm to generate a polygon containing S that satisfies the generalized upper bound. However, let us first consider a sweep arc on an edge to measure ${\beta }_{max}$ that includes a set of n points.

Lemma 3.

Let $e=\overline{c_1{c}_2}$ be a line segment and S be a set of n points inside the major segment corresponding to e, such that the measure of major arc is ${\beta }_{max}=2\pi -\frac{4\pi }{m}$ for an integer number m (see Figure 10a). There exists a chain $(s_1,s_2,\dots ,s_n)$ on S such that all internal angles of $\widehat{s_i}$ in the polygon $(c_1,s_1,s_2,\dots ,s_n,c_2,c_1)$ are greater than or equal to $\frac{2\pi }{2^{n-1}·m}$ (see Figure 10b).

Proof. 

Here, we employ the sweep arc algorithm to construct the polygon.

Algorithm 1 (Sweep Arc Algorithm)

Let us sweep the arc from measure 0 to ${\beta }_{max}$ on $e=\overline{c_1{c}_2}$. By so doing, the polygon is constructed, while the arc hits the points. In the following, we show how to construct the polygon step by step.

On the first hit:

Let $x_1$ be the first point that the sweeping arc meets. We construct the polygon by connecting $x_1$ to $c_1$ and $c_2$. Since the maximum measure of the arc is ${\beta }_{max}$, the internal angle of $\widehat{x_1}$ in the triangle $\left(c_1{x}_1{c}_2\right)$ is greater than or equal to $\frac{2\pi }{m}$ (see Figure 11).

On the second hit:

Let $x_1$ be the first point that the sweeping arc meets and $x_2$ be the second one. Also, let $e_1=\overline{c_1{x}_1}$ and $e_2=\overline{c_2{x}_1}$ be two constructed edges in the previous step. The edges $e_1$ and $e_2$ divide the sweeping arc into 3 parts; the arc $B_1$ where $e_1$ is visible but $e_2$ is not visible from all the points on it; the arc $B_2$ where $e_2$ is visible but $e_1$ is not visible from all the points on it; and finally the arc $B_3$ where $e_1$ and $e_2$ are visible from all points on it (see Figure 12).

Case 1.

If $x_2$ is placed on $B_1$: The angle $\widehat{c_1{x}_2{x}_1}$ is greater than $\widehat{c_1{x}_2{c}_2}$, and the angle $\widehat{c_1{x}_2{c}_2}$ is greater than or equal to $\frac{2\pi }{m}$. Hence, the angle $\widehat{c_1{x}_2{x}_1}$ is greater than $\frac{2\pi }{m}$. Since the internal angles $\widehat{x_2}$ and $\widehat{x_1}$ are greater than $\frac{2\pi }{2m}$, we consider the polygon $\left(c_1{x}_2{x}_1{c}_2{c}_1\right)$ as the constructed polygon.

Case 2.

If $x_2$ is placed on $B_2$: Based on the same reason mentioned above, the angle $\widehat{c_2{x}_2{x}_1}$ is greater than $\frac{2\pi }{m}$. Since the internal angles $\widehat{x_2}$ and $\widehat{x_1}$ are greater than $\frac{2\pi }{m}$, we consider the polygon $\left(c_1{x}_1{x}_2{c}_2{c}_1\right)$ as the constructed polygon.

Case 3.

If $x_2$ is placed on $B_3$: In contrast to the previous cases, the angles $\widehat{c_1{x}_2{x}_1}$ and $\widehat{c_2{x}_2{x}_1}$ are less than $\widehat{c_1{x}_2{c}_2}$, but the maximum of $\widehat{c_1{x}_2{x}_1}$ and $\widehat{c_2{x}_2{x}_1}$ is greater than $\frac{\widehat{c_1{x}_2{c}_2}}{2}$. Since $\widehat{c_1{x}_2{c}_2}$ is greater than $\frac{2\pi }{m}$, the maximum of $\widehat{c_1{x}_2{x}_1}$ and $\widehat{c_2{x}_2{x}_1}$ is greater than $\frac{2\pi }{2m}$. Hence, if $\widehat{c_1{x}_2{x}_1}>\widehat{c_2{x}_2{x}_1}$, the constructed polygon is $\left(c_1{x}_2{x}_1{c}_2{c}_1\right)$; otherwise, it is $\left(c_1{x}_1{x}_2{c}_2{c}_1\right)$.

In other words, the angular bisector of $\widehat{c_1{x}_1{c}_2}$ divides the sweeping arc into 2 parts, $A_1$ and $A_2$ (see Figure 13). Any point $x_2$ on $A_1$ constructs the angle $\widehat{c_1{x}_2{x}_1}$ greater than $\frac{2\pi }{2m}$, and on $A_2$ constructs the angle $\widehat{x_1{x}_2{c}_2}$ greater than $\frac{2\pi }{2m}$. Hence, in the case where point $x_2$ is placed on $A_1$, we consider the polygon $\left(c_1{x}_2{x}_1{c}_2{c}_1\right)$ as the constructed polygon and, if placed on $A_2$, we consider the polygon $\left(c_1{x}_1{x}_2{c}_2{c}_1\right)$ as the constructed polygon.

On the third hit:

Without loss of generality, assume that $\left(c_1{x}_2{x}_1{c}_2{c}_1\right)$ is the polygon obtained at the end of the previous step. The angular bisector of $\widehat{c_1{x}_2{x}_1}$ divides $A_1$ into 2 parts $A_{11}$ and $A_{12}$. Hence, the sweeping arc is divided into 3 parts $A_2$, $A_{11}$ and $A_{12}$ (see Figure 14).

Based on the previous step, any point $x_3$ on $A_2$ leads to the construction of the angle $\widehat{x_1{x}_3{c}_2}$ which is greater than $\frac{2\pi }{2m}$. Similarly, any point $x_3$ on $A_{11}$ and $A_{12}$ leads to the construction of the angles $\widehat{c_1{x}_3{x}_2}$ and $\widehat{x_2{x}_3{x}_1}$, respectively, which are greater than $\frac{\widehat{c_1{x}_3{x}_1}}{2}$. Since any angle $\widehat{c_1{x}_3{x}_1}$ on $A_1$ is greater than $\frac{2\pi }{2m}$, either the angle $\widehat{c_1{x}_3{x}_2}$ or $\widehat{x_2{x}_3{x}_1}$ is greater than $\frac{2\pi }{4m}$.

Let $x_3$ be the third point that the sweeping arc meets. If $x_3$ is placed on $A_2$, or on $A_{11}$ or on $A_{12}$, we consider $\left(c_1{x}_2{x}_1{x}_3{c}_2{c}_1\right)$ or $\left(c_1{x}_3{x}_2{x}_1{c}_2{c}_1\right)$ or $\left(c_1{x}_2{x}_3{x}_1{c}_2{c}_1\right)$ as the constructed polygon, respectively (see Figure 15).

Generalization:

Assume that $(c_1{x}_1{x}_2\dots x_{n-1}{c}_2{c}_1)$ is the obtained polygon at the end of the previous step. Let $x_n$ be the next point touched by the sweeping arc which is divided into n parts $A_1,A_2,\dots ,A_n$. Considering the worst case, $x_n$ is placed on $A_i$ or on $A_{i+1}$ such that the angular bisector of $\widehat{x_i}$ divides the corresponding part into $A_i$ and $A_{i+1}$. Any point $x_n$ on $A_i$, or on $A_{i+1}$, leads to the construction of the angle $\widehat{x_n}$ which is greater than $\frac{\widehat{x_i}}{2}$. Based on the previous step and considering the worst case, the angle $\widehat{x_i}$ is greater than $\frac{2\pi }{2^{n-2}m}$. Hence, the angle $\widehat{x_n}$ is greater than $\frac{2\pi }{2^{n-1}m}$. If $x_n$ is placed on $A_1$, or on $A_2$, ... or on $A_n$, we consider the polygon $(c_1{x}_n{x}_1\dots x_{n-1}{c}_2{c}_1)$, or $(c_1{x}_1{x}_n{x}_2\dots x_{n-1}{c}_2{c}_1)$, ... or $(c_1{x}_1\dots x_{n-1}{x}_n{c}_2{c}_1)$ as the constructed polygon, respectively. □

We refer to the polygon constructed by Algorithm 1 as a polygon corresponding to the line segment e. In the following, based on the Lemma 3, we present an algorithm to generate a polygon containing a given set of points, such that all internal angles are less than $2\pi -\frac{2\pi }{2^{r-1}m}$.

Theorem 2.

There exists a polygon $P\in \wp \left(S\right)$ that crosses S, in which all internal angles of P are less than $2\pi -\frac{2\pi }{2^{r-1}m}$.

Proof. 

Here, by presenting Algorithm 2, we construct the polygon.

Algorithm 2

• Compute $CH$ as the convex hull of S, and let $IP$ be the set of inner points of $CH$.
• For each edge $e_j$ of $CH$:

  (a)

  Compute the polygon $P_j$ corresponding to the edge $e_j$ using Algorithm 1 to meet the points of $IP$.

  (b)

  Remove the vertices of $P_j$ from $IP$.

• For all $j\in \{1,2,\dots ,m\}$, the edges of $P_j$ minus all edges of $CH$ (except those that have no corresponding polygon), construct the desired polygon.

Based on Lemma 2, the entire $CH$ is covered by all major segments that correspond to the edges of $CH$ with length of ${\beta }_{max}=2\pi -\frac{4\pi }{m}$. Since the number of points inside the major segments is less than r and also, based on Lemma 3, all internal angles of the corresponding polygons are greater than or equal to $\frac{2\pi }{2^{r-1}m}$. Hence, all internal angles of the polygon computed by Algorithm 2 are less than $2\pi -\frac{2\pi }{2^{r-1}m}$. □

In step 2(a) of Algorithm 2, for each edge of $CH$, the measure of sweeping arc expands from 0 to ${\beta }_{max}$, and the sweeping arc contains the inner points as much as possible. In Algorithm 3 (presented below), the sweeping arcs that correspond to all edges of $CH$ expand concurrently to contain all inner points. In this way, the upper bound is improved to $2\pi -\frac{2\pi }{2^{d-1}m}$, such that d is the depth of angular onion peeling on S which is defined as follows:

Let us increase the measure of all sweeping arcs concurrently from 0 to the first hit (or ${\beta }_{max}$, if a sweeping arc does not hit any point). All inner points that are hit by sweeping arcs form layer 1 of the points. The next layers are formed by deleting the points of the computed layer from inner points and keep increasing the measure of all sweeping arcs to the next hit. The process continues until all inner points are hit. The process of peeling away the layers, described above, is defined as "angular onion peeling" and the number of layers is called "depth of angular onion peeling" on these points.

Theorem 3.

There exists a polygon $P\in \wp \left(S\right)$ such that crosses S, and all internal angles of P are less than $2\pi -\frac{2\pi }{2^{d-1}m}$ where d denotes the depth of angular onion peeling on S.

Proof. 

Here, by presenting Algorithm 3, we construct such a polygon.

Algorithm 3

• Compute $CH$ as the convex hull of S, and let $IP$ be the set of inner points.
• While $IP$ is not empty:

  (a)

  Increase the measure of all sweeping arcs to the next hit or ${\beta }_{max}$.

  (b)

  Based on Algorithm 1, reconstruct the polygons corresponding to each edge of $CH$.

  (c)

  Remove the visited points from $IP$.

All edges of corresponding polygons computed in step 2, minus all of the edges of $CH$ (except those that have no corresponding polygon), construct the desired polygon.

Since, the number of points inside the major segments are less than d, all internal angles of corresponding polygons are greater than or equal to $\frac{2\pi }{2^{d-1}m}$. Hence, all internal angles of the polygon computed by Algorithm 3 are less than $2\pi -\frac{2\pi }{2^{d-1}m}$. □

4.2. $\alpha$-MAP vice versa $\alpha$-MNP

Let S be a set of points on the grid G and $P\in \wp \left(S\right)$ be a simple polygon. Based on Pick’s theorem [52], the area of P is equal to $\frac{b}{2}+i-1$ where b is the number of grid points on the boundary of P and i is the number of grid points which are inside the polygon P.

The polygon P crosses both $b_1$ points of S, which we call vertex points, and $b_2$ non-vertex points on G, which we call grid points. Hence, $Area\left(P\right)=\frac{b_1+b_2}{2}+i-1$.

Assume that two polygons A and B with the same number of inner grid points cross no grid points (i.e., $b_2=0$). Hence, based on Pick’s theorem, the area of polygon A is more than that of B iff the number of vertex points in A is more than that in B. In this case, $\alpha$-MAP is equivalent to $\alpha$-MNP.

In the following, we show that for each polygon $P\in \wp \left(S\right)$ on the grid and all $ϵ>0$, there exists a polygon $P^{\prime }$ with the same vertices points such that $|Area\left(P\right)-Area\left(P^{\prime }\right)|<ϵ$, and $P^{\prime }$ does not cross any grid point.

Let $e=\overline{ab}$ be an edge of P on the grid G. If $a=(x_a,y_a)$ and $b=(x_b,y_b)$, $W_e=|x_b-x_a|$ is the width of e and $H_e=|y_b-y_a|$ is the height of e. (see Figure 16)

Lemma 4.

Let e be an edge of P on the grid G. If $W_e$ and $H_e$ are coprime integers, then e does not cross any grid point.

Proof. 

Assume e crosses $n>0$ grid points. As shown in Figure 17, $W_e$ is divided into $n+1$ parts, similar to $H_e$. Hence, $n+1$ is common divisor of $W_e$ and $H_e$. □

Lemma 5.

Let a and b be two non-coprime integers. There exist infinitely many positive integers $x>1$, such that $ax$ and $bx-1$ are coprime integers.

Proof. 

Each common denominator of a and b satisfies x. □

Definition 5.

The polygon $P\in \wp \left(S\right)$ is a grid-avoiding polygon if P does not cross any grid points.

The following theorem shows that if P crosses some grid points, for all $ϵ>0$ there exists a grid-avoiding polygon $P^{\prime }$ such that $|Area\left(P\right)-Area\left(P^{\prime }\right)|<ϵ$.

Theorem 4.

Let $e=\overline{ab}$ be an edge of $P\in \wp \left(S\right)$ that crosses a grid point. For all $ϵ>0$, there exists a point $b^{\prime }$ such that $e^{\prime }=\overline{a{b}^{\prime }}$ does not cross any grid point, the number of inner grid points does not change, and $\left|Area\right(ab{b}^{\prime }\left)\right|<ϵ$.

Proof. 

We convert the grid G to the grid $G^{\prime }$ by dividing each cell of G into $x^2$ subcells and placing $b^{\prime }$ on the one grid point left or right of b, as shown in Figure 18. If the right (left) grid point is inside the polygon P, place $b^{\prime }$ on the right (left) side of b. Let $n=x{H}_e$, $m=x{W}_e$ and $m^{\prime }=x{W}_{e^{\prime }}=m-1$. Based on Lemma 5, there exist infinitely many integers x such that n and $m^{\prime }$ are coprime integers. Based on Lemma 4, since n and $m^{\prime }$ are coprime integers, the edge $e^{\prime }$ does not cross any grid point of $G\prime$. As seen in Figure 18, the number of grid points inside the polygon does not change.

Let u be the length of each side of grid cells in G and $u^{\prime }$ be the length of each side of grid cells in $G^{\prime }$. Based on Figure 18, $Area\left(ab{b}^{\prime }\right)=\frac{1}{2}{u}^{\prime }{H}_e$. Since $u^{\prime }=\frac{u}{x}$ and there exist infinitely many integers x such that $x{W}_{e^{\prime }}$ and $x{H}_e$ are coprime integers, for each $ϵ>0$ there exists an integer x such that $\left|Area\right(ab{b}^{\prime }\left)\right|<ϵ$. □

The following algorithm converts the grid G into the grid $G^{\prime }$, and the polygon P into the grid-avoiding polygon $P^{\prime }$ on $G^{\prime }$.

Algorithm 4

Let $P=(a_1,a_2,a_3,\dots ,a_n,a_1)$ be the polygon on the grid G.

• Set $i=1$
• If $i=n$ go to 5, otherwise set $e=\overline{a_i{a}_{i+1}}$
• If e does not cross any grid point

  (a)

  $i=i+1$

  (b)

  Go to step 2.

• Else

  (a)

  Set $x=LCD(W_e,H_e)$

  (b)

  Convert G into the grid $G^{\prime }$ using x (dividing each cell of G into $x^2$ subcells).

  (c)

  For $j=1$ to $i-1$

  • If $d=\overline{a_j{a}_{j+1}}$ crosses any grid point
    • Move the vertex $a_{j+1}$ to the left side or right side grid point (in $G^{\prime }$).

  (d)

  If e crosses any grid point

  • Move the vertex $a_{i+1}$ to the left side or right side grid point (in $G^{\prime }$).

  (e)

  set $i=i+1$ and go to step 2.

• Exit.

Let $W_i$ be the width of $e_i=\overline{a_i{a}_{i+1}}$ and $H_i$ be the length of $e_i$. Let us further assume that $W_1$ and $W_2$ are coprime to $H_1$ and $H_2$, respectively. Steps 3(a) and 3(b) avoid changing the position of these vertices. Assume $e_3=\overline{a_3{a}_4}$ crosses a grid point. The grid G is converted into the grid $G^{\prime }$ in step 4(b). In the new grid $G^{\prime }$, since $W_{1^{\prime }}$=$x{W}_1$ and $H_{1^{\prime }}=x{H}_1$, the width and length of $e_1$ are not coprime integers the same as the width and length of $e_2$. Therefore, the position of the previous vertices should be changed. Step 4(c) of Algorithm 4 updates the position of the previous vertices. Note that changing $e_1$ may have an effect on the edge $e_2$. Hence, we check the loop in step 4(c), to see if the edge crosses any grid point. If so, then updating the last previous edge may have an effect on the edge $e_3$. Hence, in step 4(d), we change the position of $a_4$ if $e_3$ crosses any grid point. Finally, the position of all vertices are updated such that the new edges do not cross any grid point.

Corollary 1.

Let $P_1$ and $P_2$ be two simple polygons containing S with the same number of inner grid points. $Boundary\left(P_1\right)>Boundary\left(P_2\right)$ iff $Area\left(P_1\right)<Area\left(P_2\right)$. In other words, under these conditions we have the same solution for α-MAP and α-MNP.

Corollary 2.

Let $P_1$ and $P_2$ be two simple polygons containing S. If $Boundary\left(P_1\right)\subset Boundary\left(P_2\right)$, then $Area\left(P_2\right)<Area\left(P_1\right)$.

5. Numerical Experiments and Results

Considering Equations (24), (28) and (31), the time complexity of the brute-force algorithm is $O\left(2^{n·m·r}\right)$ such that n is the number of points, m is the number of vertices of $CH$, and r is the number of inner points. In this section, we present a genetic algorithm as a fast and accurate method to solve these models. The genetic algorithm is a powerful stochastic search technique, which is applicable to a variety of nonconvex optimization problems [53].

In order to evaluate the results, we implemented both the $GA$ and the brute-force algorithm for $\alpha$-MAP, $\alpha$-MPP, and $\alpha$-MNP. We ran both algorithms on the same datasets of points. Each dataset contained 100 sets of points with the same cardinality. We obtained the results for datasets of 5, 7, 10, and 12 points which are tabulated in

Table 2. Numerical results.

Number of Points	Number of Generations	Area		Perimeter		Boundary
		Quality	Quantity	Quality	Quantity	Quality	Quantity
n = 5	50	99.15344	96	98.35035	95	98.6	95
	100	99.87179	99	99.46023	99	100	100
	150	100	100	100	100	100	100
	200	100	100	100	100	100	100
n = 7	50	97.05038	83	97.1653	88	97.4026	82
	100	98.67008	92	98.77586	96	98.14285	93
	150	98.91394	93	100	100	100	100
	200	98.90656	95	100	100	100	100
n = 10	50	94.21655	55	89.56722	67	80.90909	24
	100	95.14197	67	94.31243	80	89	50
	150	97.79823	83	96.67498	93	97.5	87
	200	97.88455	84	100	100	100	100
n = 12	50	87.95903	52	87.86893	59	80.53846	20
	100	90.84784	63	93.45262	70	84.66667	44
	150	96.67498	77	95.95328	84	93.91667	73
	200	97.76408	82	96.15958	98	98.5	91

.

A polygon-match occurs if the result of the GA on a set of points is the same as that of the brute-force algorithm. The quantity column in Table 2 shows the percentage of polygon-matches in each dataset, and the quality column displays the average difference between the two areas; that is, $Area\left(P\right)-Area\left(P^{\prime }\right)$ where P and $P^{\prime }$ are the constructed polygons using the genetic and the brute force algorithms, respectively.

The pseudocode for the GA is presented as follows:

Algorithm 5 (Genetic Algorithm)

Inputs:

$\begin{array}{cc}S:\mathrm{the}\mathrm{points}\mathrm{set}\hfill & \alpha :\mathrm{constraint}\mathrm{on}\mathrm{angles}\hfill \\ e:\mathrm{elitism}\mathrm{rate}\hfill & mu:\mathrm{mutation}\mathrm{rate}\hfill \\ it{t}_{count}:\mathrm{iteration}\mathrm{count}\hfill \end{array}$

• Initialize the population: Generate random $\alpha$-polygons with $m,m+1,\dots ,n$ vertices containing S. Also, set $itt=1$.
• Coding: Compute the vector C for each randomly generated polygon as a code such that $C[i\times j\times k]=1$ iff $Z_{i,j,k}$=1. The length of C is $n\times m\times r$.
• Packing: Construct a chromosome $chr$ for each code using C such that $chr\left[k\right]=j$ iff the kth inner point is assigned to the jth edge of $CH$, i.e., $\exists t\in \{1,2,\dots ,r\}:C[k\times j\times t]=1$. The length of chr is r.
• Elitist selection: Select e percent of the best chromosomes, and move them to the next generation.
• Crossover: The single-point crossover is used. Select a random position $ind$ ($1\le ind\le r$) and two random chromosomes as the parents.
• Mutation: Each child that is constructed in step 5 is mutated with a probability of $mu$. Select a random position $ind$ ($1\le ind\le r$) and randomly change the value of $chr\left[ind\right]$. The mutation leads an inner point to be assigned to another edge.
• Unpacking: Convert each chromosome of the new generation into an individual code. Each $chr$ in the new generation is unpacking to a code C. In this step, the order of assigned points for each edge is specified.
• Re-evaluate: Based on the objective function (Area, Perimeter, and Boundary), re-evaluate the new polygons and keep the best chromosome as the solution. Replace the old generation with the new one and set $itt=itt+1$. If $itt<it{t}_{count}$ go to step 3, otherwise finish.

Because of the exponential time complexity of the brute-force algorithm, the exact result could not be obtained on large datasets in a reasonable computational time. Thus, we ran the GA on datasets of 15, 20, 25, and 30 points and displayed the resulting polygons in Figure 19 which are the solutions for $\alpha$-MAP for $\alpha =\pi$.

As stated in Section 1, the concave hull is a generalization of the convex hull, that identifies the area occupied by a set of points. Moreira and Santos presented an algorithm to compute the concave hull [49], and in [54] an algorithm was presented to compute the concave hull in d dimensions. We implemented the said algorithm in [49], and compared the quality of the obtained result with that of the GA. Figure 20 illustrates this comparison with the x-axis exhibiting the cardinality of datasets and the y-axis exhibiting the approximation average quality of the results.

Figure 21, Figure 22 and Figure 23 illustrate the results of GA on a set of points which are the solutions for $\alpha$-MAP, $\alpha$-MPP, and $\alpha$-MNP for different values of $\alpha$, respectively. For $\alpha =0$, the constructed polygons are the convex hull of points. As the value of $\alpha$ increases, the concave angles start to appear in the polygons. For large values of $\alpha$ (e.g., for $\alpha ={180}^{\circ }$), the boundary of the polygons would pass through all of the points; the results are simple polygons with approximately minimum area, maximum perimeter, and maximum number of vertices, respectively.

6. Conclusions

In this paper, we considered the problem of finding optimal simple polygons containing a set of points in the plane. We generalized the problems of finding the minimum area, maximum perimeter, and maximum number of vertices containing a set of points by adding constraint to the angles of polygons. We formulated the generalized problems as nonlinear programming models.

Given that all simple polygons contain a set of points, we derived an upper bound for the minimum of the maximum angles of each polygon. As a further theoretical achievement, we demonstrated that the problem of computing a polygon with minimum area is almost equivalent to that of computing a polygon with a maximum number of vertices.

We presented a genetic algorithm to solve these models, and conducted experiments on several datasets. Finally, in comparison to the brute-force method and other previous studies, better results were obtained.