Constructing a Simple Polygonalizations

Authors: V. Tereshchenko, V. Muravitskiy

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.

Keywords: simple polygon, approximate algorithm, minimal area polygon, polygonalizations

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060926

References:

[1] 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.
[2] H. J. Miller and J. Han, Eds., Geographic Data Mining and Knowledge Discovery. CRC Press, 2001.
[3] ] 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.
[4] A. Galton, "Dynamic collectives and their collective dynamics," in COSIT, ser. Lecture Notes in Computer Science. Springer, 2005, vol. 3693, pp. 300-315.
[5] 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.
[6] 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.
[7] M. Melkemi and M. Djebali, "Computing the shape of a planar points set," Pattern Recognition, vol. 33, pp. 1423-1436, 2000.
[8] 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.
[9] 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.
[10] 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.
[11] B. Chazelle, "On the convex layers of a planar set," IEEE Transactions on Information Theory, vol. 31, pp. 509-517, 1985.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
[16] 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.
[17] D. Eppstein, M. Overmars, G. Rote, and G. Woeginger. Finding minimum area k-gons. Jur.Disc. Comp. Geom. 7(1):45-58, 1992.
[18] F. Preparata and M.I. Shamos. Computational Geometry: An introduction. Springer-Verlag, Berlin, 1985.
[19] Goodman J.E., O-Rourke J. - Handbook of Discrete and Computational Geometry, 2ed, CDC, 2004