# TRIANGULATING A REGION BETWEEN ARBITRARY POLYGONS

## Authors

• Vasyl Tereshchenko
• Yaroslav Tereshchenko

## Keywords:

Triangulation, simple polygon, holes, region, reducible problem, monotone polygon.

## Abstract

The paper presents an optimal algorithm for triangulating a region between arbitrary polygons on the plane with time complexity O(N log⁡N ). An efficient algorithm is received by reducing the problem to the triangulation of simple polygons with holes. A simple polygon with holes is triangulated using the method of monotone chains and keeping overall design of the algorithm simple. The problem is solved in two stages. In the first stage a convex hull for m polygons is constructed by Graham’s method. As a result, a simple polygon with holes is received. Thus, the problem of triangulating a region between arbitrary polygons is reduced to the triangulation of a simple polygon with holes. In the next stage the simple polygon with holes is triangulated using an approach based on procedure of splitting polygon onto monotone polygons using the method of chains . An efficient triangulating algorithm is received. The proposed algorithm is characterized by a very simple implementation, and the elements (triangles) of the resulting triangulation can be presented in the form of simple and fast data structure: a tree of triangles .

## References

B. Chazelle, N. Shouraboura, “Bounds on the size of tetrahedralizations,” J. Discrete & Computational Geometry, vol. 14, no. 1, pp. 429-444, 1995.

V. Tereshchenko, S. Pilipenko, A. Fisunenko, “Domain triangulation between convex polytopes,” J. Procedia Computer Science, vol. 18, pp. 2500–2503, 2013.

F. Preparata, M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, Berlin, 1985, 398 p.

V. S. Bileckiy, Small Mine Encyclopedia, vol. 1-3, Shidniy Vidavnichiy Dim, Donetsk, 2013, 1936 p. (in Ukrainian)

J. E. Goodman, J. O’Rourke, Handbook of Discrete and Computational Geometry, 2nd ed., CRC, A CRC Press Company, Boca Raton, London, 2004, 1453 p.

B. Joe, “Construction of three-dimensional Delaunay triangulations using local transformations,” J. Computer Aided Geometric Design, no. 8, pp. 123-142, 1991.

R. E. Tarjan, C. J. Van Wyk, “An O(nlog logn)-time algorithm for triangulating a simple polygon,” SIAM J. Comput, vol. 17, pp. 143–178, 1988.

D. G. Kirkpatrick, M. M. Klawe, R. E. Tarjan, “Polygon triangulation in O(nlog logn) time with simple data structures,” J. Discrete Comput. Geom., vol. 7, pp. 329–346, 1992.

K. L. Clarkson, R. E. Tarjan, C. J. Van Wyk, “A fast Las Vegas algorithm for triangulating a simple polygon,” J. Discrete Comput. Geom., vol. 4, pp. 423–432, 1989.

O. Devillers, “Randomization yields simple O(nlogn) algorithms for difficult Ω(n) problems,” Internat. J. Comput. Geom. Appl., vol. 2, pp. 97–111, 1992.

R. Seidel, “A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons,” J. Comput. Geom. Theory Appl., vol. 1, pp. 51–64, 1991.

V. Tereshchenko, I. Budjak, A. Fisunenko, “The unified algorithmic platform for solving complex problems of computational geometry,” J. Parallel Computing Technologies, vol. 7979, pp. 424-428, 2013.

M. de Berg, M. van Kreveld, M. Overmars, O. Cheong, Computational Geometry, 3rd ed., Springer-Verlag, Berlin, 2008, 398 p.

B. Chazelle, “Triangulating a simple polygon in linear time,” J. Discrete Comput. Geom., vol. 6, pp. 485-524, 1991.

E. Edelsbrunner, L. J. Guibas, J. Stolfi, “Optimal point location a monotone subdivision,” SIAM J. Comput., vol. 15, no. 2, pp. 317–340, 1986.

G. H. Meisters, “Polygons have ears,” J. American Mathematical Monthly, vol. 82, pp. 648–651, 1975.

V. Tereshchenko, Y. Tereshchenko, D. Kotsur, “Point triangulation using Graham’s scan,” in Proceedings of the 5-th IEEE International Conference on Innovative Computing, Galicia, Spain, May 20-22, 2015, pp. 148-151.

U. Grossmann, M. Schauch, S. Hakobyan, “The accuracy of algorithms for WLAN indoor positioning and the standardization of signal reception for diferent mobile devices”, International Journal of Computing, vol. 6, issue 1, pp. 103-109, 2007.

D. Zahorodnia, Y. Pigovsky, P. Bykovyy, “Canny-based method of image contour segmentation,” International Journal of Computing, vol. 15, issue 3, pp. 200-205, 2016.

N. I. Korsunov, D. A. Toropchin, “The method of finding the spam images based on the hash of the key points of the image,” International Journal of Computing, vol. 16, issue 4, pp. 259-264, 2016.

2017-09-30

## How to Cite

Tereshchenko, V., & Tereshchenko, Y. (2017). TRIANGULATING A REGION BETWEEN ARBITRARY POLYGONS. International Journal of Computing, 16(3), 160-165. https://doi.org/10.47839/ijc.16.3.899

Articles