Constructing a Simple Polygonalizations

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.

Authors:

• V. Tereshchenko
• V. Muravitskiy

Keywords:

• simple polygon
• approximate algorithm
• minimal area polygon
• polygonalizations

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