2023/02/14 by Kerem Geva, Matthew J. Katz, Geva, Kerem +5
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2302.06776
openalex publication_date 2023/02/14 · openalex created_date 2023/02/17 · openalex updated_date 2026/07/28
Let E=\e1,…,en\ be a set of C-oriented disjoint segments in the plane, where C is a given finite set of orientations that spans the plane, and let s and t be two points. %(We also require that for each orientation in C, its opposite orientation is also in C.) We seek a minimum-link C-oriented tour of E, that is, a polygonal path π from s to t that visits the segments of E in order, such that, the orientations of its edges are in C and their number is minimum. We present an algorithm for computing such a tour in O(|C|2 ⋅ n2) time. This problem already captures most of the difficulties occurring in the study of the more general problem, in which E is a set of not-necessarily-disjoint C-oriented polygons.