Đang chuẩn bị liên kết để tải về tài liệu:
A-non recursive algorithm for polygon triangulation

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. | Yugoslav Journal of Operations Research 13 (2003), Number 1, 61-67 A NON-RECURSIVE ALGORITHM FOR POLYGON TRIANGULATION Predrag S. STANIMIROVI], Predrag V. KRTOLICA, Rade STANOJEVI] Faculty of Science and Mathematics, University of Ni{, Ni{, Serbia pecko@pmf.pmf.ni.ac.yu, krca@pmf.pmf.ni.ac.yu, rrr@eunet.yu 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. Keywords: Reverse Polish notation, convex polygon triangulation, contex-free grammar. 1. INTRODUCTION AND PRELIMINARIES The triangulation of the convex polygon is the following problem. For the given polygon find the number of the possible splitting on triangles by its diagonals without gaps and overlaps of these splitting. This is the classical problem solved so far in a few ways. One solution from [4] uses the context-free grammar with productions: S → aSS, S → b , (1) where a and b are terminals, and S a non-terminal symbol. The triangulation of polygon is based on the following principles: (a) The non-terminal S represents an oriented topological segment. This segment is named potential. (b) The chain aSS corresponds to the oriented topological triangle with one real edge a and two potential edges S and S . (c) The production S → aSS means the replacement of the potential segment S by the triangle aSS , consisting of its real edge a defined orientation and potential edges S , being the edge a with defined 62 P.S. Stanimirovi}, P.V. Krtolica, R. Stanojevi} / A Non-Recursive Algorithm orientation and potential edges S , being the edge of the polygon which is about to be defined. (d) The replacement S → b means replacing the potential edge S with the real edge b . If we apply n − 2 times the first production in (1) (in other words, if .