组合优化领域最经典的NP-困难问题之一，点覆盖问题，它指的是用最少的点来覆盖图中的所有的边.后来，在2010年Bre(s)ar等人对此问题进行了推广，提出了k-路点覆盖问题（MVCPk），即寻找图G的一个最小顶点集F使得任意一条k-路至少有一个点被包含在F中.如果一个VCPk，其导出子图连通，则称为最小连通k-路点覆盖问题，记为MCVCPk.当考虑加权的情况，目标就是找到一个权和最小的VCPk(简称MWVCPk).　　Liu等人给出了在单位圆盘图上对于连通的MCVCPk问题的PTAS近似算法.以及Zhang等人给出了在球图上对于最小点覆盖问题的PTAS近似算法.那么对于球图上的MVCPk问题而言，是否也能得到PTAS的近似算法呢？本文主要使用局部搜索方法，对于球图上MVCPk问题，在球图中的所有球中的最大半径与最小半径的比值有一个常数上界时，给出一个PTAS近似算法.同时给出MCVCPk在单位圆盘图上的一个简化算法.它不再象Liu等的文章中那样需要基于一个常数近似算法，算法和分析过程也比Liu等的文章有极大的简化.　　本学位论文共分五章:在第一章中，介绍一些准备知识，以及相关领域的研究现状.第二章中，研究了在球图上的MVCPk问题，并且给出其近似比以及复杂性分析.第三章中，基于对MVCPk问题的进一步推广，进一步研究了在球图上m-重的MVCPk问题.第四章中，给出单位圆盘图上的CVCPk问题的一个简化的PTAS近似算法.第五章中，基于以上问题的讨论与总结.