Novel algorithms for optimal triangulation and polygonization of planar point sets

Date

2020-08

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

This dissertation follows a three-paper format. Abstracts for each paper are presented below.

First Research Study: Novel Heuristic for Approximating Minimum Weight Triangulation of Planar Point Sets

We introduce a novel heuristic for the problem of finding close approximations to Minimum Weight Triangulation (MWT) of a planar point set, a classical problem of computational geometry with many applications. Our algorithm constructs Greedy Compact Triangulation (GCT) by progressively adding most compact non-intersecting empty 3-gons. It further improves GCT by performing weight-reducing edge flips to create improved Greedy Compact Triangulation (iGCT). We prove that the time and space complexity of our algorithm are O(n^4) and O(n^3) respectively. We also demonstrate that GCT approximates MWT to within a constant factor in a variety of point set configurations, including ones where other important triangulations such as Delaunay and Greedy fail to do so. This leads us to conjecture that GCT is only the second known triangulation that approximates MWT to within a constant factor in all point set configurations.

Second Research Study: Incidence of Minimum Perimeter Polygon within Compact Triangulation of Planar Point Sets

In prior research study we introduced improved Greedy Compact Triangulation (iGCT) as approximating to within constant factor the Minimum Weight Triangulation (MWT) of planar point sets. In this research we investigated the degree of embeddedness of TSP polygons within iGCT of planar point sets and the quality of minimum perimeter polygons embedded fully in iGCT. We achieved this by analyzing eighteen planar point sets from the library of TSPLIB problems. We found that TSP polygons are fully embedded in iGCT approximately 61% of the time, and that on average the minimum perimeter polygons embedded in iGCT are within 0.36% of the perimeter length of TSP polygons. In one of the TSPLIB problems the length of the minimum perimeter polygon was found to be lower than the previously reported optimal TSP solution. We also presented an in-depth review of deviations between the embedded minimum weight polygon embedded in iGCT and the TSP polygon identified for the given planar point set in our sample.

Third Research Study: “Apple Carving” Algorithm to Approximate Minimum Perimeter Polygon within Compact Triangulation of Planar Point Sets

We propose a modified version of the Convex Hull algorithm for approximating minimum-length Hamiltonian cycle (TSP) in planar point sets. Starting from a full compact triangulation of a point set, our heuristic “carves out” candidate triangles with the minimal Triangle Inequality Measure until all points lie on the outer perimeter of the remaining partial triangulation. The initial candidate list consists of triangles on the convex hull of a given planar point set; the list is updated as triangles are eliminated and new triangles are thereby exposed. We show that the time and space complexity of the “apple carving” algorithm are O(n^2) and O(n) respectively. We tested our algorithm using a well-known problem subset and demonstrated that our proposed algorithm outperforms nearly all other TSP tour construction heuristics.

Description

Keywords

Traveling salesman problem, Minimum weight triangulation, Heuristics, Combinatorial optimization, Computational geometry, Empty 3-gons

Citation