Output-sensitive algorithm for computing β-skeletons

作     者：Mukhopadhyay, A Rao, SV 

作者机构：Univ Windsor Sch Comp Sci Windsor ON N9B 3P4 Canada Indian Inst Technol Dept Comp Sci & Engn Guwahati 781001 Assam India 

出 版 物：《COMPUTING》 (Comput Vienna New York)

年 卷 期：2000年第65卷第3期

页      面：285-289页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：computational geometry beta-skeleton shape of a point set output-sensitive algorithm 

摘      要：The beta -skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying the parameter beta. For a fixed value of beta, a beta -skeleton is a geometric graph obtained by joining each pair of points whose beta -neighborhood is empty. For beta greater than or equal to 1, this neighborhood of a pair of points p(i),p(j) is the interior of the intersection of two circles of radius beta\(p(i)p(j)) over bar\/2, centered at the points (1 - beta /2)p(i) + (beta /2)p(j) and (beta /2)p(i) + (1 - beta /2)p(j), respectively. For beta epsilon (0, 1], it is the interior of the intersection of two circles of radius \(p(i)p(j)) over bar\(2 beta), passing through p(i) and p(j). In this paper we present an output-sensitive algorithm for computing a beta -skeleton in the metrics II and l(infinity) for any beta greater than or equal to 2. This algorithm is in O(n log n + k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n(5/2) log n) [7].