Theme-Logo
  • Login
  • Home
  • Course
  • Publication
  • Theses
  • Reports
  • Published books
  • Workshops / Conferences
  • Supervised PhD
  • Supervised MSc
  • Supervised projects
  • Education
  • Language skills
  • Positions
  • Memberships and awards
  • Committees
  • Experience
  • Scientific activites
  • In links
  • Outgoinglinks
  • News
  • Gallery
publication name Orbiting Triangle Method for Convex Polygon Triangulation
Authors Sead H. Mašović, Islam A. Elshaarawy, Predrag S. Stanimirović, Predrag V. Krtolica
year 2018
keywords
journal Applicable Analysis and Discrete Mathematics
volume 12
issue 2
pages 439-454
publisher Not Available
Local/International International
Paper Link http://www.doiserbia.nb.rs/Article.aspx?ID=1452-86301800012B
Full paper download
Supplementary materials Not Available
Abstract

Finding all possible triangulations of convex polygon is a highly time and memory space consuming combinatorial problem. Therefore, it is very important to develop algorithms for generating triangulations as efficiently as possible. This paper presents a new method for generating triangulations of a convex polygon, called Orbiting triangle method (OTM). The method is based on using the set of (n-1)-gon triangulations during the set of n-gon triangulations creation. The main feature of the OTM algorithm is the use of the Catalan triangle to identify valid triangulations, so that the algorithm spends almost no time to eliminate duplicates. In this way, the method possesses small complexity and saves the computational time required for detecting and eliminating duplicates.

Benha University © 2023 Designed and developed by portal team - Benha University