Conceptual framework for finding approximations to minimum weight triangulation and traveling salesman problem of planar point sets

Marko Dodig, Milton Smith

Research output: Contribution to journalArticlepeer-review

Abstract

We introduce a novel Conceptual Framework for finding approximations to both Minimum Weight Triangulation (MWT) and optimal Traveling Salesman Problem (TSP) of planar point sets. MWT is a classical problem of Computational Geometry with various applications, whereas TSP is perhaps the most researched problem in Combinatorial Optimization. We provide motivation for our research and introduce the fields of triangulation and polygonization of planar point sets as theoretical bases of our approach, namely, we present the Isoperimetric Inequality principle, measured via Compactness Index, as a key link between our two stated problems. Our experiments show that the proposed framework yields tight approximations for both problems.

Original languageEnglish
Pages (from-to)12-18
Number of pages7
JournalInternational Journal of Advanced Computer Science and Applications
Volume11
Issue number4
DOIs
StatePublished - 2020

Keywords

  • Combinatorial optimization
  • Computational geometry
  • Minimum weight triangulation
  • Traveling salesman problem

Fingerprint Dive into the research topics of 'Conceptual framework for finding approximations to minimum weight triangulation and traveling salesman problem of planar point sets'. Together they form a unique fingerprint.

Cite this