Mendeley
TY  _  JOUR
ID  -  202005066584
TI  -  Heuristic algorithms for pseudo-triangulation random point set in the plane
JO  -  Journal of Information and Communication Technology
JA  -  ES
LA  -  fa
SN  -  2717-0411
AU  -  naghdeforoshhs mona
AU  -  taherkhani fahime
AU  -  norollah ali
AD  -  دانشگاه آزاد اسلامی
AD  -  دانشگاه آزاد اسلامی
AD  -  دانشگاه آزاد اسلامی
Y1  -  2019
PY  -  2019
VL  -  16
IS  -  
SP  -  49
EP  -  58
KW  -  Pseudo-Triangulation
KW  -   Convex hull
KW  -   Convex and concave chain
KW  -   Visibility
KW  -   Simple polygon
DO  -  
N2  -  Finding algorithms for the diverse issues proposed in Computational Geometry including pseudo-triangulation of point set is among the scientific subjects, which has already attracted the attention of computer scientists'.
A pseudo-triangle is a simple polygon in the plane with exactly three convex vertices, called corners. Three reflex chains of edges join the corners. A pseudo-triangulation for point set is a partition of the convex hull of point set into pseudo-triangles whose vertex set is point set.
Many possible optimality criteria have been investigated for pseudo-triangulations which are often based on edge weights or angles in which computing a minimum weight pseudo-triangulation for a point set is among the open problems. A pseudo-triangulation is called minimum if it consists of exactly n-2 pseudo-triangles and the minimum number of edges needed for it is 2n-3. Every vertex of a minimum pseudo-triangulation is pointed. A vertex is pointed if it has an incident angle greater than π.
With respect to the proposed cases, the aim of this thesis is to present new methods for pseudo-triangulation of point set in the plane, so that it can open new algorithmic reflections in this field. This research shows that the generation of convex hull layers for point set and their pseudo-triangulation, using two new algorithms which have been considered in this research, minimizes pseudo-triangulation. Also a new algorithm has been considered to generate spiral simple polygon such that the generation of random simple polygons has two main areas of application: testing the correctness and evaluating the CPU-time consumption of algorithms that operate on polygons

UR  - rimag.ir/en/Article/6584
L1  - rimag.ir/en/Article/Download/6584
ER  -  
