Article Free Access Share on Coping with inconsistencies: a new approach to produce quality triangulations of polygonal domains with holes Authors: Elefterios A. Melissaratos View Profile , Diane L. Souvaine View Profile Authors Info & Claims SCG '92: Proceedings of the eighth annual symposium on Computational geometryJuly 1992 Pages 202–211https://doi.org/10.1145/142675.142719Published:01 July 1992Publication History 21citation316DownloadsMetricsTotal Citations21Total Downloads316Last 12 Months14Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The goal of this paper is to show that the concept of the shortest path inside a polygonal region contributes to the design of efficient algorithms for certain geometric optimization problems involving simple polygons: computing optimum separators, maximum area or perimeter-inscribed triangles, a minimum area circumscribed concave quadrilateral, or a maximum area contained triangle. The structure for the algorithms presented is as follows: (a) decompose the initial problem into a low-degree polynomial number of optimization problems; (b) solve each individual subproblem in constant time using standard methods of calculus, basic methods of numerical analysis, or linear programming. These same optimization techniques can be applied to splinegons (curved polygons). First a decomposition technique for curved polygons is developed; this technique is substituted for triangulation in creating equally efficient curved versions of the algorithms for the shortest-path tree, ray-shooting, and two-point shortest path problems. The maximum area or perimeter inscribed triangle problem, the minimum area circumscribed concave quadrilateral problem and maximum area contained triangle problem have applications to robotics and stock-cutting. The results of this paper appear in E. A. Melissaratos’s Ph.D. thesis [Mesh Generation and Geometric Optimization, Rutgers University, New Brunswick, NJ, 1991].

We have developed techniques which contribute to efficient algorithms for certain geometric optimization problems involving simple polygons: computing minimum separators, maximum inscribed triangles, a minimum circumscribed concave quadrilateral, or a maximum contained triangle.The structure for our algorithms is as follows: a) decompose the initial problem into a low-degree polynomial number of easy optimization problems; b) solve each individual subproblem in constant time using the methods of cealcu-Ins, standard methods of numerical analysis, or linear programming.The decomposition step uses shorteat path trees inside simple polygons (Guibas et. al.~ 1987) and, in the case of inscribed triangles, produces a new class of polygons, the fan-shaped polygon.By extending the shortest-path algorithm to splinegons, we also generate splinegon-versions of the algorithms for some of the optimization problems.The problems we discuss fall into four subgroups: Separators: If two points z and y lie on the boundary of simple polygon P and define a directed line segment zy C_ P that separates P into two sets PL and Pa, then zy is called a separator.M i n i m u m l e n g t h : The areas of PL and PR are defined by constants KL and KR.Find a separator of minimum length.