Optimal and suboptimal robust algorithms for proximity graphs

Given a set of <f>n</f> points in the plane, any <f>β</f>-skeleton and <f>[γ0,γ1]</f>-graph can be computed in quadratic time. The presented algorithms are optimal for <f>β</f> values that are less than 1 and <f>[γ0,γ1]</f> values that result in non-planar graphs. We show a numerically robust algorithm that computes Gabriel graphs in quadratic time and degree 2. We finally show how a <f>β</f>-spectrum can be computed in optimal <f>O(n2)</f> time. [Copyright &y& Elsevier]