Commenced in January 2007
Paper Count: 30184
Constructing a Simple Polygonalizations
Abstract:We consider the methods of construction simple polygons for a set S of n points and applying them for searching the minimal area polygon. In this paper we propose the approximate algorithm, which generates the simple polygonalizations of a fixed set of points and finds the minimal area polygon, in O (n3) time and using O(n2) memory.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060926Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1819
 Chong Zhu, Gopalakrishnan Sundaramb, J. Snoeyink and Joseph S. B. Mitchell. Generating random polygons with given vertices. Jur.Computational Geometry: Theory and Applications . Vol. 6, Issue 5, Elsevier, 1996, Pages 277-290.
 H. J. Miller and J. Han, Eds., Geographic Data Mining and Knowledge Discovery. CRC Press, 2001.
 ] A. Galton and M. Duckham, "What is the region occupied by a set of points?" in GIScience, ser. Lecture Notes in Computer Science. Springer, 2006, vol. 4197, pp. 81-98.
 A. Galton, "Dynamic collectives and their collective dynamics," in COSIT, ser. Lecture Notes in Computer Science. Springer, 2005, vol. 3693, pp. 300-315.
 M. F. Worboys and M. Duckham, "Monitoring qualitative spatiotemporal change for geosensor networks," International Journal of Geographic Information Science, vol. 20, no. 10, pp. 1087-1108, 2006.
 H. Edelsbrunner, D. G. Kirkpatrick, and R. Seidel, "On the shape of a set of points in the plane," IEEE Transactions on Information Theory, vol. IT-29, no. 4, pp. 551-558, 1983.
 M. Melkemi and M. Djebali, "Computing the shape of a planar points set," Pattern Recognition, vol. 33, pp. 1423-1436, 2000.
 M. J. Fadili, M. Melkemi, and A. ElMoataz, "Non-convex onion-peeling using a shape hull algorithm," Pattern Recognition Letters, vol. 25, pp. 1577-1585, 2004.
 A. R. Chaudhuri, B. B. Chaudhuri, and S. K. Parui, "A novel approach to computation of the shape of a dot pattern and extraction of its perceptual border," Computer Vision and Image Understanding, vol. 68, no. 3, pp. 257-275, 1997.
 Nina Amenta, , Sunghee Choi and Ravi Krishna Kolluri. "The power crust, unions of balls, and the medial axis transform, jur.Computational Geometry: Theory and Applications, vol. 19, no. 2-3, pp. 127-153, 2001.
 B. Chazelle, "On the convex layers of a planar set," IEEE Transactions on Information Theory, vol. 31, pp. 509-517, 1985.
 H. Alani, C. B. Jones, and D. Tudhope, "Voronoi-based region approximation for geographical information retrieval with gazetteers," International Journal of Geographical Information Science, vol. 15, no. 4, pp. 287-306, 2001.
 A. Arampatzis, M. van Kreveld, I. Reinbacher, C. B. Jones, S. Vaid, P. Clough, H. Joho, and M. Sanderson, "Web-based delineation of imprecise regions," Computers, Environment, and Urban Systems, vol. 30, no. 4, pp. 436-459, 2006.
 G. Garai and B. B. Chaudhuri, "A split and merge procedure for polygonal border detection of dot pattern," Image and Vision Computing, vol. 17, pp. 75-82, 1999.
 Thomas Auer and Martin Held.Heuristics for the generation of random polygons. In Proc. of the 8th Canadian Conference on Compu. Geom. (CCCG'96), pages 38-43, 1996.
 S.P. Fekete, W.R. Pulleyblank. Area Optimization of Simple Polygons, Proceedings of the 9th Annual ACM Symposium on Computational Geometry (SoCG '93), pp. 173-182.
 D. Eppstein, M. Overmars, G. Rote, and G. Woeginger. Finding minimum area k-gons. Jur.Disc. Comp. Geom. 7(1):45-58, 1992.
 F. Preparata and M.I. Shamos. Computational Geometry: An introduction. Springer-Verlag, Berlin, 1985.
 Goodman J.E., O-Rourke J. - Handbook of Discrete and Computational Geometry, 2ed, CDC, 2004