Geodesic disks and clustering in a simple polygon
文献类型:期刊论文
作者 | Borgelt, Magdalene G.; Van Kreveld, Marc; Luo, Jun |
刊名 | International Journal of Computational Geometry & Applications
![]() |
出版日期 | 2011 |
卷号 | 21期号:6页码:595-608 |
英文摘要 | Let P be a simple polygon of it vertices and let S be a set of N points lying in the interior of P. A,geodesic disk GD(p, r) with center p and radius r is the set of points in P that have a geodesic distance <= r from p (where the geodesic distance is the length of the shortest polygonal path connection that lies in P). Inthis paper we present an output sensitive algorithm for finding all N geodesic disks centered at the points of S, for a given value of r. Our algorithm runs in O((n + (kn)(2/3) + k) log(c) n) time for some constant c and output size k. It is the basis of a cluster reporting algorithm where geodesic distatices are used. |
收录类别 | SCI |
原文出处 | http://www.worldscientific.com/doi/abs/10.1142/S0218195911003822 |
语种 | 英语 |
源URL | [http://ir.siat.ac.cn:8080/handle/172644/3564] ![]() |
专题 | 深圳先进技术研究院_数字所 |
作者单位 | International Journal of Computational Geometry & Applications |
推荐引用方式 GB/T 7714 | Borgelt, Magdalene G.,Van Kreveld, Marc,Luo, Jun. Geodesic disks and clustering in a simple polygon[J]. International Journal of Computational Geometry & Applications,2011,21(6):595-608. |
APA | Borgelt, Magdalene G.,Van Kreveld, Marc,&Luo, Jun.(2011).Geodesic disks and clustering in a simple polygon.International Journal of Computational Geometry & Applications,21(6),595-608. |
MLA | Borgelt, Magdalene G.,et al."Geodesic disks and clustering in a simple polygon".International Journal of Computational Geometry & Applications 21.6(2011):595-608. |
入库方式: OAI收割
来源:深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。