·30· 智能系统学报 第3卷 法种类而且均以x线性的复杂性近似地解决几个困 [12]MITCHELL J S B,SHARIR M.New results on shor- 难的几何问题 test paths in three dimensions[C]//Proc SCG Brook- lyn.New York,2004. 参考文献： [13]CANN YJ,REIF J H.New lower bound techniques for [1 ]BULOW T,KL ETTE R.Digital curves in 3D space and a robot motion planning problems[C]//Proc IEEE Conf Foundations Computer Science.Los Angeles,USA, linear-time length estimation algorithm [J ]IEEE Trans 1987. Pattern Analysis Machine Intelligence,2002,24(7):962 作者简介： -970. 李发捷，男，1965年生，博士，荷兰格罗 [2]LIF,KL ETTE R.Exact and approximate algorithms for 宁根大学博士后，主要研究方向为数字几何、 the calculation of shortest paths [R].IMA Minneapolis 计算几何、天文数据的计算机视觉分析，发表 2006.www.ima.umn.edu/preprints/oct2006. 论文10余篇. [3]DROR M,EFRAT A,LUBIW A,et al.Touring a se- quence of polygons[C]//ProcSTOC.San Diego,USA, 2003. [4]HOEFT J,PALEHAR U S.Heuristics for the platecut- KL ETTE Reinhard,男，1950年生，博 ting traveling salesman problem [J ]IIE Transactions, 士，教授，主要研究方向为并行计算、图像处 1997,29(9):719.731. 理、计算机视觉、数字几何、计算几何，发表论 (5]LAWLER E,L ENSTRA J,RINNOOY K A,et al.The 文250多篇，出版专著8部，编辑专著21部」 traveling salesman problem [M].New York:John Wiley KL ETTE Reinhard教授担任“IEEE and Sons,1985. Trans.PAMl”(Associate Editor),“CAAl [6]LAPORTE G,MERCURE H,NOBERT Y.Generalized Transactions on Intelligent Systems(智能系 traveling salesman problem through n clusters [J].Dis- 统学报)”(Member of Editorial Board),“Springers Computa crete Applied Mathematics,1987,18(2):185-197. tional Imaging and Vision"(Editor),"International Journal of [7]NOON C E.BEAN J C.An ecient transformation of the Computer Vision"(Member of Editorial Board),"Machine generalized traveling salesman problem [J ]INFOR, GRAPHICS &VISION"(Member of Advisory Board),"Op- 1993,31:39.44. to-Electronics Review"(Member of Editorial Advisory [8 GAREY M R,GRA HAM R L,JOHNSON D S.Some Board)等期刊的编辑或委员.是以下因际学术会议的主要发 NP-complete geometric problems[C]//Proc ACM Sym- 起人：CAIP conferences(International Conference on Com pos Theory Computing.Hershey,USA,1976. puter Analysis of Images and Patterns)(Member of Steering [9]GEOFFRION A M.Lagrangean relaxation and its uses in Committee).是28场国际学术会议（在智利、德国、新西兰、 integer programming [J ]Mathematical Programming 台湾等地)的主席或副主席.是2005年DAGM奖获得者之 Study,1974(2):28-114. 一曾应邀在阿根廷、中国、印度、意大利新西兰、台湾和美国 [10]GUIGNARD M,KIM S.Lagrangean decomposition: 等地国际学术会议作报告.在德国柏林技术大学、德因哥廷根 amodel yielding stronger Lagrangean bounds[J ]Math- 大学和新西兰奥克兰大学已指导培养14名博士和100多名 ematical Programming,1987,31(3):271-274 硕士 [11 ]DROR M.Polygon plate-cutting with a given order[J IIE Transactions,1999,31(3):271-274. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.enki.net法种类而且均以κ线性的复杂性近似地解决几个困 难的几何问题. 参考文献 : [1 ]BULOW T , KL ETTE R. Digital curves in 3D space and a linear2time length estimation algorithm [J ]. IEEE Trans Pattern Analysis Machine Intelligence , 2002 ,24 (7) :962 - 970. [2 ]L I F , KL ETTE R. Exact and approximate algorithms for the calculation of shortest paths [ R ]. IMA Minneapolis 2006. www. ima. umn. edu/ preprints/ oct2006. [3 ] DROR M , EFRA T A ,LUBIW A , et al. Touring a se2 quence of polygons[ C ]/ / ProcSTOC. San Diego , USA , 2003. [4 ] HOEFT J , PAL EHAR U S. Heuristics for the platecut2 ting traveling salesman problem [J ]. IIE Transactions , 1997 ,29 (9) :719 - 731. [5 ]LAWL ER E ,L ENSTRA J , RINNOO Y K A , et al. The traveling salesman problem [ M ]. New York :John Wiley and Sons , 1985. [6 ]LAPORTE G, MERCURE H , NOBERT Y. Generalized traveling salesman problem through n clusters[J ]. Dis2 crete Applied Mathematics , 1987 ,18 (2) :185 - 197. [7 ]NOON C E ,BEAN J C. An e2cient transformation of the generalized traveling salesman problem [ J ]. INFOR , 1993 ,31 :39 - 44. [ 8 ] GAREY M R , GRA HAM R L ,JO HNSON D S. Some NP2complete geometric problems[ C]/ / Proc ACM Sym2 pos Theory Computing. Hershey ,USA ,1976. [ 9 ] GEOFFRION A M. Lagrangean relaxation and its uses in integer programming [ J ]. Mathematical Programming Study ,1974 (2) :28 - 114. [10 ] GU IGNARD M , KIM S. Lagrangean decomposition : amodel yielding stronger Lagrangean bounds[J ]. Math2 ematical Programming , 1987 ,31 (3) :271 - 274. [11 ]DROR M. Polygon plate2cutting with a given order[J ]. IIE Transactions , 1999 ,31 (3) :271 - 274. [12 ] MITCHELL J S B ,SHARIR M. New results on shor2 test paths in three dimensions[ C]/ / Proc SCG Brook2 lyn. New York ,2004. [13 ]CANN Y J ,REIF J H. New lower bound techniques for robot motion planning problems[ C]/ / Proc IEEE Conf Foundations Computer Science. Los Angeles , USA , 1987. 作者简介 : 李发捷 ,男 ,1965 年生 ,博士 ,荷兰格罗 宁根大学博士后 ,主要研究方向为数字几何、 计算几何、天文数据的计算机视觉分析 ,发表 论文 10 余篇. KL ETTE Reinhard , 男 , 1950 年 生 , 博 士 ,教授 ,主要研究方向为并行计算、图像处 理、计算机视觉、数字几何、计算几何 ,发表论 文 250 多篇 ,出版专著 8 部 ,编辑专著 21 部. KL ETTE Reinhard 教 授 担 任“IEEE Trans. PAMI”( Associate Editor ) ,“CAAI Transactions on Intelligent Systems (智能系 统学报) ”(Member of Editorial Board) “, Springers Computa2 tional Imaging and Vision”( Editor) “, International Journal of Computer Vision”( Member of Editorial Board) “, Machine GRAPHICS &VISION”(Member of Advisory Board) “, Op2 to2Electronics Review ”( Member of Editorial Advisory Board) 等期刊的编辑或委员. 是以下国际学术会议的主要发 起人 : CAIP conferences ( International Conference on Com2 puter Analysis of Images and Patterns) (Member of Steering Committee) . 是 28 场国际学术会议 (在智利、德国、新西兰、 台湾等地) 的主席或副主席. 是 2005 年 DA GM 奖获得者之 一. 曾应邀在阿根廷、中国、印度、意大利、新西兰、台湾和美国 等地国际学术会议作报告. 在德国柏林技术大学、德国哥廷根 大学和新西兰奥克兰大学已指导培养 14 名博士和 100 多名 硕士. ·30 · 智 能 系 统 学 报 第 3 卷