Output-sensitive algorithm for computing \(\beta\)-skeletons (Q1840767)

A \(\beta\)-skeleton of a planar set of \(n\) points, i.e. the geometric graph obtained by joining the pair of points whose \(\beta\)-neighborhood is empty, can be computed by a standard algorithm in time \(O(n^{5/2}\log n)\). An algorithm is proposed to detect the \(\beta\)-skeleton in time \(O(n\log n+k)\), where \(k\) is the size of the output graph. After the algorithm description, it is proved a theorem concerning the space and time necessary to perform the algorithm.