Heuristic algorithms for pseudo-triangulation random point set in the plane
Subject Areas :mona naghdeforoshhs 1 * , fahime taherkhani 2 , ali norollah 3
1 -
2 -
3 -
Keywords: Pseudo-Triangulation, Convex hull, Convex and concave chain, Visibility, Simple polygon,
Abstract :
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
[1]. G. Rote, F. Santos, and I. Streinu, “Pseudo-Triangulation – a Survey,” Contemporary Mathematics, 453: 343-410, American Mathematical Society, 2008.
[2]. O. Aichholzer, F. Aurenhammer, H. Krasser, and B. Speckmann, “Convexity minimizes pseudo-triangulations,” Computational Geometry 28, pp.3-10, 2004.
[3]. I. Streinu, “A combinatorial approach to planar non-colliding robot arm motion planning,” In : Proc. 41st Annu.IEEE Sympos. Foundat. Comput.Sci. (FOCS'00), , pp.443-453, 2000.
[4]. S. Gerdjikov, and A. Wolff, “Decomposing a simple polygon into pseudo-triangles and convex polygons,” Computational Geometry 41, pp.21-30, 2008.
[5]. M. Ben-Ner, A. Schulz, and A. Sheffer, “On numbers of pseudo-triangulations,” arXiv: 1210. 7126v1 [cs.CG] 26 oct 2012.
[6]. O. Aichholzer, T. Hackl, and B. Vogtenhuber, “Compatible pointed pseudo-triangulations,” 22nd Canadian Conference on Computational Geometry, 2010.
[7]. M. Pocchiola, and G. Vegter, “Topologically sweeping visibility complexes via pseudo-triangulations,” Discrete Compute.Geom. 16, pp.419-453, 1996.
[8]. M.T. Goodrich, and R. Tamassia, “Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations,” J. Algorithms 23 (1), pp.51-73, 1997.
[9]. D.G. Kirkpatrick, J. Snoeyink, and B. Speckmann, “kinetic collision detection for simple polygons,” Internat. J. Comput. Geom. Appl. 12(1-2), pp. 3-27, 2002.
[10]. B. Speckmann, and C.D. Tόth, “Allocating vertex π-guard in simple polygons via pseudo-triangulations,” Discrete Comput. Geom. 33 (2), pp.345-364, 2005.
[11]. T. Aure, and M. Held, “Heuristic for generation of random polygons,” 8th Canadian Conference On Computational Geometry (CCCG),Ottawa, Canada, pp.38-44,1996.
[12]. D. Dailey, and D. Whitfield, “Constructing random polygons,” SIGITE'08, USA, pp.119-124, 2008.
[13]. M. D. Berg, Computational Geometry: Algorithms and Applications, 3rd edition, published by Springer-Verlag, 2008.
[14]. B. Chazelle, “On the convex layers of a planar Set,” IEEE Tran. Information Theory, Vol. IT-31, No. 4, pp. 509-517, 1985.