Planar $\beta$-skeletons via point location in monotone subdivisions of subset of lunes

Abstract

We present a new algorithm for lune-based $\beta$-skeletons for sets of $n$ points in the plane, for $\beta \in (2,\infty ]$, the only case when optimal algorithms are not known. The running time of the algorithm is $O(n^{3/2}{\log }^{1/2}n)$, which is the best known and is an improvement of Rao and Mukhopadhyay \cite{rm97} result. The method is based on point location in monotonic subdivisions of arrangements of curve segments.

Cited by in corpus (1)

• Algorithmic and geometric aspects of data depth with focus on $\beta$-skeleton depth