Research On Complexity And Fixed Parameter Algorithms For Point Covering Problems

Point covering problems are fundamental problems in computational geometry. The study of such problems has great theoretical significance and practical values in many fields such as VLSL design, movement of heavy machinery and motion planning. The paper mainly studies on rectilinear spanning path problem and rectilinear spanning tour problem in the aspects of computational complexity and fixed parameterized algorithms.In this paper, we study the NP-completeness of Rectilinear Spanning Path and Rectilinear Spanning Tour in2-dimensions. We prove that Rectilinear Spanning Path in2-dimensions is NP-complete by a reduction from Constrained Bipartite Vertex Cover. Similarly, the Rectilinear Spanning Tour problem in2-dimensions is also proved to be NP-complete. The above proof solves an open problem and is an important complement to the study of computational complexity for these two problems.We also study the Constrained Rectilinear Spanning Path problem from the parameterized complexity point of view. By analyzing the structure of problem instance, we propose3reduction rules and an O(k2) kernel is obtained with running time O(n2). Based on branch and search and dynamic programming, we propose an FPT algorithm with running time O(dk-12kk2+dkn) in arbitrary d-dimensions, which greatly improves the previous best result O((0.74dk)k(kd+n)(?)k) and is the first FPT algorithm that runs in O*(2O(k)). When d=2, we further improve this result to O(3.24kk2+1.62kn) by optimizing the branching strategy. The above two algorithms are also modified to fit the Rectilinear Spanning Tour problem. We also implement above algorithms and the experiment shows that the improved algorithm can practically solve many instances.