Optimal covering tours with turn costs

摘要: We give the first algorithmic study of a class “covering tour” problems related to geometric Traveling Salesman Problem: Find polygonal tour for cutter so that it sweeps out specified region (“pocket”), in order minimize cost depends not only on length but also number turns. These arise naturally manufacturing applications computational geometry automatic tool path generation and inspection systems, as well arc routing (“postman”) with turn penalties. prove lower bounds (NP-completeness minimum-turn milling) efficient approximation algorithms several natural versions problem, including polynomial-time scheme based novel adaptation m-guillotine method.