Fast algorithms for computing β-skeletons and their relatives

摘要

In this paper we present fast algorithms for computing β-skeletons (Kirkpatrick and Radke, in: Toussaint (Ed.), Computational Geometry, North-Holland, Amsterdam, 1985, pp. 217–248) and two of its relatives, namely, kβ-skeletons, and additively weighted β-skeletons. A β-skeleton is a generalization of the Relative Neighborhood Graph, introduced by Toussaint (Toussaint, Pattern Recognition 12 (1980) 261–268). Our algorithms are in O(n3/2logn) for β⩾1 and in O(n5/2logn) for β∈[0,1) under the metric Lp for 1