TY - JOUR
T1 - Conceptual framework for finding approximations to minimum weight triangulation and traveling salesman problem of planar point sets
AU - Dodig, Marko
AU - Smith, Milton
N1 - Publisher Copyright:
© 2020 Science and Information Organization.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Combinatorial optimization
KW - Computational geometry
KW - Minimum weight triangulation
KW - Traveling salesman problem
UR - http://www.scopus.com/inward/record.url?scp=85085547123&partnerID=8YFLogxK
U2 - 10.14569/IJACSA.2020.0110403
DO - 10.14569/IJACSA.2020.0110403
M3 - Article
AN - SCOPUS:85085547123
VL - 11
SP - 12
EP - 18
JO - International Journal of Advanced Computer Science and Applications
JF - International Journal of Advanced Computer Science and Applications
SN - 2158-107X
IS - 4
ER -