Planar $β$-skeletons via point location in monotone subdivisions of subset of lunes
Mirosław Kowaluk · arXiv (Cornell University) · 2014
We present a new algorithm for lune-based $β$-skeletons for sets of $n$ points in the plane, for $β\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.