{"title":"Constructing a Simple Polygonalizations","authors":"V. Tereshchenko, V. Muravitskiy","volume":53,"journal":"International Journal of Computer and Information Engineering","pagesStart":493,"pagesEnd":497,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/5368","abstract":"We consider the methods of construction simple\npolygons for a set S of n points and applying them for searching the\nminimal area polygon. In this paper we propose the approximate\nalgorithm, which generates the simple polygonalizations of a fixed\nset of points and finds the minimal area polygon, in O (n3) time and\nusing O(n2) memory.","references":"[1] Chong Zhu, Gopalakrishnan Sundaramb, J. Snoeyink and Joseph S. B.\nMitchell. Generating random polygons with given vertices.\nJur.Computational Geometry: Theory and Applications . Vol. 6, Issue 5,\nElsevier, 1996, Pages 277-290.\n[2] H. J. Miller and J. Han, Eds., Geographic Data Mining and Knowledge\nDiscovery. CRC Press, 2001.\n[3] ] A. Galton and M. Duckham, \"What is the region occupied by a set of\npoints?\" in GIScience, ser. Lecture Notes in Computer Science.\nSpringer, 2006, vol. 4197, pp. 81-98.\n[4] A. Galton, \"Dynamic collectives and their collective dynamics,\" in\nCOSIT, ser. Lecture Notes in Computer Science. Springer, 2005, vol.\n3693, pp. 300-315.\n[5] M. F. Worboys and M. Duckham, \"Monitoring qualitative\nspatiotemporal change for geosensor networks,\" International Journal of\nGeographic Information Science, vol. 20, no. 10, pp. 1087-1108, 2006.\n[6] H. Edelsbrunner, D. G. Kirkpatrick, and R. Seidel, \"On the shape of a set\nof points in the plane,\" IEEE Transactions on Information Theory, vol.\nIT-29, no. 4, pp. 551-558, 1983.\n[7] M. Melkemi and M. Djebali, \"Computing the shape of a planar points\nset,\" Pattern Recognition, vol. 33, pp. 1423-1436, 2000.\n[8] M. J. Fadili, M. Melkemi, and A. ElMoataz, \"Non-convex onion-peeling\nusing a shape hull algorithm,\" Pattern Recognition Letters, vol. 25, pp.\n1577-1585, 2004.\n[9] A. R. Chaudhuri, B. B. Chaudhuri, and S. K. Parui, \"A novel approach\nto computation of the shape of a dot pattern and extraction of its\nperceptual border,\" Computer Vision and Image Understanding, vol. 68,\nno. 3, pp. 257-275, 1997.\n[10] Nina Amenta, , Sunghee Choi and Ravi Krishna Kolluri. \"The power\ncrust, unions of balls, and the medial axis transform, jur.Computational\nGeometry: Theory and Applications, vol. 19, no. 2-3, pp. 127-153,\n2001.\n[11] B. Chazelle, \"On the convex layers of a planar set,\" IEEE Transactions\non Information Theory, vol. 31, pp. 509-517, 1985.\n[12] H. Alani, C. B. Jones, and D. Tudhope, \"Voronoi-based region\napproximation for geographical information retrieval with gazetteers,\"\nInternational Journal of Geographical Information Science, vol. 15, no.\n4, pp. 287-306, 2001.\n[13] A. Arampatzis, M. van Kreveld, I. Reinbacher, C. B. Jones, S. Vaid, P.\nClough, H. Joho, and M. Sanderson, \"Web-based delineation of\nimprecise regions,\" Computers, Environment, and Urban Systems, vol.\n30, no. 4, pp. 436-459, 2006.\n[14] G. Garai and B. B. Chaudhuri, \"A split and merge procedure for\npolygonal border detection of dot pattern,\" Image and Vision\nComputing, vol. 17, pp. 75-82, 1999.\n[15] Thomas Auer and Martin Held.Heuristics for the generation of random\npolygons. In Proc. of the 8th Canadian Conference on Compu. Geom.\n(CCCG'96), pages 38-43, 1996.\n[16] S.P. Fekete, W.R. Pulleyblank. Area Optimization of Simple Polygons,\nProceedings of the 9th Annual ACM Symposium on Computational\nGeometry (SoCG '93), pp. 173-182.\n[17] D. Eppstein, M. Overmars, G. Rote, and G. Woeginger. Finding\nminimum area k-gons. Jur.Disc. Comp. Geom. 7(1):45-58, 1992.\n[18] F. Preparata and M.I. Shamos. Computational Geometry: An\nintroduction. Springer-Verlag, Berlin, 1985.\n[19] Goodman J.E., O-Rourke J. - Handbook of Discrete and Computational\nGeometry, 2ed, CDC, 2004","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 53, 2011"}