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., "Triangulation a simple polygon in linear time", Discrete Comput. Geom., 6 (1991) 485-524.

Chazelle, B., and Palios, L., "Decomposition algorithms in geometry", in: Ch.L. Bajaj (ed.), Algebraic Geometry and Its Application, Springer-Verlag, New York, Inc., 1994, 419-447.

Corman, T.H., Leiserson, C.E., and Rivest, R.L., Introduction to Algorithms, MIT Press, Cambridge, Massachusetts, London, England, 1990.

Kross, M., and Lentin, A., Notions sur les grammaries formelles, Gauthier-Villars, 1967.

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

Tremblay, J.P., and Sorenson, P.G., The Theory and Practice of Compiler Writing, McGraw-Hill Book Company, New York, 1985.

Downloads

Published

2003-03-01

Issue

Vol. 13 No. 1 (2003)

Section

Research Articles

License

Copyright (c) 2003 YUJOR

Creative Commons License

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