点集覆盖问题是计算几何领域的一类基本问题,其中包括了直线覆盖、路径覆盖、回路覆盖等问题。此类问题的研究不仅具有重大的理论意义,而且在电路设计、重型器械移动、路径规划等领域有着重大的应用价值。本文分别从计算复杂性和固定参数算法的角度,着重研究了此类问题中的直角路径覆盖问题和直角回路覆盖问题。从计算复杂性的角度,本文研究了直角路径覆盖问题在二维平面上的NP复杂性。本文通过受限二分图顶点覆盖问题到二维平面上的直角路径覆盖问题的多项式时间规约,证明了二维平面上的直角路径覆盖问题是NP-完全问题。利用类似的方法,本文也证明了二维平面上的直角回路覆盖问题是NP-完全问题。以上证明解决了这两个问题在二维平面上是否为NP-完全问题的开放问题,完善了这两个问题的计算复杂性研究。从参数计算理论的角度,本文研究了直角路径覆盖问题的一种简化形式：受限直角路径覆盖问题。本文利用核心化技术分析了该问题的结构特征,提出了三条规约规则,在O(n2)时间内获得了该问题一个大小为O(k2)的核。通过运用分支搜索和动态规划技术,本文提出了一个时间复杂度为O(dk+12kk2+dkn)的固定参数算法,极大地改进了当时最好的结果O((0.74dk)k(kd+n)(?k),并且是该问题第一个复杂度形如O*(2O(k)的算法。在d=2时,本文通过进一步优化分支搜索的策略,提出了时间复杂度为O(3.24kk2+1.62kn)的固定参数算法。同时,本文论证了这两个算法通过修改也能适用于受限直角回路覆盖问题。最后,本文通过实验分析了以上提出的改进算法的实际运行效率,证明了以上改进算法能有效的解决一部分实际问题。