New sequential and parallel algorithms for computing the β-spectrum

β-skeletons, prominent members of the neighborhood graph family, have interesting geometric properties and various applications ranging from geographic networks to archeology. This paper focuses on computing the β  -spectrum, a labeling of the edges of the Delaunay triangulation, DT(V)DT(V), which makes it possible to quickly find the lune-based β-skeleton of V   for any query value β∈[1,2]β∈[1,2]. We consider planar n-point sets V   with LpLp metric, 1