  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.
