A non-recursive algorithm for polygon triangulation

Authors

  • Predrag S. Stanimirović Faculty of Science and Mathematics, University of Ni{, Ni{, Serbia
  • Predrag V. Krtolica Faculty of Science and Mathematics, University of Ni{, Ni{, Serbia
  • Rade Stanojević Faculty of Science and Mathematics, University of Ni{, Ni{, Serbia

DOI:

https://doi.org/10.2298/YJOR0301061S

Keywords:

reverse polish notation, convex polygon triangulation, contex-free grammar

Abstract

In this paper an algorithm for the convex polygon triangulation based on the reverse Polish notation is proposed. The formal grammar method is used as the starting point in the investigation. This idea is "translated" to the arithmetic expression field enabling application of the reverse Polish notation method. .

References

Chazelle, B. (1991) Triangulating a simple polygon in linear time. Discrete and Computational Geometry, 6, 5, 485-524

Chazelle, B., Palios, L. (1994) Decomposition algorithms in geometry. u: Ch.L.Bajaj [ur.] Algebraic Geometry and Its Application, Berlin, itd: Springer Verlag, 419-447

Corman, T.H., Leiserson, C.E., Rivest, R.L. (1990) Introduction to algorithms. Cambridge, MA, itd: Massachusetts Institute of Technology Press

Kross, M., Lentin, A. (1967) Notions sur les grammaires formelles. Paris: Gauthier-Villars

Krtolica, P.V., Stanimirović, P.S. (1999) On some properties of reverse Polish notation. Filomat, 13, 157-172

Tremblay, J.P., Sorenson, P.G. (1985) The theory and practice of compiler writing. New York, itd: McGraw-Hill

Downloads

Published

2003-03-01

Issue

Vol. 13 No. 1 (2003)

Section

Research Articles

License

Copyright (c) YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.